生產(chǎn)第十一章_制造業(yè)作業(yè)計(jì)劃及控制

1、第十一章 制造業(yè)作業(yè)計(jì)劃與控制 引言 通過(guò)MRP確定各車(chē)間的零部件投入出產(chǎn)計(jì)劃，從而將全廠性的產(chǎn)品出產(chǎn)計(jì)劃變成了各車(chē)間生產(chǎn)作業(yè)計(jì)劃，將車(chē)間的生產(chǎn)任務(wù)變成各個(gè)班組、各個(gè)工作地和各個(gè)工人的任務(wù)。只有將計(jì)劃安排到工作地和工人，任務(wù)才算真正落到實(shí)處。將任務(wù)安排到工作地，牽涉到任務(wù)分配和作業(yè)排序問(wèn)題，這正是本章要討論的。 11.1 作業(yè)計(jì)劃問(wèn)題的基本概念 11.2 流水作業(yè)排序問(wèn)題 11.3 單件作業(yè)的排序問(wèn)題 11.4 生產(chǎn)作業(yè)控制 11 收入、費(fèi)用和利潤(rùn)收入、費(fèi)用和利潤(rùn)要求掌握： 最長(zhǎng)流程時(shí)間的計(jì)算 2.約翰遜算法 3.一般流水作業(yè)排序問(wèn)題的3種啟發(fā)式算法4. 相同零件的3種移動(dòng)方式下機(jī)器加工周期的

2、計(jì)算方法學(xué)習(xí)目的與要求 重點(diǎn) 最長(zhǎng)流程時(shí)間的計(jì)算 約翰遜算法 相同零件的3種移動(dòng)方式下機(jī)器加工周期的計(jì)算方法 難點(diǎn) 一般流水作業(yè)排序問(wèn)題的啟發(fā)式算法教學(xué)重點(diǎn)與難點(diǎn)生產(chǎn)任務(wù)的最終落實(shí) MRP確定各車(chē)間的零部件投入出產(chǎn)計(jì)劃，將全廠性的產(chǎn)品出產(chǎn)計(jì)劃變成了各車(chē)間的生產(chǎn)任務(wù)。 各車(chē)間要將車(chē)間的生產(chǎn)任務(wù)變成各個(gè)班組、各個(gè)工作地和各個(gè)工人的任務(wù)。 將任務(wù)安排到工作地，牽涉到作業(yè)計(jì)劃。編制作業(yè)計(jì)劃要解決的問(wèn)題 由于每臺(tái)機(jī)器都可能被分配了多項(xiàng)任務(wù)，就帶來(lái)了零件在機(jī)器上加工的順序問(wèn)題。 編制作業(yè)計(jì)劃要解決先加工哪個(gè)工件、后加工哪個(gè)工件的加工順序問(wèn)題 確定機(jī)器加工每個(gè)工件的開(kāi)始時(shí)間和完成時(shí)間 例如;醫(yī)院要安排病人手

3、術(shù)，為此要安排手術(shù)室，配備手術(shù)器械、手術(shù)醫(yī)師和護(hù)士。第一節(jié) 排序問(wèn)題的基本概念 一、名詞術(shù)語(yǔ) 排序：確定工件在機(jī)器上的加工順序。 作業(yè)計(jì)劃：不僅要確定工件的加工順序，而且還要確定機(jī)器加工每個(gè)工件的開(kāi)始時(shí)間和完成時(shí)間。通常情況下都是按最早可能開(kāi)（完）工時(shí)間來(lái)編制作業(yè)計(jì)劃。 派工：按作業(yè)計(jì)劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機(jī)床上加工。 趕工：實(shí)際進(jìn)度已落后于計(jì)劃進(jìn)度時(shí)采取的行動(dòng)。 “機(jī)器”，可以是工廠里的各種機(jī)床，也可以是維修工人，表示“服務(wù)者” “零件”代表“服務(wù)對(duì)象”。零件可以是單個(gè)零件，也可以是一批相同的零件 “加工順序”則表示每臺(tái)機(jī)器加工n個(gè)零件的先后順序，是排序和編制作業(yè)計(jì)劃要解決的問(wèn)

4、題二、假設(shè)條件和符號(hào)說(shuō)明 假設(shè)條件： 1.一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工。 2.工件在加工過(guò)程中采取平行移動(dòng)方式，即當(dāng)上一道工序完工后，立即送下道工序加工。 3.不允許中斷。一個(gè)工件一旦開(kāi)始加工，必須一直進(jìn)行到完工，不得中途停止插入其他工件。 4.每道工序只在一臺(tái)機(jī)器上完成。 5.工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無(wú)關(guān)。 6.每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件有關(guān)符號(hào) Ji：工件i，i=1，2，n Mj：機(jī)器j，j=1，2，n pij為Ji在Mj上的加工時(shí)間 ri為Ji的到達(dá)時(shí)間，指Ji從外部進(jìn)入車(chē)間，可以加工的最早時(shí)間 di為Ji的完工期限 Ci為Ji的完工時(shí)間 Cmax為最

5、長(zhǎng)完工時(shí)間 Fi為Ji的流程時(shí)間，即工件在車(chē)間的實(shí)際停留時(shí)間 Fmax為最長(zhǎng)流程時(shí)間 Li為工件的延遲時(shí)間 Lmax為最長(zhǎng)延遲時(shí)間三、排序問(wèn)題的分類(lèi) 根據(jù)機(jī)器數(shù)的多少單臺(tái)機(jī)器的排序問(wèn)題多臺(tái)機(jī)器的排序問(wèn)題 對(duì)于多臺(tái)機(jī)器排序問(wèn)題，根據(jù)加工路線(xiàn)的特征，分成單件作業(yè)排序(Job - Shop)問(wèn)題流水作業(yè)排序(Flow - Shop)問(wèn)題 工件的加工路線(xiàn)不同，是單件作業(yè)排序問(wèn)題的基本特征； 所有工件的加工路線(xiàn)完全相同，是流水作業(yè)排序問(wèn)題的基本特征。也就是說(shuō)，每個(gè)零件都順序地經(jīng)過(guò)線(xiàn)上不同機(jī)器加工，它們的加工路線(xiàn)一致。 根據(jù)工件到達(dá)系統(tǒng)的情況靜態(tài)排序動(dòng)態(tài)排序 根據(jù)參數(shù)的性質(zhì)確定型排序隨機(jī)型排序4參數(shù)法 n

6、/m/A/B 其中，n為工件數(shù) m為機(jī)器數(shù) A車(chē)間類(lèi)型。在A的位置若標(biāo)以標(biāo)以“P”，則表示流水作業(yè)排列排序問(wèn)題；若標(biāo)以“G”，則表示一般單件作業(yè)排序問(wèn)題。當(dāng)m=1，則A處為空白。 B為目標(biāo)函數(shù)，通常是使其值最小 例如：n/3/P/Cmax四、作業(yè)排序方案的評(píng)價(jià)標(biāo)準(zhǔn) 1.工作流程時(shí)間 從工件可以開(kāi)始加工至完工的時(shí)間，包括在各個(gè)機(jī)器之間的移動(dòng)時(shí)間、等待時(shí)間、加工時(shí)間以及由于機(jī)器故障、部件無(wú)法得到等問(wèn)題引起的延誤時(shí)間等。 2. 加工周期 完成一組工作所需的全部時(shí)間。它是從第一個(gè)工件在第一臺(tái)機(jī)器上開(kāi)始加工時(shí)算起，到最后一個(gè)工件在最后一臺(tái)機(jī)器上完工時(shí)為止所經(jīng)過(guò)的時(shí)間。 3.在制品庫(kù)存（WIP） 在制品是

7、對(duì)介于原材料和成品之間的生產(chǎn)過(guò)程中的產(chǎn)品的稱(chēng)謂。一個(gè)工件正從一個(gè)工作地移向另一個(gè)，由于一些原因被拖延加工，正在被加工或放置于零件庫(kù)中，都可以看作在制品庫(kù)存。 4.利用率 用一臺(tái)機(jī)器或一個(gè)工人的有效生產(chǎn)時(shí)間占總工作時(shí)間的百分比來(lái)表示。五、優(yōu)先調(diào)度規(guī)則 調(diào)度方法： 所謂調(diào)度方法，就是運(yùn)用若干預(yù)先規(guī)定的優(yōu)先順序規(guī)則，順次決定下一個(gè)應(yīng)被加工的工件的排序方法。 一個(gè)工作地可選擇的下一個(gè)工件會(huì)有很多種，因此，按什么樣的準(zhǔn)則來(lái)選擇，對(duì)排序方案的優(yōu)劣有很大影響。常用的優(yōu)先順序規(guī)則： FCFS規(guī)則 優(yōu)先選擇最早進(jìn)入可排序集合的工件。 EDD規(guī)則 優(yōu)先選擇完工期限最緊的工作。 SPT規(guī)則 優(yōu)先選擇加工時(shí)間最短的工

8、件。 SCR規(guī)則 優(yōu)先選擇臨界比最小的工件。臨界比為工作允許停留時(shí)間和工件余下加工時(shí)間之比。 MWKR規(guī)則 優(yōu)先選擇余下加工時(shí)間最長(zhǎng)的工件。 LWKR規(guī)則 優(yōu)先選擇余下加工時(shí)間最短的工件。 MOPNR規(guī)則 優(yōu)先選擇余下工序數(shù)最多的工件。 RANDOM規(guī)則 隨機(jī)地挑選下一個(gè)工件。一般作業(yè)排序的目標(biāo)滿(mǎn)足顧客或下一道工序的交貨期要求流程時(shí)間最短準(zhǔn)備時(shí)間最短或成本最小化在制品庫(kù)存最低機(jī)器設(shè)備或勞動(dòng)力利用最大化 例 一個(gè)加工車(chē)間負(fù)責(zé)加工發(fā)動(dòng)機(jī)機(jī)殼，現(xiàn)在共有5個(gè)機(jī)殼等待加工。只有一名技工在崗，做此項(xiàng)工作?，F(xiàn)在已經(jīng)估算出各個(gè)機(jī)殼的標(biāo)準(zhǔn)加工時(shí)間，顧客也已經(jīng)明確提出了他們所希望的完工時(shí)間。下表顯示了周一上午的情

9、況，顧客的取貨時(shí)間用從周一上午開(kāi)始，還有多少工作小時(shí)來(lái)計(jì)算。SPT規(guī)則排序結(jié)果 顧客實(shí)際取貨時(shí)間基于以下假設(shè)：顧客不會(huì)在預(yù)定取貨時(shí)間之前來(lái)取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時(shí)馬上取走。流程時(shí)間=等待時(shí)間+加工時(shí)間平均在制品庫(kù)存=各工件流程時(shí)間之和加工周期平均總庫(kù)存=各工件實(shí)際取貨時(shí)間之和加工周期EDD規(guī)則排序結(jié)果 顧客實(shí)際取貨時(shí)間基于以下假設(shè)：顧客不會(huì)在預(yù)定取貨時(shí)間之前來(lái)取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時(shí)馬上取走。 比較SPT規(guī)則和EDD規(guī)則的排序結(jié)果，用SPT規(guī)則排序，其平均流程時(shí)間更短，在制品庫(kù)存更少。用EDD規(guī)則，可以給顧客提供更好的服務(wù)（平均延遲時(shí)間較少），它也提供了更低的總

10、庫(kù)存水平。優(yōu)先調(diào)度法則 按SPT法則可使工件的平均流程時(shí)間最短，從而減少在制品量。 FCFS法則來(lái)自排隊(duì)論，它對(duì)工件較公平。 EDD法則可使工件延誤時(shí)間最小。 MWKR法則使不同工作量的工件的完工時(shí)間盡量接近。LWKR法則，使工作量小的工件盡快完成。第二節(jié) 流水作業(yè)排序問(wèn)題 流水作業(yè)排序問(wèn)題的基本特征是每個(gè)工件的加工路線(xiàn)都一致。 加工路線(xiàn)一致，是指工件的流向一致，并不要求每個(gè)工件必須經(jīng)過(guò)加工路線(xiàn)上每臺(tái)機(jī)器加工。 對(duì)于流水作業(yè)排序問(wèn)題，工件在不同機(jī)器上的加工順序不盡一致。 排列排序問(wèn)題：所有工件在各臺(tái)機(jī)器上的加工順序都相同的情況。一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算 n/m/P/Fmax問(wèn)題，n個(gè)零件

11、要按相同的加工路線(xiàn)經(jīng)過(guò)m臺(tái)機(jī)器加工，目標(biāo)是使這批零件的最長(zhǎng)流程時(shí)間最短。 最長(zhǎng)流程時(shí)間又稱(chēng)加工周期，它是從第一個(gè)零件在第一臺(tái)機(jī)器開(kāi)始加工時(shí)算起，到最后一個(gè)零件在最后一臺(tái)機(jī)器上完成加工時(shí)為止所經(jīng)過(guò)的時(shí)間。 例 有一個(gè)6/4/P/Fmax問(wèn)題，其加工時(shí)間如下表所示。當(dāng)按順序S=（6，1，5，2，4，3）加工時(shí)，求Fmax。1iP2iP3iP4iPipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846二、兩臺(tái)機(jī)器排序問(wèn)題 兩個(gè)或更多的作業(yè)必須在兩臺(tái)機(jī)器上以相同的工序進(jìn)行加工，要使

12、加工周期最短，約翰遜于1954年提出了一個(gè)有效算法，那就是著名的Johnson算法。約翰遜算法包括以下幾個(gè)步驟： （1）列出每個(gè)作業(yè)在兩臺(tái)機(jī)器上的加工時(shí)間。 （2）選擇最短的加工時(shí)間，如果有兩個(gè)相同的值，則任選一個(gè)。 （3）如果最短的加工時(shí)間來(lái)自第一臺(tái)機(jī)器，那么先完成這個(gè)作業(yè)；如果來(lái)自第二臺(tái)機(jī)器，那么這個(gè)作業(yè)就放在最后完成。然后從加工時(shí)間矩陣中劃去已排序工件的加工時(shí)間。 （4）對(duì)于剩余的作業(yè)重復(fù)第二步和第三步，直到整個(gè)排序完成。 【例】求如表所示的6/2/F/Fmax問(wèn)題的最優(yōu)解。將零件2排第1位 2將零件3排第6位 2 3將零件5排第2位 2 5 3將零件6排第3位 2 5 6 3將零件4排

13、第5位 2 5 6 4 3將零件1排第4位 2 5 6 1 4 3【例 題】有5件任務(wù)都需要兩步操作（先1后2）來(lái)完成，下表給出了相應(yīng)的時(shí)間：（1）根據(jù)Johnson算法安排工作順序；（2）計(jì)算加工周期。A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2A,3.0E,3.5D,3B,2C,11.03.06.09.512.50操作1A,1.2E,1.5D,3.0B,2.5C,1.62.65.59.01113.7操作2116 . 26 . 132635 . 95 . 35 .120 .

14、 35 . 55 . 20 . 90 . 3115 . 17 .132 . 1【例 題】根據(jù)Johnson算法求以下8/2/F/Fmax問(wèn)題的最優(yōu)解。 1. 將所有ai bi的工件按ai值不減的順序排成一個(gè)序列A； 2. 將aibi的工件按bi值不增的順序排成一個(gè)序列B； 3. 將A放到B之前，就構(gòu)成了一個(gè)最優(yōu)加工順序。改進(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 4 8 13 18 263 11 15 22 26 28 ai bi 最優(yōu)順序下的加工周期為2

15、8練 習(xí) 某公司要生產(chǎn)4種產(chǎn)品，需要兩臺(tái)機(jī)器1和2。其中，有3種產(chǎn)品需要先在機(jī)器1上加工。下表給出了兩臺(tái)機(jī)器上加工各產(chǎn)品所需的時(shí)間。 （1）安排生產(chǎn)順序，使得在最短時(shí)間內(nèi)完成生產(chǎn)。 （2）機(jī)器1共需工作多長(zhǎng)時(shí)間？ （3）機(jī)器2應(yīng)該在機(jī)器1開(kāi)始工作后多長(zhǎng)時(shí)間開(kāi)始運(yùn)轉(zhuǎn)？9.5B,1.25A,2.10C,3.00D,2.1B,2.5A,3.2C,1.71.74.97.44.76.88.65機(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)題的可行解 。 啟發(fā)式方法因其易于實(shí)現(xiàn)、計(jì)算復(fù)雜度低等原因

16、，目前應(yīng)用得最為廣泛。 （一）Palmer法 1965年，DSPalmer提出按斜度指標(biāo)排列工件的啟發(fā)式算法，稱(chēng)之為 Palmer法。 工件的斜度指標(biāo)可按下式計(jì)算： k=l，2，m 式中，m為機(jī)器數(shù)；pik為工件i在Mk上的加工時(shí)間。 按照各工件i不增的順序排列工件，可得出令人滿(mǎn)意的順序。ikmkipmk12/)1(m, 2 , 1k 2/ ) 1(1，mkikipmk31i3miipp時(shí)，當(dāng)43215 . 15 . 05 . 05 . 14miiiiipppp時(shí)，當(dāng)5432121025miiiiiippppp時(shí)，當(dāng)例 有一個(gè)4/3/F/Fmax問(wèn)題，其加工時(shí)間如下表所示，試用帕爾默法求最優(yōu)順

17、序。解：對(duì)于本例， i =Pi1Pi3于是，1 = P11P13=14=3 2 = P21P23=25=3 3 = P31P33=68=2 4 = P41P43=32=1 按i 不增的順序排列工件，得到加工順序(1，2，3，4)和(2，1，3，4)，恰好這兩個(gè)順序都是最優(yōu)順序。如不是這樣，則從中挑選較優(yōu)者。在最優(yōu)順序下， F max =28。321k2/)13(1，ikmkipk（二）關(guān)鍵零件法 步驟如下： （1）計(jì)算每個(gè)零件的總加工時(shí)間，找出加工時(shí)間最長(zhǎng)的零件C，將其作為關(guān)鍵零件。 （2）對(duì)于余下的零件，若pi1pim，則按pi1不減的順序排成一個(gè)序列Sa；若pi1pim，則按pim不增的順

18、序排成一個(gè)序列Sb。 （3）順序（Sa，C，Sb）即為所求順序。例 有一個(gè)4/3/F/Fmax問(wèn)題，其加工時(shí)間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。解：總加工時(shí)間最長(zhǎng)的為3號(hào)零件， pi1pi3的零件為1和2，按pi1不減的順序排成Sa=（1，2）； pi1pi3的零件為4號(hào)零件，Sb=（4）,這樣得到的加工順序?yàn)椋?，2，3，4）。例 題 用關(guān)鍵工件法求解下表的最優(yōu)排序。 解：總加工時(shí)間最長(zhǎng)的為2號(hào)零件，pi1pi4的零件為1和3，按pi1不減的順序排成sa=（1，4）；pi1pi4的零件為4號(hào)零件，sb=（3），這樣得到的順序?yàn)椋?，4，2，3）。（三）CDS法 康坎貝爾-杜德克-史密斯三

19、人提出了一個(gè)啟發(fā)式算法，簡(jiǎn)稱(chēng)CDS法。 具體做法是，對(duì)加工時(shí)間 用Johnson算法求（m-1）次加工順序，取其中最好的結(jié)果。，和1m21pml - 1mkik1lplkik。，和1m21pml - 1mkik1lplkikm=2時(shí)，l=1,加工時(shí)間分別為pi1和pi2；m=3時(shí)，l=1,2,加工時(shí)間分別為：（1）l=1，pi1和pi3（2）l=2,pi1+pi2和pi2+pi3m=4時(shí)，l=1，2，3，加工時(shí)間分別為：（1）l=1,pi1和pi4（2）l=2，pi1+pi2和pi3+pi4（3）l=3，pi1+pi2+pi3和pi2+pi3+pi4lA 加工時(shí)間 B 加工時(shí)間1t1tm2t1

20、+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tm 2)1(pml - 1mkik1，和lplkik當(dāng)l=1時(shí)，按（Johnson）算法得到加工順序（1，2，3，4）；當(dāng)l=2時(shí)，得到加工順序（2，3，1，4）。對(duì)于（2，3，1，4），相應(yīng)的Fmax=29。所以，取順序（1，2，3，4）。用Palmer法、關(guān)鍵工件法和CDS法求以下4/4/P/Fmax問(wèn)題的最優(yōu)解，并比較三種方法的結(jié)果。四、相同零件、不同移動(dòng)方式下加工周期的計(jì)算 排序問(wèn)題針對(duì)的是不同零件，如果n個(gè)零件相同，則沒(méi)有排序問(wèn)題。但零件在加工過(guò)程中采取的移動(dòng)方式不同，會(huì)導(dǎo)致一批

21、零件的加工周期不同。 三種典型的移動(dòng)方式順序移動(dòng)方式(串行工程)平行移動(dòng)方式（平行工程）平行順序移動(dòng)方式（一）順序移動(dòng)方式分鐘52t分鐘153t加工周期時(shí)間工序 1 2 3 4順序移動(dòng)方式順序移動(dòng)方式 一批零件在上道工序全部加工完畢后才整批地轉(zhuǎn)移到下道工序繼續(xù)加工。分鐘101t分鐘104t 設(shè)零件批量為n（件），工序數(shù)目為m，一批零件不計(jì)算工序間運(yùn)輸時(shí)間，只考慮加工時(shí)間，設(shè)其加工的周期為T(mén)（分鐘），零件在i道工序的單件工時(shí)為 ti （分鐘/件），i=1.2n。 則該批零件的加工周期為： 121.mimiTntntntnt 已知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘

22、，則T順=4（10+5+15+10）=160分鐘（二）平行移動(dòng)方式分鐘101t分鐘52t分鐘153t工序 1 2 34時(shí)間 加工周期 每個(gè)零件在前道工序加工完畢后，立即轉(zhuǎn)移到后道工序去繼續(xù)加工，形成前后工序交叉作業(yè)。分鐘104t零件平行移動(dòng)的加工周期 為：T平。為最長(zhǎng)的單件工序時(shí)間式中，平LLitt ) 1n(tT已知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘，則T平=（10+5+15+10）+（4-1）15=85分鐘（三）平行順序移動(dòng)方式 既要求每道工序連續(xù)進(jìn)行加工，又要求各道工序盡可能平行地加工。 時(shí)間工序1234 加工 周期（1）當(dāng)titi+1時(shí)，零件按平行移動(dòng)

23、方式轉(zhuǎn)移；（2）當(dāng)titi+1時(shí)，以i工序最后一個(gè)零件的完工時(shí)間為基準(zhǔn)，往前推移（n-1）ti+1作為零件在（i+1）工序的開(kāi)始時(shí)間。分鐘104t分鐘101t分鐘52t分鐘153t具體做法 （1）當(dāng)titi+1時(shí)，零件按平行移動(dòng)方式轉(zhuǎn)移； （2）當(dāng)titi+1時(shí)，以i工序最后一個(gè)零件的完工時(shí)間為基準(zhǔn)，往前推移（n-1）ti+1作為零件在（i+1）工序的開(kāi)始時(shí)間。平行順序移動(dòng)加工周期計(jì)算已知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘，則T平順=4（10+5+15+10）-（4-1）（5+5+10）=100分鐘)tt (min)1n(tn1j1m1jjm1ii，平順T 例

24、已知n=4，t1=10分鐘，t2=5分鐘，t3=15分鐘，t4=10分鐘。求三種移動(dòng)方式下的加工周期。 解：T順=4（10+5+15+10）=160分鐘 T平=（10+5+15+10）+（4-1）15=85分鐘 T平順=4（10+5+15+10）-（4-1）（5+5+10）=100分鐘零件三種移動(dòng)方式的比較 已知m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分別求在順序移動(dòng)、平行移動(dòng)和平行順序移動(dòng)方式下，這批零件的加工周期。第三節(jié) 單件作業(yè)排序問(wèn)題 11.3.1 指派問(wèn)題 11.3.2 單件作業(yè)排序問(wèn)題的描述 11.3.3 兩種作業(yè)計(jì)劃的構(gòu)成 11.3.4 求解一般n/

25、m/G/Fmax問(wèn)題的啟發(fā)式方法 1 1、指派問(wèn)題的形式表述、指派問(wèn)題的形式表述 給定了一系列所要完成的任務(wù)（給定了一系列所要完成的任務(wù)（taskstasks）以）以及一系列完成任務(wù)的被指派者及一系列完成任務(wù)的被指派者（assigneesassignees），所需要解決的問(wèn)題就是要），所需要解決的問(wèn)題就是要確定出哪一個(gè)人被指派進(jìn)行哪一項(xiàng)任務(wù)確定出哪一個(gè)人被指派進(jìn)行哪一項(xiàng)任務(wù) 2 2、指派問(wèn)題的假設(shè)、指派問(wèn)題的假設(shè)被指派者的數(shù)量和任務(wù)的數(shù)量是被指派者的數(shù)量和任務(wù)的數(shù)量是相同的相同的每一個(gè)被指派者只完成每一個(gè)被指派者只完成一項(xiàng)任務(wù)一項(xiàng)任務(wù) 每一項(xiàng)任務(wù)只能由每一項(xiàng)任務(wù)只能由一一個(gè)被指派者個(gè)被指派者來(lái)

26、完成來(lái)完成 每個(gè)被指派者和每項(xiàng)任務(wù)的組合有一個(gè)相關(guān)成本每個(gè)被指派者和每項(xiàng)任務(wù)的組合有一個(gè)相關(guān)成本 目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小 11.3.1 指派問(wèn)題設(shè)設(shè)n n 個(gè)人被分配去做個(gè)人被分配去做n n 件工作，每人只能完成一項(xiàng)任件工作，每人只能完成一項(xiàng)任務(wù)，每項(xiàng)任務(wù)只能由一人完成。已知第務(wù)，每項(xiàng)任務(wù)只能由一人完成。已知第i i 個(gè)人去做第個(gè)人去做第j j 件工件工作的的效率為作的的效率為C Cijij( (i i=1.2=1.2n n; ;j j=1.2=1.2n n) )并假設(shè)并假設(shè)C Cijij 0 0。問(wèn)應(yīng)。問(wèn)應(yīng)如何分配才能使總效率（如

27、何分配才能使總效率（ 時(shí)間或費(fèi)用）最高？時(shí)間或費(fèi)用）最高？).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij 或3、指派問(wèn)題模型、指派問(wèn)題模型（The Model for Assignment Problem）項(xiàng)任務(wù)個(gè)人取完成第不分配第項(xiàng)任務(wù)個(gè)人取完成第分配第ji0ji1ijx典型問(wèn)題典型問(wèn)題 例例1 1：有一份說(shuō)明書(shū)，要分別譯成英、日、：有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種文字，交與甲、乙、丙、丁四個(gè)德、俄四種文字，交與甲、乙、丙、丁四個(gè)人去完成，因各人專(zhuān)長(zhǎng)不同，他們完成翻譯人去完成，因各人專(zhuān)長(zhǎng)不同，他們完成翻

28、譯不同文字所需要的時(shí)間（小時(shí)）如表所示。不同文字所需要的時(shí)間（小時(shí)）如表所示。規(guī)定每項(xiàng)工作只能交與其中的一個(gè)人完成，規(guī)定每項(xiàng)工作只能交與其中的一個(gè)人完成，每個(gè)人只能完成其中的一項(xiàng)工作。每個(gè)人只能完成其中的一項(xiàng)工作。 問(wèn)：如何分配，能使所需的總時(shí)間最少？問(wèn)：如何分配，能使所需的總時(shí)間最少？甲 乙 丙 丁工作人譯英文譯日文譯德文譯俄文2 10 9 715 4 14 813 14 16 114 15 13 9 建立模型設(shè)設(shè) xij=10若第若第i項(xiàng)工作交與第項(xiàng)工作交與第j個(gè)人完成個(gè)人完成若第若第i項(xiàng)工作不交與第項(xiàng)工作不交與第j個(gè)人完成個(gè)人完成 4141minijijijxcf譯英文：譯英文：x11+

29、 x12 + x13 + x14 =1譯日文：譯日文：x21+ x22 + x23 + x24 =1譯德文：譯德文：x31+ x32 + x33 + x34 =1譯俄文：譯俄文：x41+ x42 + x43 + x44 =1甲：甲：x11+ x21 + x31 + x41 =1乙：乙：x12+ x22 + x32 + x42 =1丙：丙：x13+ x23 + x33 + x43 =1丁：丁：x14+ x24 + x34 + x44 =1xij =0或或1 (i=1,2,3,4; j=1,2,3,4)甲 乙 丙 丁工作人譯英文譯日文譯德文譯俄文2 10 9 715 4 14 813 14 16

30、114 15 13 9 4、指派問(wèn)題的匈牙利解法、指派問(wèn)題的匈牙利解法 9118713161491514410413152 241047501110062111302497第第1 1步：變換指派問(wèn)題的系數(shù)矩陣（步：變換指派問(wèn)題的系數(shù)矩陣（c cijij），使各行），使各行各列中都出現(xiàn)各列中都出現(xiàn)0 0元素元素(1) (1) 從（從（c cijij）的每行元素都減去該行的最小元素；）的每行元素都減去該行的最小元素；(2)(2)再?gòu)乃眯孪禂?shù)矩陣無(wú)零元素的列中減去該列的最小元素。再?gòu)乃眯孪禂?shù)矩陣無(wú)零元素的列中減去該列的最小元素。42 00102350960607130在變化后的效率矩陣中找盡可能

31、多的獨(dú)立在變化后的效率矩陣中找盡可能多的獨(dú)立0 0元素，若元素，若能找出能找出n n個(gè)獨(dú)立個(gè)獨(dú)立0 0元素，就以這元素，就以這n n個(gè)獨(dú)立個(gè)獨(dú)立0 0元素對(duì)應(yīng)解元素對(duì)應(yīng)解矩陣矩陣( (x xijij) )中的元素為中的元素為1 1，其余為，其余為0 0，這就得到最優(yōu)解。，這就得到最優(yōu)解。第第2 2步：進(jìn)行試指派，即確定獨(dú)立零元素步：進(jìn)行試指派，即確定獨(dú)立零元素（1 1）從有唯一的零元素的行或）從有唯一的零元素的行或列開(kāi)始確定獨(dú)立零元素，并用列開(kāi)始確定獨(dú)立零元素，并用 表示，并劃掉其所在行或列的表示，并劃掉其所在行或列的其他零。直到盡可能多的零元其他零。直到盡可能多的零元素都被圈出和劃掉為止。素

32、都被圈出和劃掉為止。0 0（2 2）若）若獨(dú)立零元素獨(dú)立零元素的數(shù)目的數(shù)目m m等等于矩陣的階數(shù)于矩陣的階數(shù)n n，那么這指派，那么這指派問(wèn)題的最優(yōu)解已得到。若問(wèn)題的最優(yōu)解已得到。若m m n n, , 則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。0100000100101000ijx 9118713161491514410413152 00102350960607130例例2 2 有有甲、乙、丙、丁甲、乙、丙、丁四個(gè)工人，要分別派他們完四個(gè)工人，要分別派他們完成四項(xiàng)不同的任務(wù)，分別記作成四項(xiàng)不同的任務(wù)，分別記作A A、B B、C C、D D。他們完成各項(xiàng)。他們完成各項(xiàng)任務(wù)所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，

33、可使總時(shí)間任務(wù)所需時(shí)間如下表所示，問(wèn)如何分派任務(wù)，可使總時(shí)間最少？最少？ 任務(wù)任務(wù)人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982第第1 1步，變換系數(shù)矩陣：步，變換系數(shù)矩陣：2142 289541013895421176)( ijc 0673390245100954 0173340240100454-5第第2 2步，確定獨(dú)立零元素步，確定獨(dú)立零元素 找到找到 3 個(gè)獨(dú)立零元素，個(gè)獨(dú)立零元素， 但但 m = 3 n = 4求解過(guò)程如下求解過(guò)程如下 第第3 3步，作最少的直線(xiàn)覆蓋所有零元素：步，作最少的直線(xiàn)覆蓋所有零元素： (1)(1)對(duì)沒(méi)有獨(dú)立零元素的行打?qū)](méi)有獨(dú)立零元素的

34、行打號(hào)；號(hào)；(2)(2)對(duì)已打?qū)σ汛蛱?hào)的行中所有含劃掉零元素的列打號(hào)的行中所有含劃掉零元素的列打號(hào)；號(hào)；(3)(3)再對(duì)打有再對(duì)打有號(hào)的列中含獨(dú)立零元素的行打號(hào)的列中含獨(dú)立零元素的行打號(hào)；號(hào)；(4)(4)重復(fù)重復(fù)(2)(2)，(3)(3)直到得不出新的打直到得不出新的打號(hào)的行、列為止；號(hào)的行、列為止；(5)(5)對(duì)沒(méi)有打?qū)](méi)有打號(hào)的行畫(huà)橫線(xiàn)，有打號(hào)的行畫(huà)橫線(xiàn)，有打號(hào)的列畫(huà)縱線(xiàn)，號(hào)的列畫(huà)縱線(xiàn)，這就得到覆蓋所有零元素的最少直線(xiàn)數(shù)這就得到覆蓋所有零元素的最少直線(xiàn)數(shù)第第4 4步：在沒(méi)有被直線(xiàn)覆蓋的所有元素中找出最小元素，步：在沒(méi)有被直線(xiàn)覆蓋的所有元素中找出最小元素，然后將所在行然后將所在行（或列）（或

35、列）都減去這最小元素；都減去這最小元素； 017334024010045410623402401013430062440250100343在出現(xiàn)負(fù)數(shù)的列在出現(xiàn)負(fù)數(shù)的列（或行）（或行）都加上這最小元素（以保證都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問(wèn)題仍相同。轉(zhuǎn)回第原問(wèn)題仍相同。轉(zhuǎn)回第2 2步。步。 2142 289541013895421176)( ijc 0673390245100954 0173340240100454-51062340240101343006244025010034301000010000110

36、00ijx11.3.2 問(wèn)題的描述加工描述矩陣D為D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2 對(duì)于一般單件作業(yè)排序問(wèn)題，每個(gè)工件都有其獨(dú)特的加工路線(xiàn)，工件沒(méi)有一定的流向。要描述一道工序，需要用三個(gè)參數(shù)：3個(gè)參數(shù)：i，j和k。i表示工件代號(hào)，j表示工序號(hào)，k表示完成工序i的第j道工序的機(jī)器代號(hào)。（i，j，k）表示工件i的第j道工序在機(jī)器k上進(jìn)行。11.3.3 兩種作業(yè)計(jì)劃的構(gòu)成 各工序都按最早可能完工時(shí)間安排的作業(yè)計(jì)劃稱(chēng)為能動(dòng)作業(yè)計(jì)劃。 各工序都按最早可能開(kāi)始時(shí)間安排的作業(yè)計(jì)劃稱(chēng)為無(wú)延遲作業(yè)計(jì)劃。 無(wú)延遲作業(yè)計(jì)劃是沒(méi)有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃。 符號(hào)說(shuō)明每安排一道

37、工序稱(chēng)為一“步”St:t步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃；Ot:t步可排序工序的集合；Tk為Ot中工序Ok的最早可能開(kāi)始時(shí)間；Tk為Ot中工序Ok的最早可能完成時(shí)間。（一）能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟 （1）設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。 （2）求T* = minTk,并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺(tái)，則任選一臺(tái)。 （3）從Ot中選出滿(mǎn)足以下兩個(gè)條件的工序Oj：需要M*加工，且Tj T* 。 （4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1. （5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。 例 有一個(gè)2/3/G/Fm

38、ax問(wèn)題，其加工描述矩陣D和加工時(shí)間矩陣T分別為：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5試構(gòu)成一個(gè)能動(dòng)作業(yè)計(jì)劃。能動(dòng)作業(yè)計(jì)劃的構(gòu)成2,3,2M2131382,3,261,3,2M28812771,3,22,3,252,2,1M1787731,3,22,2,141,2,3M3777331,2,32,2,132,1,3M3363201,2,32,1,321,1,1M1223001,1,12,1,31OjM*T*TkTkOtt能動(dòng)作業(yè)計(jì)劃的甘特圖2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 7

39、0時(shí)間時(shí)間機(jī)器 M1M2M3（二）無(wú)延遲作業(yè)計(jì)劃構(gòu)成步驟 （1）設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。 （2）求T* = minTk,并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺(tái)，則任選一臺(tái)。 （3）從Ot中選出滿(mǎn)足以下兩個(gè)條件的工序Oj：需要M*加工，且Tj=T* 。 （4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1。 （5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。無(wú)延遲作業(yè)計(jì)劃的構(gòu)成1,3,2M21213121,3,262,3,2M2M277812771,3,22,3,252,2,1M1387731,3,22,2,141,2,3

40、M3M13377331,2,32,2,132,1,3M3063201,2,32,1,321,1,1M1M30023001,1,12,1,31OjM*T*TkTkOtt無(wú)延遲作業(yè)計(jì)劃的甘特圖2,3,21,1,1 2,2,12,1,3 1,2,3 3 7 7 12 13 2 3 70時(shí)間時(shí)間機(jī)器 M1M2M31,3,2 能動(dòng)作業(yè)計(jì)劃和無(wú)延遲作業(yè)計(jì)劃盡管不一定是最優(yōu)作業(yè)計(jì)劃，但一般是較好的作業(yè)計(jì)劃，特別是無(wú)延遲作業(yè)計(jì)劃能提供令人滿(mǎn)意的解。 一般能動(dòng)作業(yè)計(jì)劃和無(wú)延遲作業(yè)計(jì)劃都有多個(gè)。 一般來(lái)說(shuō)，以構(gòu)成無(wú)延遲作業(yè)計(jì)劃的步驟為基礎(chǔ)的啟發(fā)式算法比以構(gòu)成能動(dòng)作業(yè)計(jì)劃的步驟為基礎(chǔ)的啟發(fā)算法的效果要好。練 習(xí) 1

41、.南希汽車(chē)座椅罩和噴漆工廠正在競(jìng)標(biāo)一份為愛(ài)得舊車(chē)交易所提供全部客戶(hù)服務(wù)的合同。取得合同的主要要求是快速交貨。愛(ài)得說(shuō)，如果南希廠可以在24小時(shí)內(nèi)將愛(ài)得收到的5輛車(chē)全部整修并且重新噴漆，合同就歸該廠。下面是這5輛車(chē)在整修和噴漆車(chē)間各自需要的時(shí)間。假定車(chē)子在重新噴漆前要經(jīng)過(guò)重新整修的步驟，南希廠可以滿(mǎn)足時(shí)間要求并且得到合同嗎？ 2.有一個(gè)2/3/G/Fmax問(wèn)題，其加工描述矩陣D和加工時(shí)間矩陣T分別為： 試構(gòu)成一個(gè)能動(dòng)作業(yè)計(jì)劃和無(wú)延遲作業(yè)計(jì)劃。D=1,1,1 1,2,3 1,3,22,1,3 2,2,2 2,3,1T=3 5 22 4 34，1，2M20604，1，20403，1，11182，2，1

42、1251，2，230604，1，20403，1，11182，2，11，1，1M10501，1，120604，1，20403，1，12，1，3M30802，1，30501，1，11OjM*T*T kTkOtt1694，3，11393，2，41292，2，11，2，2M261361，2，264，2，4M46864，2，41393，2，41292，2，161361，2，25864，2，43，1，1M15953，1，11182，2，11361，2，24OjM*T*T kTkOtt4，3，1M11219124，3，118133，3，317132，3，419131，3，3919124，3，13，2，4M4

43、91393，2，416122，3，419131，3，3891694，3，191393，2，42，2，1M191292，2，119131，3，37OjM*T*T kTkOtt22194，4，31819183，4，21827182，4，31，3，3M31824181，3，31222194，4，33，3，3M31318133，3，326172，4，31319131，3，31122194，4，31318133，3，32，3，4M41317132，3，41319131，3，310OjM*T*T kTkOtt2，4，3M32736272，4，34，4，3M32427244，4，32433242，4，324

44、27244，4，32433242，4，31，4，4M42426241，4，41427244，4，33，4，2M21819183，4，233242，4，326241，4，413OjM*T*T kTkOtt151611.3.3 求解一般n/m/G/Fmax問(wèn)題的啟發(fā)式方法三類(lèi)啟發(fā)式算法：n 優(yōu)先調(diào)度法則n 隨機(jī)抽樣法n 概率調(diào)度法1.優(yōu)先調(diào)度法則 SPT（Shortest processing time）法則 優(yōu)先選擇加工時(shí)間最短的工序 可使工件的平均流程時(shí)間最短，從而減少在制品量 FCFS（First come first served）法則 優(yōu)先選擇最早進(jìn)入可排工序集合的工件 來(lái)自排隊(duì)論，對(duì)工件較公平 EDD（Earliest due date）法則 優(yōu)先選擇完工期限緊的工件 可使工件最大延誤時(shí)間最小 MWKR（Most work remaining）法則 優(yōu)先選擇余下加工時(shí)間最長(zhǎng)的工件 不同工作量的工