生產(chǎn)計劃與管理課件之作業(yè)排程的基本概念

1、第七章作業(yè)排程前言作業(yè)排程的基本概念作業(yè)排程的特徵與限制單機(jī)排程問題平行機(jī)臺排程問題流線型生產(chǎn)之排程問題零工型生產(chǎn)之排程問題前推與後推排程問題人員排程問題結(jié)語 前言半導(dǎo)體製造工廠 汽車組裝生產(chǎn)線汽車租賃保留(reservation)系統(tǒng)醫(yī)院中的護(hù)士排班問題 系統(tǒng)安裝設(shè)置(installation)專案生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程3作業(yè)排程的基本概念排程是一種資源分配的決策活動。作業(yè)排程(Operations Scheduling)為廣義排程中的一種，若在製造業(yè)中特別是指製造現(xiàn)場機(jī)臺與工件間的安排，以下簡稱排程。在一般工廠內(nèi)常見的排程問題中，處理步驟主要可分為兩部份。決定各工作站

2、的工作負(fù)荷(work loading)決定工作之處理順序(sequencing)生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程4作業(yè)排程的基本概念 1/2將各項工作分配至各工作站，它決定各工作站該負(fù)責(zé)之工作，讓管理者將製令單安排至各工作站，同時兼顧各工作站間目前的產(chǎn)能負(fù)荷情況以及生產(chǎn)線平衡問題，但並未排定各工作站內(nèi)的工作次序。又稱派工(Dispatching)，透過派工法則來決定線上執(zhí)行順序。排程可定義成一種短期計畫，此計畫關(guān)係著製造現(xiàn)場的製令單或擬作業(yè)之工作的作業(yè)順序和時間配置，此定義說明排程是一序列的排序步驟。負(fù)荷安排工作的處理優(yōu)先順序生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程5作業(yè)排程的

3、基本概念 2/2因此，所有工作的作業(yè)先後順序、先天的技術(shù)限制、各個作業(yè)的估計時間和各個作業(yè)所需之資源產(chǎn)能等，都是構(gòu)建細(xì)部排程時需要考慮的因素。生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程6作業(yè)排程的特徵與限制 製造現(xiàn)場生產(chǎn)結(jié)構(gòu)(Shop Structure)評估準(zhǔn)則(Performance Criteria)產(chǎn)品結(jié)構(gòu)(Product Structure)工作中心之產(chǎn)能(Work Center Capacities)生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程7單機(jī)(single machine)排程問題 n個工作的開始時間均為零作業(yè)時間(tj)包含了準(zhǔn)備時間(setup time)，而 且不受

4、排程順序的不同而有所影響作業(yè)時間(tj)事先已知一旦機(jī)器有空馬上處理下一等待的工作上機(jī)的工作未處理完成前，不能中途停止假設(shè)單機(jī)排程是最基本的排程問題，其定義為n件 獨立工作以何順序分派至一部機(jī)臺上作業(yè)， 以使某一績效評估指標(biāo)最佳定義生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程8排程之基本評估指標(biāo) 1/2作業(yè)流程時間(Flowtime)：工作在系統(tǒng)中停留之時間。延誤時間(Lateness)：工作i完工時間與交期之差異?？偼旯r間(Makespan)：所有工作處理完成之完工時間。延遲時間(Tardiness)：工作i完工時間超出交期的時間。延遲作業(yè)數(shù)目(Number of tardy jobs)：

5、生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程9排程之基本評估指標(biāo) 2/2平均流程時間(Average flowtime)：平均延誤時間(Average lateness)：平均延遲時間(Average tardiness)：最大延誤時間(Maximum lateness)：最大延遲時間(Maximum tardiness)：生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程10單機(jī)(single machine)排程問題n 件獨立工作以何順序分派至一部機(jī)臺上作業(yè)，以使某一績效評估指標(biāo)最佳。最小化平均流程時間。job作業(yè)時間越小者排越前面，亦可以使平均延誤(遲)時間，平均等候時間最小化。最短作業(yè)時間法

6、則(SPT)最小化平均加權(quán)流程時間。將作業(yè)時間除以權(quán)重，所得之值越小者排越前面。加權(quán)最短作業(yè)時間法則(WSPT)最大延誤(遲)時間最小化。交期越早者排越前面，但是此法會有增加延遲工件數(shù)目和增加平均延遲時間的傾向。最早交期法則(EDD) 最小化延遲工件數(shù)目。Hodgson法則 生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程11當(dāng)n個作業(yè)要排至單一機(jī)臺上時，利用SPT (Shortest Process Time) 法則排序可使得平均流程時間最小化，也就是。最短作業(yè)時間(SPT)法則最小化平均流程時間()生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程12範(fàn)例 7.1 1/3給予一組工作集如表 7.6，

7、目標(biāo)為最小化平均流程時間。表 7.6 工作作業(yè)時間表工作 i作業(yè)時間 ti142837435106127685生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程13範(fàn)例 7.1 2/3依SPT派工法則排序，順序為4-1-8-7-3-2-5-6。其流程時間計算和表7.7所示。表 7.7 流程時間計算表工作 i流程時間 ti4313+483+4+573+4+5+633+4+5+6+723+4+5+6+7+853+4+5+6+7+8+1063+4+5+6+7+8+10+12生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程14範(fàn)例 7.1 3/3所以平均流程時間由上例及圖7.3觀察，工作流程時間的計算方式為除了

8、最小化平均流程時間以外，在單機(jī)排程問題中SPT法則亦可以最小化平均延誤時間、最小化平均等候時間。 4187325605101520253035404550生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程15加權(quán)最短作業(yè)時間法則 (WSPT)最小化加權(quán)平均流程時間 當(dāng)工作附有重要性之屬性時，排程人員可給予個別之權(quán)重，權(quán)重值愈大表示重要性愈大。WSPT法則即是將作業(yè)時間除以權(quán)重，所得之值愈小者表示為愈重要之工作，而將它排至順序的第一位，依此類推。加權(quán)平均流程時間的計算方式為生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程16最短作業(yè)時間 (SPT) 法則最小化平均延誤時間 () 單機(jī)排程問題之目標(biāo)若為最小

9、化平均延誤時間，SPT法則排序可得最佳解，即 生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程17最早交期法則 (EDD Rule)最小化最大延誤時間 (Lmax)1955年Jackson提出EDD (Early Due Date) 派工法則，其應(yīng)用在最小化最大延誤時間和最大延遲時間，但是會有增加延遲工作數(shù)目和增加平均延遲時間的傾向。EDD法則排序為交期愈早者排至愈前面，即生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程18Hodgson法則：求NT最小，即最小化延遲工件數(shù)目以EDD法則將所有工作排序為集合，並計算E集合中所有工作的完工時間。假使結(jié)果出現(xiàn)沒有或者只有一個延遲工作，則停止，此時已達(dá) 為最

10、小最佳解。否則進(jìn)入第二步驟。Step1在集合中從頭至尾找出第一個延遲作業(yè)，假設(shè)為kStep2檢視前個工作 (包含第個)，將最長作業(yè)時間之工作 移至另一集合中 (開始為空集合)，其中。Step3重新計算集合中所有工作的完工時間。若集合中沒有延遲作業(yè)，則停止，集合的延遲個數(shù)即為最小解。否則回到步驟2。Step4生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程19平行機(jī)臺(parallel machine)排程問題 1/2傳統(tǒng)平行機(jī)臺排程問題就是將n個工作如何安排至m部平行機(jī)臺的問題。生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程20平行機(jī)臺(parallel machine)排程問題 2/2一般平行機(jī)臺

11、主要可分為二種：Unrelated parallel machine (無關(guān)聯(lián)平行機(jī)臺)：各機(jī)臺的加工速度皆不同，且以同一機(jī)臺來說， 不同的工件也會有不同的加工速度。Identical parallel machine (等效平行機(jī)臺)：所有的機(jī)臺對於某一個工件的加工速度均相同。生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程21最小化平均流程時間範(fàn)例 7.6Step1:SPT法則 : 6,10,3,7,9,1,8,2,5,4Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺工作 i12345678910作業(yè)時間ti5638723542生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程22降低總完工時間範(fàn)例 7

12、.7Step1:LPT法則 : 4,5,2,1,8,9,3,7,6,10Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺Step3:依SPT法則排序機(jī)臺上工作工作 i12345678910作業(yè)時間ti5638723542生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程23降低最大延遲時間Step1:EDD法則 : 6,10,1,7,2,8,5,4,3,9Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺作業(yè)時間交期工作i158269331448125711625738851094151027生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程24降低延遲工件數(shù)目在探討單機(jī)排程時，我們發(fā)現(xiàn)Hodgson方法可使延遲件數(shù)最

13、小，現(xiàn)在依此方法應(yīng)用到平行機(jī)臺排程上。利用方法7.5.3指派所有工作。步驟1針對每部機(jī)臺，找出第一個延遲工作，假設(shè)發(fā)現(xiàn)在機(jī)臺j的第i個順位。步驟2檢查並找出在機(jī)臺j前i個順位中作業(yè)時間最長者，將它移至機(jī)臺j的最後順位，修正更改後工作的完成時間並重複步驟2。步驟3生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程25流線型生產(chǎn)之排程問題 1/3如何決定n件工作進(jìn)入系統(tǒng)的處理順序：m部序列機(jī)臺(m-1機(jī)臺排在m機(jī)臺前)，每件工作都必須依序通過此m部機(jī)臺，當(dāng)某工作在一機(jī)臺之作業(yè)完成後，便依序到下一機(jī)臺等待處理。生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程26流線型生產(chǎn)之排程問題 2/3強(qiáng)生法則(Johns

14、ons rule)兩部序列機(jī)臺最小化總完工時間。找出所有工作在兩部機(jī)臺上之作業(yè)時間ti,1和ti,2兩者中最小者。Step1假使選出的最小時間在機(jī)臺1(ti,1)，則將所對應(yīng)的工作排在順序最早的下一可排空位，繼續(xù)步驟3。假使選出的最小時間在機(jī)臺2(ti,2)，則將所對應(yīng)的工作排在順序最後的下一可排空位，繼續(xù)步驟3。Step2將已指派之工作刪除，回至步驟1，直到所有工作排完為止。 Step3生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程27流線型生產(chǎn)之排程問題 3/3兩部序列機(jī)臺最小化總完工時間：Johnsons rule結(jié)果 : , , , , 14253生產(chǎn)計畫與管理 Chapter 7 作業(yè)

15、排程28流線型生產(chǎn)之排程問題範(fàn)例7.10 1/3工作i 機(jī)臺1之作業(yè)時間 機(jī)臺2之作業(yè)時間 13526232847656665975483296810104生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程29流線型生產(chǎn)之排程問題範(fàn)例7.10 2/3 工作i 機(jī)臺1之作業(yè)時間 機(jī)臺2之作業(yè)時間 13526232847656665975483296810104生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程30流線型生產(chǎn)之排程問題範(fàn)例7.10 1/3最後之順序為3-1-6-9-5-4-7-10-8-2生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程31零工型生產(chǎn)之排程問題生產(chǎn)計畫與管理 Chapter 7 作

16、業(yè)排程32零工型生產(chǎn)排程問題零工型生產(chǎn)系統(tǒng)的派工法則 : 隨機(jī)法則, FCFS, EDD, SPT, LSF, LWR,生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程33零工型生產(chǎn)排程問題一般而言，有限產(chǎn)能排程問題主要可分成下列幾種：利用訂單排序法則決定訂單或製令的加工優(yōu)先順序，再按順序高低逐一安排各製令的詳細(xì)作業(yè)排程。以製令為主的排程方法(Job-based Scheduling或Order-based Scheduling)運算邏輯是利用事件導(dǎo)向(Event-Driven)的模擬觀念來描述製造系統(tǒng)的實際運作流程。 以工作中心為主的排程方法(Event-based Scheduling)生產(chǎn)計

17、畫與管理 Chapter 7 作業(yè)排程34派工法則 1/2幾種常用的派工法則：以首先來到等候線的工作為優(yōu)先先進(jìn)先出派工法則(First Come First Served, FCFS)以等候線中工作的最早交期者為優(yōu)先最早交期派工法則(Earliest Due Date, EDD)等候線上的每一等待工作的選擇是具相同機(jī)率。一般此法將作為與其他方法之比較基礎(chǔ)。隨機(jī)法則(Random)以等候線中工作的作業(yè)時間最短者為優(yōu)先。最短作業(yè)時間派工法則(Shortest Processing Time, SPT)生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程35派工法則 2/2以等候線中工作的仍剩餘的加工時間最

18、短者為優(yōu)先。最小剩餘時間派工法則(Least Work Remaining, LWR)寬裕時間是指交期減掉工作還需在機(jī)器上加工完成的時間。以等候線中工作的寬裕時間最短者為優(yōu)先。最小寬裕時間派工法則(Least Slack First, LSF)依照距離到期日剩餘時間對剩餘加工時間比率，最小者為優(yōu)先。關(guān)鍵性比率(Critical Ratio, CR)生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程36範(fàn)例 7-11以製令為主的排程方法 1/3 以EDD法則來決定製令的加工優(yōu)先順序 順序製令交期111023123213451456156418製令作業(yè)順序與時間交期1A(3)B(3) C(2)102A(

19、5)C(2)133B(4)A(4)C(2)124B(3)C(5)A(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程37範(fàn)例 7-11以製令為主的排程方法 2/3順序製令交期111023123213451456156418生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程38範(fàn)例 7-11以製令為主的排程方法 3/3生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程39範(fàn)例 7.12 (EDD)以工作中心為主的排程方法 1/8製令作業(yè)順序與時間交期1A(3)B(3) C(2)102A(5)C(2)133B(4)A(4)C(3)124B(3)C(5)A

20、(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程40範(fàn)例 7.12 (EDD)以工作中心為主的排程方法 2/8若以T來表示時間軸。當(dāng)T=0時，此時機(jī)臺A，B，C均空閒。當(dāng)開始著手於A機(jī)臺的排程時，我們所面對的抉擇是製令1或製令2，何者排在最前？假設(shè)依據(jù)EDD派工法則來進(jìn)行模擬過程，如表分別針對機(jī)臺A，B，C選定該上機(jī)之製令。 機(jī)臺可排之製令派工法則判斷選定之製令作業(yè)時間A1,2D1D213B3,4D3D434C5,6D5D655註：Di 表示製令i 的交期，其中 i=1,2,6. 生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程41範(fàn)例 7.12 派工法則：EDD 3/8製令作業(yè)順序與時間交期1A(3)B(3) C(2)102A(5)C(2)133B(4)A(4)C(3)124B(3)C(5)A(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計畫與管理 Chapter 7 作業(yè)排程42範(fàn)例 7.12 派工法則：SPT 4/8製令作業(yè)順序與時間交期1A(3)B(3) C(2)102A(5)C(2)133B(4)A(4)C(3)124B(3)C(5)A(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計畫與管