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