【正文】 3 4 pi1 1 2 6 3 pi2 8 4 2 9 pi3 4 5 8 2 pi 13 11 16 14 例 有一個 4/3/F/Fmax問題，其加工時間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。 ? （ 2）對于余下的零件，若 pi1≤p im，則按 pi1不減 的順序排成一個序列 Sa；若 pi1≥p im，則按 pim不增 的順序排成一個序列 Sb。在最優(yōu)順序下， F max =28。 i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 解：對于本例， λ i =－ Pi1＋ Pi3 于是， λ 1 = － P11＋ P13=－ 1＋ 4=3 λ 2 = － P21＋ P23=－ 2＋ 5=3 λ 3 = － P31＋ P33=－ 6＋ 8=2 λ 4 = － P41＋ P43=－ 3＋ 2=－ 1 按 λi 不增的順序排列工件，得到加工順序 (1， 2， 3， 4)和 (2， 1， 3， 4)，恰好這兩個順序都是最優(yōu)順序。 ? 按照各工件 λ i不增 的順序排列工件，可得出令人滿意的順序。 （一） Palmer法 ? 1965年， D． S． Palmer提出按 斜度指標 排列工件的啟發(fā)式算法，稱之為 Palmer法。 ? （ 2）機器 1共需工作多長時間？ ? （ 3）機器 2應該在機器 1開始工作后多長時間開始運轉(zhuǎn)？ 任務 在機器 1上加工所需時間（小時） 在機器 2上加工所需時間（小時） A B C D 0 任務 在機器 1上加工所需時間（小時） 在機器 2上加工所需時間（小時） A B C D 0 B, A, C, D, B, A, C, 機器 1 機器 2 三、一般 n/m/P/Fmax問題的啟發(fā)式算法 ? 啟發(fā)式算法是一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費 (時間、占用空間等 )下給出待解決組合優(yōu)化問題的可行解 。下表給出了兩臺機器上加工各產(chǎn)品所需的時間。 改進算法 工件號 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 工件最優(yōu)順序： 2 5 6 1 4 3 1 3 4 5 5 8 2 7 4 7 4 2 1 4 8 13 18 26 3 11 15 22 26 28 ai bi 最優(yōu)順序下的加工周期為 28 練 習 ? 某公司要生產(chǎn) 4種產(chǎn)品，需要兩臺機器 1和 2。 任務 操作 1所需時間（小時） 操作 2所需時間（小時） A B C D E 任務 操作 1所需時間（小時） 操作 2所需時間（小時） A B C D E A, E, D,3 B,2 C,1 0 操作 1 A, E, D, B, C, 11 操作 2 A, E, D,3 B,2 C,1 0 操作 1 A, E, D, B, C, 11 操作 2 i C B D E A 操作 1 操作 2 1 . . . 111 .【 例 題 】 根據(jù) Johnson算法求以下 8/2/F/Fmax問題的最優(yōu)解。 【 例 】 求如表所示的 6/2/F/Fmax問題的最優(yōu)解。然后從加工時間矩陣中劃去已排序工件的加工時間。 ? （ 2）選擇最短的加工時間，如果有兩個相同的值，則任選一個。 i 1 2 3 4 5 6 4 2 3 1 4 2 4 5 6 7 4 5 5 8 7 5 5 5 4 2 4 3 3 1 1iP2i3iiPi pi1 pi2 pi3 pi4 6 1 5 2 4 3 2 5 5 1 4 4 5 4 4 4 5 3 2 5 8 2 1 7 5 3 3 6 7 4 2 6 10 12 13 16 7 11 15 20 27 33 12 17 22 30 35 42 13 21 25 32 38 46 二、兩臺機器排序問題 ? 兩個或更多的作業(yè)必須在兩臺機器上以相同的工序進行加工，要使加工周期最短，約翰遜于 1954年提出了一個有效算法，那就是著名的 Johnson算法 。 ? 例 有一個 6/4/P/Fmax問題，其加工時間如下表所示。 一、最長流程時間 Fmax的計算 ? n/m/P/Fmax問題， n個零件要按相同的加工路線經(jīng)過 m臺機器加工，目標是使這批零件的最長流程時間最短。 ? 對于流水作業(yè)排序問題，工件在不同機器上的加工順序不盡一致。 第二節(jié) 流水作業(yè)排序問題 ? 流水作業(yè)排序問題的基本特征是每個工件的加工路線都一致。 ? MWKR法則使不同工作量的工件的完工時間盡量接近。 ? FCFS法則來自排隊論，它對工件較公平。用 EDD規(guī)則，可以給顧客提供更好的服務（平均延遲時間較少），它也提供了更低的總庫存水平。 加工周期 機殼加工次序 開始 工作 加工 時間 結(jié)束 工作 流程 時間 預計顧客 取貨時間 顧客實際取貨時間 提前 小時數(shù) 拖延 小時數(shù) 機殼 1 0 8 8 8 10 10 2 機殼 2 8 6 14 14 12 14 2 機殼 4 14 3 17 17 18 18 1 機殼 3 17 15 32 32 20 32 12 機殼 5 32 12 44 44 22 44 22 總數(shù) 115 118 3 36 平均數(shù) 平均在制品庫存 =115/44= 平均總庫存 =118/44= EDD規(guī)則排序結(jié)果 顧客實際取貨時間基于以下假設：顧客不會在預定取貨時間之前來取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時馬上取走。 流程時間 =等待時間 +加工時間 平均在制品庫存 =各工件流程時間之和 247。下表顯示了周一上午的情況，顧客的取貨時間用從周一上午開始，還有多少工作小時來計算。只有一名技工在崗，做此項工作。 ? RANDOM規(guī)則 隨機地挑選下一個工件。 ? LWKR規(guī)則 優(yōu)先選擇余下加工時間最短的工件。臨界比為工作允許停留時間和工件余下加工時間之比。 ? SPT規(guī)則 優(yōu)先選擇加工時間最短的工件。 常用的優(yōu)先順序規(guī)則： ? FCFS規(guī)則 優(yōu)先選擇最早進入可排序集合的工件。 五、優(yōu)先調(diào)度規(guī)則 ? 調(diào)度方法： ? 所謂調(diào)度方法，就是運用若干預先規(guī)定的優(yōu)先順序規(guī)則，順次決定下一個應被加工的工件的排序方法。一個工件正從一個工作地移向另一個，由于一些原因被拖延加工，正在被加工或放置于零件庫中，都可以看作在制品庫存。它是從第一個工件在第一臺機器上開始加工時算起，到最后一個工件在最后一臺機器上完工時為止所經(jīng)過的時間。 ? B為目標函數(shù)，通常是使其值最小 ? 例如： n/3/P/Cmax 四、作業(yè)排序方案的評價標準 ? ? 從工件可以開始加工至完工的時間，包括在各個機器之間的移動時間、等待時間、加工時間以及由于機器故障、部件無法得到等問題引起的延誤時間等。在 A的位置若標以標以“ P” ，則表示 流水作業(yè)排列排序 問題；若標以“ G” ，則表示一般單件作業(yè)排序問題。也就是說，每個零件都順序地經(jīng)過線上不同機器加工，它們的加工路線一致。 ? 、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其他工件。 ? ，即當上一道工序完工后，立即送下道工序加工。 ? “ 機器”，可以是工廠里的各種機床，也可以是維修工人，表示“服務者” ? “零件”代表“服務對象”。 ? 派工：按作業(yè)計劃的要求，將具體生產(chǎn)任務安排到具體的機床上加工。 ? 作業(yè)計劃：不僅要確定工件的加工順序，而且還要確定機器加工每個工件的開始時間和完成時間。醫(yī)院要安排病人手術(shù)，為此要安排手術(shù)室，配備手術(shù)器械、手術(shù)醫(yī)師和護士。 編制作業(yè)計劃要解決的問題 ? 由于每臺機器都可能被分配了多項任務，就帶來了零件在機器上加工的順序問題。 ? 各車間要將車間的生產(chǎn)任務變成各個班組、各個工作地和各個工人的任務。將任務安排到工作地，牽涉到任務分配和作業(yè)排序問題，這正是本章要討論的。第十一章 制造業(yè)作業(yè)計劃與控制 ? 引言 ? 通過 MRP確定各車間的零部件投入出產(chǎn)計劃，從而將全廠性的產(chǎn)品出產(chǎn)計劃變成了各車間生產(chǎn)作業(yè)計劃，將車間的生產(chǎn)任務變成各個班組、各個工作地和各個工人的任務。只有將計劃安排到工作地和工人，任務才算真正落到實處。 ? 作業(yè)計劃問題的基本概念 ? 流水作業(yè)排序問題 ? 單件作業(yè)的排序問題 ? 生產(chǎn)作業(yè)控制 11 收入、費用和利潤 要求掌握： 3種啟發(fā)式算法 4. 相同零件的 3種移動方式下機器加工周期的計算方法 學習目的與要求 重點 最長流程時間的計算 約翰遜算法 相同零件的 3種移動方式下機器加工周期的計算方法 難點 一般流水作業(yè)排序問題的啟發(fā)式算法 教學重點與難點 生產(chǎn)任務的最終落實 ? MRP確定各車間的零部件投入出產(chǎn)計劃，將全廠性的產(chǎn)品出產(chǎn)計劃變成了各車間的生產(chǎn)任務。 ? 將任務安排到工作地，牽涉到作業(yè)計劃。 ? 編制作業(yè)計劃要解決先加工哪個工件、后加工哪個工件的加工順序問題 ? 確定機器加工每個工件的開始時間和完成時間 ? 例如 。 第一節(jié) 排序問題的基本概念 ? 一、名詞術(shù)語 ? 排序：確定工件在機器上的加