制造業(yè)生產(chǎn)作業(yè)計劃華中科技大學管理學院陳榮秋.ppt

第11章 制造業(yè)生產(chǎn)作業(yè)計劃,華中科技大學管理學院 陳榮秋,生產(chǎn)任務的最終落實,MRP確定各車間的零部件投入出產(chǎn)計劃，將全廠性的產(chǎn)品出產(chǎn)計劃變成了各車間的生產(chǎn)任務。 各車間要將車間的生產(chǎn)任務變成各個班組、各個工作地和各個工人的任務，才算落到實處。 將任務安排到工作地，牽涉到任務分配和作業(yè)排序問題,編制作業(yè)計劃要解決的問題,工廠里要對每個工人和工作地安排每天的生產(chǎn)任務，規(guī)定開始時間和完成時間； 醫(yī)院要安排病人手術，為此要安排手術室、配備手術器械、手術醫(yī)師和護士； 學校要安排上課時間表，使學生能按規(guī)定的時間到規(guī)定的教室聽事先安排的教師講課。 項目計劃管理，也是一個作業(yè)計劃問題。 英文Scheduling可以譯成編制作業(yè)計劃或安排日程計劃(時間表)。 編制作業(yè)計劃實質(zhì)上是要將資源分配給不同的任務，按照既定的優(yōu)化目標，確定各種資源利用的時間問題。,有關的名詞術語,排序(Sequencing) 是確定零件在機器上的加工順序。 編制作業(yè)計劃(Scheduling)則不僅包括確定加工順序，而且還包括加工任務的分配和加工每個零件的開始時間和完成時間。 “調(diào)度”是作業(yè)計劃編制后實施生產(chǎn)控制所采取的一切行動，“編制作業(yè)計劃”是加工制造發(fā)生之前的活動?；疖嚂r刻表是作業(yè)計劃?；疖嚂r刻表制定后，對火車運行的安排，包括發(fā)生晚點后的處理，都屬于調(diào)度。,名詞術語(續(xù)),“派工” (Dispatching)是在作業(yè)計劃制定以后，按照作業(yè)計劃的要求，將具體生產(chǎn)任務通過工票或施工單的形式下達到具體的機床和工人，屬于通常所說的“調(diào)度”范圍。 “趕工” (Expediting)是在實際進度已落后于計劃進度時采取的行動，也屬于通常所說的“調(diào)度”范圍。 “機器”，可以是工廠里的各種機床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計算機中央處理單元、存貯器和輸入、輸出單元。表示“服務者”；,名詞術語(續(xù)),“零件”則代表“服務對象”。零件可以是單個零件，也可以是一批相同的零件 “加工路線”是零件加工經(jīng)過不同機器構成的路線。比如，某零件要經(jīng)過車、銑、占、磨的路線加工，我們可以用M1,M2,M3,M4來表示。 “加工順序”則表示每臺機器加工n個零件的先后順序，是排序要解決的問題,4參數(shù)表示法:,n /m /A /B。 其中, n 零件數(shù)； m 機器數(shù)； A 作業(yè)類型；在A的位置若標以“F”，則代表流水作業(yè)排序問題。若標以“P”，則表示流水作業(yè)排列排序問題。若標以“G”，則表示一般單件作業(yè)排序問題。當m1，則A處為空白 B目標函數(shù)，通常是使其值最小。,流水作業(yè)計劃問題,流水線是流水車間(Flow shop) 典型的代表，每個零件的加工路線都一致。 只要加工路線一致：M1， M2, M3，Mm,不要求每個零件都經(jīng)過每臺機器加工,最長流程時間Fmax的計算,最長流程時間又稱作加工周期 6/4/p/ Fmax問題，當按順序S( 6,1,5,2,4,3)加工時，求Fmax.,加工周期為46,n/2/F/Fmax問題的最優(yōu)算法,Johnson算法： 從加工時間矩陣中找出最短的加工時間。 若最短的加工時間出現(xiàn)在M1上，則對應的零件盡可能往前排；若最短加工時間出現(xiàn)在M2上，則對應零件盡可能往后排。然后，從加工時間矩陣中劃去已排序零件的加工時間。若最短加工時間有多個，則任挑一個 若所有零件都已排序，停止。否則，轉(zhuǎn)步驟。,求最優(yōu)順序,算法步驟的改進,把Johnson算法作些改變，改變后的算法按以下步驟進行： 將所有aibi的零件按ai值不減的順序排成一個序列A。 將所有aibi的零件按bi值不增的順序排成一個序列B。 將A放到B之前，就構成了最優(yōu)加工順序,序列A為 (2， 5，6，1)，序列B為(4，3)，構成最優(yōu)順序為 (2，5，6，1， 4，3)，與Johnson算法結果一致。,Johnson法則只是一個充分條件，不是必要條件。不符合這個法則的加工順序，也可能是最優(yōu)順序。如對例11-2順序(2，5，6，4，1，3)不符合Johnson法則，但它也是一個最優(yōu)順序 對于3臺機器的流水車間排序問題，只有幾種特殊類型的問題找到了有效算法。 對于一般的流水車間排列排序問題，可以用分支定界法。,求一般n/m/P/ Fmax問題近優(yōu)解 (Near optimal solution)的啟發(fā)式算法,關鍵零件法 CDS法,關鍵零件法求近優(yōu)解舉例,CDS法,Campbell-Dudek-Smith 三人提出了一個啟發(fā)式算法,簡稱CDS法。他們把Johnson算法用于一般的n/m/P/Fmax問題，得到(1)個加工順序，取其中優(yōu)者,當1時，按Johnson算法得到加工順序(1，2，3，4)； 當2時，得到加工順序(2，3，1，4)。對于順序(2，3，1， 4)，相應的Fmax29。所以，取順序(1，2，3，4)。我們已經(jīng)知道，這就是最優(yōu)順序。,單件作業(yè)排序問題,加工描述矩陣和加工時間矩陣,無延遲作業(yè)計劃(non-delay schedule)的構成,我們稱每安排一道工序稱作一“步”，設 Stt步之前已排序工序構成的部分作業(yè)計劃； Ot 第t步可以排序的工序的集合； Tk Ot 中工序Ok的最早可能開工時間； Tk Ot 中工序Ok的最早可能完工時間。,無延遲作業(yè)計劃的構成步驟:, 設t1，S1為空集，O1為各工件第一道工序的集合。 求T*minTk，并求出T*出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。 從Ot中挑出滿足以下兩個條件的工序Oj：需要機器M*加工，且TjT*。 將確定的工序Oj放入St，從 Ot 中消去Oj，并將Oj的緊后工序放入 Ot ，使tt1。 若還有未安排的工序，轉(zhuǎn)步驟；否則，停止。,優(yōu)先派工法則,在介紹無延遲作業(yè)計劃的構成步驟時，其中第步的兩個條件一般都有多個工序可以滿足。按什么樣的準則來選擇可安排的工序，對作業(yè)計劃的優(yōu)劣有很大影響。為了得到所希望的作業(yè)計劃，人們提出了很多優(yōu)先調(diào)度法則，按優(yōu)先調(diào)度法則挑選工序比隨意挑選一道工序的方法更能符合計劃編制者的要求，同時又不必列出所有可能的作業(yè)計劃，從而計算量小。 迄今，人們已提出了100多個優(yōu)先調(diào)度法則，其中主要的有下8個： SPT(Shortest Processing Time)法則 優(yōu)先選擇加工時間最短的工序。 FCFS(First Come First Served)法則 優(yōu)先選擇最早進入可排工序集合的工件。,優(yōu)先派工法則(續(xù)), EDD(Earliest Due Date)法則 優(yōu)先選擇完工期限緊的工件。 MWKR(Most Work Remaining)法則 優(yōu)先選擇余下加工時間最長的工件。 LWKR(Least Work Remaining)法則 優(yōu)先選擇余下加工時間最短的工件。 MOPNR(Most Operations Remaining)法則 優(yōu)先選擇余下工序數(shù)最多的工件。 SCR(Smallest Critical Ratio)法則 優(yōu)先選擇臨界比最小的工件。臨界比為工件允許停留時間與工件余下加工時間之比。 RANDOM法則 隨機地挑一個工件,隨機抽樣法,用窮舉法或分支定界法求一般單件車間排序問題的最優(yōu)解時，實際上比較了全部能動作業(yè)計劃；采用優(yōu)先調(diào)度法則求近優(yōu)解時，只選擇了一種作業(yè)計劃。 隨機抽樣法介于這兩個極端之間。 它從全部無延遲作業(yè)計劃之中抽樣，得出多個作業(yè)計劃，從中選優(yōu)。 應用隨機抽樣法時，實際上是對同一個問題多次運用RANDOM法則來決定要挑選的工序，從而得到多個作業(yè)計劃。,概率調(diào)度法,隨機抽樣法是從k個可供選擇的工序以等概率方式挑選，每個工序被挑選的概率為1k，這種方法沒有考慮不同工序的特點，有一定盲目性。 例如，在構在無延遲作業(yè)計劃的第步有3道工序