【正文】 處理下一等待的工作 ?上機(jī)的工作未處理完成前 ， 不能中途停止 假設(shè) ?單機(jī)排程是最基本的排程問題 ， 其定義為 n件 獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè) ， 以使某一績(jī)效評(píng)估指標(biāo)最佳 定義 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 79 排程之基本評(píng)估指標(biāo) 1/2 作業(yè)流程時(shí)間 (Flowtime)：工作在系統(tǒng)中停留之時(shí)間 。 sisisi dCL , ??總完工時(shí)間 (Makespan)：所有工作處理完成之完工時(shí)間 。 ? ?, , ,m a x 0 ,i s i s i sT C d??延遲作業(yè)數(shù)目 (Number of tardy jobs)： 1niiNT ??? ?生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 710 排程之基本評(píng)估指標(biāo) 2/2 ??? n1is,is Fn1F??? n1i s,isLn1L??? n1i s,isTn1T}L,0m a x {T m a xm a x ?}L{m axL s,ini1m a x ???平均流程時(shí)間 (Average flowtime)： 平均延誤時(shí)間 (Average lateness)： 平均延遲時(shí)間 (Average tardiness)： 最大延誤時(shí)間 (Maximum lateness)： 最大延遲時(shí)間 (Maximum tardiness)： 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 711 單機(jī) (single machine)排程問題 n 件獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè) ， 以使某一績(jī)效評(píng)估指標(biāo)最佳 。 job作業(yè)時(shí)間越小者排越前面，亦可以使平均延誤 (遲 )時(shí)間，平均等候時(shí)間最小化。將作業(yè)時(shí)間除以權(quán)重，所得之值越小者排越前面。交期越早者排越前面，但是此法會(huì)有增加延遲工件數(shù)目和增加平均延遲時(shí)間的傾向。 Hodgson法則 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 712 當(dāng) n個(gè)作業(yè)要排至單一機(jī)臺(tái)上時(shí) ， 利用 SPT (Shortest Process Time) 法則排序可使得平均流程時(shí)間最小化 ， 也就是 。 表 工作作業(yè)時(shí)間表 工作 i 作業(yè)時(shí)間 ti 1 4 2 8 3 7 4 3 5 10 6 12 7 6 8 5 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 714 範(fàn)例 2/3 依 SPT派工法則排序 ， 順序?yàn)?41873256。 表 流程時(shí)間計(jì)算表 工作 i 流程時(shí)間 ti 4 3 1 3+4 8 3+4+5 7 3+4+5+6 3 3+4+5+6+7 2 3+4+5+6+7+8 5 3+4+5+6+7+8+10 6 3+4+5+6+7+8+10+12 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 715 範(fàn)例 3/3 所以平均流程時(shí)間 由上例及圖 ， 工作流程時(shí)間的計(jì)算方式為 除了最小化平均流程時(shí)間以外 ， 在單機(jī)排程問題中 SPT法則亦可以最小化平均延誤時(shí)間 、 最小化平均等候時(shí)間 。 WSPT法則即是將作業(yè)時(shí)間除以權(quán)重 ， 所得之值愈小者表示為愈重要之工作 ， 而將它排至順序的第一位 ， 依此類推 。 EDD法則排序?yàn)榻黄谟缯吲胖劣懊?， 即 ? ? ? ? ? ?12 nd d d? ? ?生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 719 Hodgson法則：求 NT最小， 即最小化延遲工件數(shù)目 以 EDD法則將所有工作排序?yàn)榧?， 並計(jì)算 E集合中所有工作的完工時(shí)間 。 否則進(jìn)入第二步驟 。 Step3 重新計(jì)算集合中所有工作的完工時(shí)間 。否則回到步驟 2。 M a ch i n e 1M a ch i n e 2M a ch i n e 3M a ch i n e iM a ch i n e mn 件工作m 部平行機(jī)臺(tái). . .生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 721 平行機(jī)臺(tái) (parallel machine) 排程問題 2/2 一般平行機(jī)臺(tái)主要可分為二種： Unrelated parallel machine (無(wú)關(guān)聯(lián)平行機(jī)臺(tái) )： ?各機(jī)臺(tái)的加工速度皆不同 ， 且以同一機(jī)臺(tái)來說 ， 不同的工件也會(huì)有不同的加工速度 。 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 722 最小化平均流程時(shí)間 範(fàn)例 Step1:SPT法則 : {6,10,3,7,9,1,8,2,5,4} Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái) 2 1816141210864機(jī)臺(tái) 1機(jī)臺(tái) 2機(jī)臺(tái) 36 48710 9 2513工作 i 1 2 3 4 5 6 7 8 9 10 作業(yè)時(shí)間 ti 5 6 3 8 7 2 3 5 4 2 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 723 降低總完工時(shí)間 範(fàn)例 Step1:LPT法則 : {4,5,2,1,8,9,3,7,6,10} Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái) Step3:依 SPT法則排序機(jī)臺(tái)上工作 2 1816141210864機(jī)臺(tái) 1機(jī)臺(tái) 2機(jī)臺(tái) 36 48792513102 1816141210864機(jī)臺(tái) 1機(jī)臺(tái) 2機(jī)臺(tái) 3648 79251 3 10工作 i 1 2 3 4 5 6 7 8 9 10 作業(yè)時(shí)間 ti 5 6 3 8 7 2 3 5 4 2 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 724 降低最大延遲時(shí)間 Step1:EDD法則 : {6,10,1,7,2,8,5,4,3,9} Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái) 作業(yè)時(shí)間 交期 工作 i 1 5 8 2 6 9 3 3 14 4 8 12 5 7 11 6 2 5 7 3 8 8 5 10 9 4 15 10 2 7 2 1816141210864機(jī)臺(tái) 1機(jī)臺(tái) 2機(jī)臺(tái) 364879251310生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 725 降低延遲工件數(shù)目 在探討單機(jī)排程時(shí) ， 我們發(fā)現(xiàn) Hodgson方法可使延遲件數(shù)最小 ， 現(xiàn)在依此方法應(yīng)用到平行機(jī)臺(tái)排程上 。 步驟 1 針對(duì)每部機(jī)臺(tái)，找出第一個(gè)延遲工作，假設(shè)發(fā)現(xiàn)在機(jī)臺(tái) j的第 i個(gè)順位。 步驟 3 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 726 流線型生產(chǎn)之排程問題 1/3 如何決定 n件工作進(jìn)入系統(tǒng)的處理順序： m部序列機(jī)臺(tái) (m1機(jī)臺(tái)排在 m機(jī)臺(tái)前 )， 每件工作都必須依序通過此 m部機(jī)臺(tái) ， 當(dāng)某工作在一機(jī)臺(tái)之作業(yè)完成後 ， 便依序到下一機(jī)臺(tái)等待處理 。 找出所有工作在兩部機(jī)臺(tái)上之作業(yè)時(shí)間 ti,1和 ti,2兩者中最小者 。假使選出的最小時(shí)間在機(jī)臺(tái) 2(ti,2)， 則將所對(duì)應(yīng)的工作排在順序最後的下一可排空位 ， 繼續(xù)步驟 3。 Step3 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 728 流線型生產(chǎn)之排程問題 3/3 兩部序列機(jī)臺(tái)最小化總完工時(shí)間： Johnson’s rule 結(jié)果 : { , , , , } 1 4 2 5 3 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 729 流線型生產(chǎn)之排程問題範(fàn)例 ─ 1/3 工作 i 機(jī)臺(tái) 1之作業(yè)時(shí)間 機(jī)臺(tái) 2之作業(yè)時(shí)間 1 3 5 2 6 2 3 2 8 4 7 6 5 6 6 6 5 9 7 5 4 8 3 2 9 6 8 10 10 4 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 730 流線型生產(chǎn)之排程問題範(fàn)例 ─ 2/3 工作 i 機(jī)臺(tái) 1之作業(yè)時(shí)間 機(jī)臺(tái) 2之作業(yè)時(shí)間 1 3 5 2 6 2 3 2 8 4 7 6 5 6 6 6 5 9 7 5 4 8 3 2 9 6 8 10 10 4 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程 731 流線型生產(chǎn)之排程問題範(fàn)例 ─ 1/3 最後之順序?yàn)?316