制造業(yè)作業(yè)計劃與控制課件

第八章制造業(yè)作業(yè)計劃與控制2021/4/91第八章制造業(yè)作業(yè)計劃與控制2021/4/91生產(chǎn)任務(wù)的最終落實MRP確定各車間的零部件投入出產(chǎn)計劃，將全廠性的產(chǎn)品出產(chǎn)計劃變成了各車間的生產(chǎn)任務(wù)。各車間要將車間的生產(chǎn)任務(wù)變成各個班組、各個工作地和各個工人的任務(wù)。將任務(wù)安排到工作地，牽涉到作業(yè)計劃。生產(chǎn)作業(yè)計劃是安排零部件（作業(yè)、活動）的產(chǎn)出數(shù)量、設(shè)備以及人工使用、投入時間及產(chǎn)出時間。2021/4/92生產(chǎn)任務(wù)的最終落實MRP確定各車間的零部件投入出產(chǎn)計劃，將全編制作業(yè)計劃要解決的問題由于每臺機器都可能被分配了多項任務(wù)，就帶來了零件在機器上加工的順序問題。編制作業(yè)計劃要解決先加工哪個工件、后加工哪個工件的加工順序問題確定機器加工每個工件的開始時間和完成時間2021/4/93編制作業(yè)計劃要解決的問題由于每臺機器都可能被分配了多項任務(wù)，第一節(jié)排序問題的基本概念一、名詞術(shù)語排序：確定工件在機器上的加工順序。作業(yè)計劃：不僅要確定工件的加工順序，而且還要確定機器加工每個工件的開始時間和完成時間。通常情況下都是按最早可能開（完）工時間來編制作業(yè)計劃。派工：按作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機床上加工。趕工：實際進度已落后于計劃進度時采取的行動。2021/4/94第一節(jié)排序問題的基本概念一、名詞術(shù)語2021/4/94“機器”，可以是工廠里的各種機床，也可以是維修工人，表示“服務(wù)者”“零件”代表“服務(wù)對象”。零件可以是單個零件，也可以是一批相同的零件“加工順序”則表示每臺機器加工n個零件的先后順序，是排序和編制作業(yè)計劃要解決的問題2021/4/95“機器”，可以是工廠里的各種機床，也可以是維修工人，表示“服二、假設(shè)條件和符號說明假設(shè)條件：1.一個工件不能同時在幾臺不同的機器上加工。2.工件在加工過程中采取平行移動方式，即當(dāng)上一道工序完工后，立即送下道工序加工。3.不允許中斷。一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其他工件。4.每道工序只在一臺機器上完成。5.工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。6.每臺機器同時只能加工一個工件2021/4/96二、假設(shè)條件和符號說明假設(shè)條件：2021/4/96有關(guān)符號Ji：工件i，i=1，2，…，nMj：機器j，j=1，2，…，npij為Ji在Mj上的加工時間ri為Ji的到達時間，指Ji從外部進入車間，可以加工的最早時間di為Ji的完工期限Ci為Ji的完工時間Cmax為最長完工時間Fi為Ji的流程時間，即工件在車間的實際停留時間Fmax為最長流程時間Li為工件的延遲時間Lmax為最長延遲時間2021/4/97有關(guān)符號Ji：工件i，i=1，2，…，n2021/4/97三、排序問題的分類根據(jù)機器數(shù)的多少單臺機器的排序問題多臺機器的排序問題對于多臺機器排序問題，根據(jù)加工路線的特征，分成單件作業(yè)排序(Job-Shop)問題流水作業(yè)排序(Flow-Shop)問題工件的加工路線不同，是單件作業(yè)排序問題的基本特征；所有工件的加工路線完全相同，是流水作業(yè)排序問題的基本特征。也就是說，每個零件都順序地經(jīng)過線上不同機器加工，它們的加工路線一致。2021/4/98三、排序問題的分類根據(jù)機器數(shù)的多少2021/4/98根據(jù)工件到達系統(tǒng)的情況靜態(tài)排序動態(tài)排序根據(jù)參數(shù)的性質(zhì)確定型排序隨機型排序根據(jù)目標(biāo)函數(shù)的情況單目標(biāo)排序多目標(biāo)排序2021/4/99根據(jù)工件到達系統(tǒng)的情況2021/4/99四參數(shù)法n/m/A/B其中，n為工件數(shù)m為機器數(shù)A車間類型。在A的位置若標(biāo)以“F”，則代表流水作業(yè)排序問題；若標(biāo)以“P”，則表示流水作業(yè)排列排序問題；若標(biāo)以“G”，則表示一般單件作業(yè)排序問題。當(dāng)m=1，則A處為空白。B為目標(biāo)函數(shù)，通常是使其值最小2021/4/910四參數(shù)法n/m/A/B2021/4/910四、甘特圖作業(yè)排序中最常用的一種工具，最早由亨利.甘特于1917年提出。兩種基本形式的甘特圖：作業(yè)進度圖和機器圖。作業(yè)進度圖表示一項工作的計劃開始日期、計劃完成日期以及現(xiàn)在的進度。

2021/4/911四、甘特圖作業(yè)排序中最常用的一種工具，最早由亨利.甘特于19例如，假設(shè)一個汽車零件制造公司有三項工作在進行中，它們分別是加工三種汽車零件A、B、C。這些工作的預(yù)定計劃和現(xiàn)在的完成情況如圖所示：2021/4/912例如，假設(shè)一個汽車零件制造公司有三項工作在進行中，它們分別是如果這三項工作都在等待進行磨削加工，之后他們要進行拋光才能最后交貨，則下圖表示了三種工作在兩種不同設(shè)備上的所需時間、時間安排和現(xiàn)在的進度。這種形式的甘特圖就稱為機器圖，它描述不同工作在每一臺機器上的工作次序，也可被用來管理生產(chǎn)進度。2021/4/913如果這三項工作都在等待進行磨削加工，之后他們要進行拋光才能最五、作業(yè)排序方案的評價標(biāo)準(zhǔn)1.工作流程時間從工件可以開始加工至完工的時間，包括在各個機器之間的移動時間、等待時間、加工時間以及由于機器故障、部件無法得到等問題引起的延誤時間等。2.加工周期完成一組工作所需的全部時間。它是從第一個工件在第一臺機器上開始加工時算起，到最后一個工件在最后一臺機器上完工時為止所經(jīng)過的時間。2021/4/914五、作業(yè)排序方案的評價標(biāo)準(zhǔn)1.工作流程時間2021/4/913.在制品庫存（WIP）在制品是對介于原材料和成品之間的生產(chǎn)過程中的產(chǎn)品的稱謂。一個工件正從一個工作地移向另一個，由于一些原因被拖延加工，正在被加工或放置于零件庫中，都可以看作在制品庫存。4.利用率用一臺機器或一個工人的有效生產(chǎn)時間占總工作時間的百分比來表示。2021/4/9153.在制品庫存（WIP）2021/4/915六、優(yōu)先調(diào)度規(guī)則調(diào)度方法：所謂調(diào)度方法，就是運用若干預(yù)先規(guī)定的優(yōu)先順序規(guī)則，順次決定下一個應(yīng)被加工的工件的排序方法。一個工作地可選擇的下一個工件會有很多種，因此，按什么樣的準(zhǔn)則來選擇，對排序方案的優(yōu)劣有很大影響。2021/4/916六、優(yōu)先調(diào)度規(guī)則調(diào)度方法：2021/4/916常用的優(yōu)先順序規(guī)則：FCFS規(guī)則（先到先服務(wù)）按訂單送到的先后順序進行加工。EDD規(guī)則優(yōu)先選擇完工期限最緊的工作。SPT規(guī)則（最短加工時間）優(yōu)先選擇加工時間最短的工件。STR規(guī)則（剩余松弛時間）優(yōu)先選擇STR最短的工件。STR為交貨前所剩余的時間與剩余的加工時間之差。MWKR規(guī)則優(yōu)先選擇余下加工時間最長的工件。LWKR規(guī)則優(yōu)先選擇余下加工時間最短的工件。MOPNR規(guī)則優(yōu)先選擇余下工序數(shù)最多的工件。RANDOM規(guī)則隨機地挑選下一個工件。。。。。。。2021/4/917常用的優(yōu)先順序規(guī)則：FCFS規(guī)則（先到先服務(wù)）按訂單送到的一般作業(yè)排序的目標(biāo)滿足顧客或下一道工序的交貨期要求流程時間最短準(zhǔn)備時間最短或成本最小化在制品庫存最低機器設(shè)備或勞動力利用最大化2021/4/918一般作業(yè)排序的目標(biāo)2021/4/918[例]

一個加工車間負(fù)責(zé)加工發(fā)動機機殼，現(xiàn)在共有5個機殼等待加工。只有一名技工在崗，做此項工作?，F(xiàn)在已經(jīng)估算出各個機殼的標(biāo)準(zhǔn)加工時間，顧客也已經(jīng)明確提出了他們所希望的完工時間。下表顯示了周一上午的情況，顧客的取貨時間用從周一上午開始，還有多少工作小時來計算。發(fā)動機機殼所需標(biāo)準(zhǔn)加工時間（包括機器調(diào)整）預(yù)計顧客取貨時間（從現(xiàn)在開始算起的所需工作時間）機殼1810機殼2612機殼31520機殼4318機殼512222021/4/919[例]一個加工車間負(fù)責(zé)加工發(fā)動機機殼，現(xiàn)在共有5個機殼等待機殼加工次序開始工作加工時間結(jié)束工作流程時間預(yù)計顧客取貨時間顧客實際取貨時間提前小時數(shù)拖延小時數(shù)機殼40333181815機殼2369912123機殼198171710177機殼51712292922297機殼329154444204424總數(shù)1021201838平均數(shù)20.43.67.6平均在制品庫存=102/44=2.32個平均總庫存=120/44=2.73個SPT規(guī)則排序結(jié)果

顧客實際取貨時間基于以下假設(shè)：顧客不會在預(yù)定取貨時間之前來取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時馬上取走。流程時間=等待時間+加工時間平均在制品庫存=各工件流程時間之和÷加工周期平均總庫存=各工件實際取貨時間之和÷加工周期2021/4/920機殼加工次序開始加工結(jié)束流程預(yù)計顧客顧客實際取貨時間提前拖延機殼加工次序開始工作加工時間結(jié)束工作流程時間預(yù)計顧客取貨時間顧客實際取貨時間提前小時數(shù)拖延小時數(shù)機殼1088810102機殼286141412142機殼4143171718181機殼317153232203212機殼532124444224422總數(shù)115118336平均數(shù)23.00.67.2平均在制品庫存=115/44=2.61個平均總庫存=118/44=2.68個EDD規(guī)則排序結(jié)果

顧客實際取貨時間基于以下假設(shè)：顧客不會在預(yù)定取貨時間之前來取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時馬上取走。

比較SPT規(guī)則和EDD規(guī)則的排序結(jié)果，用SPT規(guī)則排序，其平均流程時間更短，在制品庫存更少。用EDD規(guī)則，可以給顧客提供更好的服務(wù)（平均延遲時間較少），它也提供了更低的總庫存水平。2021/4/921機殼加工次序開始加工結(jié)束流程預(yù)計顧客顧客實際取貨時間提前拖延例題作業(yè)（按到達順序）加工時間/天交貨日期（從現(xiàn)在起天數(shù)）A35B46C27D69E12優(yōu)先調(diào)度準(zhǔn)則：FCFS、SOT、EDD、LCFS、STR2021/4/922例題作業(yè)（按到達順序）加工時間/天交貨日期（從現(xiàn)在起天數(shù)）A優(yōu)先調(diào)度法則按SPT法則可使工件的平均流程時間最短，從而減少在制品量。FCFS法則來自排隊論，它對工件較公平。EDD法則可使工件延誤時間最小。MWKR法則使不同工作量的工件的完工時間盡量接近。LWKR法則，使工作量小的工件盡快完成。2021/4/923優(yōu)先調(diào)度法則按SPT法則可使工件的平均流程時間最短，從而減少第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件的加工路線都一致。加工路線一致，是指工件的流向一致，并不要求每個工件必須經(jīng)過加工路線上每臺機器加工。對于流水作業(yè)排序問題，工件在不同機器上的加工順序不盡一致。排列排序問題：所有工件在各臺機器上的加工順序都相同的情況。2021/4/924第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件一、最長流程時間Fmax的計算n/m/P/Fmax問題，n個零件要按相同的加工路線經(jīng)過m臺機器加工，目標(biāo)是使這批零件的最長流程時間最短。最長流程時間又稱加工周期，它是從第一個零件在第一臺機器開始加工時算起，到最后一個零件在最后一臺機器上完成加工時為止所經(jīng)過的時間。2021/4/925一、最長流程時間Fmax的計算n/m/P/Fmax問題，n個例有一個6/4/P/Fmax問題，其加工時間如下表所示。當(dāng)按順序S=（6，1，5，2，4，3）加工時，求Fmax。i1234564231424567455875554243312021/4/926例有一個6/4/P/Fmax問題，其加工時間如下表所示。當(dāng)ipi1pi2pi3pi46152432551445444532582175336742610121316711152027331217223035421321253238462021/4/927ipi1pi2pi3pi461524325514454445二、兩臺機器排序問題兩個或更多的作業(yè)必須在兩臺機器上以相同的工序進行加工，要使加工周期最短，約翰遜于1954年提出了一個有效算法，那就是著名的Johnson算法。約翰遜算法包括以下幾個步驟：（1）列出每個作業(yè)在兩臺機器上的加工時間。（2）選擇最短的加工時間，如果有兩個相同的值，則任選一個。（3）如果最短的加工時間來自第一臺機器，那么先完成這個作業(yè)；如果來自第二臺機器，那么這個作業(yè)就放在最后完成。然后從加工時間矩陣中劃去已排序工件的加工時間。（4）對于剩余的作業(yè)重復(fù)第二步和第三步，直到整個排序完成。2021/4/928二、兩臺機器排序問題兩個或更多的作業(yè)必須在兩臺機器上以相同的【例】求如表所示的6/2/F/Fmax問題的最優(yōu)解。i123456ai518534bi722474.5將零件2排第1位2將零件3排第6位23將零件5排第2位253將零件6排第3位2563將零件4排第5位25643將零件1排第4位2561432021/4/929【例】求如表所示的6/2/F/Fmax問題的最優(yōu)解。i123【例題】有5件任務(wù)都需要兩步操作（先1后2）來完成，下表給出了相應(yīng)的時間：（1）根據(jù)Johnson算法安排工作順序；（2）計算加工周期。任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.52021/4/930【例題】有5件任務(wù)都需要兩步操作（先1后2）來完成，下表任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5A,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操作22021/4/931任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.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操作2iCBDEA操作1操作22021/4/932A,3.0E,3.5D,3B,2C,11.03.06.09.1.將所有ai≤

bi的工件按ai值不減的順序排成一個序列A；2.將ai＞bi的工件按bi值不增的順序排成一個序列B；3.將A放到B之前，就構(gòu)成了一個最優(yōu)加工順序。改進算法2021/4/9331.將所有ai≤bi的工件按ai值不減的順序排成一個序工件號123456ai518534bi722474工件最優(yōu)順序：256143

1345582747424

8

13

18

2631115222628aibi

最優(yōu)順序下的加工周期為282021/4/934工件號123練習(xí)某公司要生產(chǎn)4種產(chǎn)品，需要兩臺機器1和2。其中，有3種產(chǎn)品需要先在機器1上加工。下表給出了兩臺機器上加工各產(chǎn)品所需的時間。（1）安排生產(chǎn)順序，使得在最短時間內(nèi)完成生產(chǎn)。（2）機器1共需工作多長時間？（3）機器2應(yīng)該在機器1開始工作后多長時間開始運轉(zhuǎn)？任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.102021/4/935練習(xí)某公司要生產(chǎn)4種產(chǎn)品，需要兩臺機器1和2。其中，有3任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.109.5B,1.25A,2.10C,3.00D,2.1B,2.5A,3.2C,1.71.74.97.44.76.88.65機器1機器22021/4/936任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小三、一般n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法是一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費(時間、占用空間等)下給出待解決組合優(yōu)化問題的可行解。啟發(fā)式方法因其易于實現(xiàn)、計算復(fù)雜度低等原因，目前應(yīng)用得最為廣泛。2021/4/937三、一般n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法是一個（一）Palmer法1965年，D．S．Palmer提出按斜度指標(biāo)排列工件的啟發(fā)式算法，稱之為Palmer法。工件的斜度指標(biāo)可按下式計算：

k=l，2，…，m式中，m為機器數(shù)；pik為工件i在Mk上的加工時間。按照各工件λi不增的順序排列工件，可得出令人滿意的順序。2021/4/938（一）Palmer法1965年，D．S．Palmer提出按斜2021/4/9392021/4/939例有一個4/3/F/Fmax問題，其加工時間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。i1234Pi11263Pi28429Pi34582解：對于本例，

λ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)順序。如不是這樣，則從中挑選較優(yōu)者。在最優(yōu)順序下，F(xiàn)max=28。2021/4/940例有一個4/3/F/Fmax問題，其加工時間如下表所示，試（二）關(guān)鍵零件法步驟如下：（1）計算每個零件的總加工時間，找出加工時間最長的零件C，將其作為關(guān)鍵零件。（2）對于余下的零件，若pi1≤pim，則按pi1不減的順序排成一個序列Sa；若pi1≥pim，則按pim不增的順序排成一個序列Sb。（3）順序（Sa，C，Sb）即為所求順序。2021/4/941（二）關(guān)鍵零件法步驟如下：2021/4/941i1234pi11263pi28429pi34582pi13111614例有一個4/3/F/Fmax問題，其加工時間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。解：總加工時間最長的為3號零件，pi1≤pi3的零件為1和2，按pi1不減的順序排成Sa=（1，2）；pi1≥pi3的零件為4號零件，Sb=（4）,這樣得到的加工順序為（1，2，3，4）。2021/4/942i1234pi11263pi28429pi34582pi13例題用關(guān)鍵工件法求解下表的最優(yōu)排序。解：總加工時間最長的為2號零件，pi1≤pi2的零件為1和3，按pi1不減的順序排成sa=（1，3）；pi1＞pi2的零件為4號零件，sb=（4），這樣得到的順序為（1，3，2，4）。i1234pi11954pi25763pi34635pi46237i1234pi11954pi25763pi34635pi46237pi162417192021/4/943例題用關(guān)鍵工件法求解下表的最優(yōu)排序。i1234pi119單件作業(yè)排序問題2021/4/944單件作業(yè)排序問題2021/4/944一、問題的描述加工描述矩陣D為D=1,1,11,2,31,3,22,1,32,2,12,3,2

對于一般單件作業(yè)排序問題，每個工件都有其獨特的加工路線，工件沒有一定的流向。要描述一道工序，需要用三個參數(shù)：3個參數(shù)：i，j和k。i表示工件代號，j表示工序號，k表示完成工序i的第j道工序的機器代號。（i，j，k）表示工件i的第j道工序在機器k上進行。2021/4/945一、問題的描述加工描述矩陣D為D=1,1,11,2,3二、兩種作業(yè)計劃的構(gòu)成各工序都按最早可能完工時間安排的作業(yè)計劃稱為能動作業(yè)計劃。各工序都按最早可能開始時間安排的作業(yè)計劃稱為無延遲作業(yè)計劃。無延遲作業(yè)計劃是沒有任何延遲出現(xiàn)的能動作業(yè)計劃。2021/4/946二、兩種作業(yè)計劃的構(gòu)成各工序都按最早可能完工時間安排的作業(yè)計2兩種單件作業(yè)排序方法例：加工描述矩陣和加工時間矩陣如下，分別按下列兩種方法進行作業(yè)排序．

(1)最小最早完工時間法（能動作業(yè)計劃）(2)最小最早開工時間法（無延遲作業(yè)計劃）1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝2021/4/9472兩種單件作業(yè)排序方法(1)最小最早完工時間法（能動作業(yè)(l)最小最早完工時間法

1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝序列可排事件最早可能開工時間最早可能完工時間最小最早可能完工時間所需機器排定事件1234561,3,2M2141412

1,3,22,3,2M29912781,3,22,3,22,2,1M1898731,3,22,2,11,2,3M3778331,2,32,2,12,1,3M3363201,2,32,1,31,1,1M1223001,1,12,1,32021/4/948(l)最小最早完工時間法1,1,11,2,3按此方法編制出的作業(yè)計劃叫做：能動作業(yè)計劃

1,1,11,2,31,3,22,1,32,2,12,3,2D＝

242354T＝排定事件1,1,12,1,31,2,32,2,12,3,21,3,2時間機器機器1機器2機器31,1,12,1,31,2,32,2,12,3,21,3,20032378121482021/4/949按此方法編制出的作業(yè)計劃叫做：能動作業(yè)計劃1,1,1(2)最小最早開工時間法

1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝序列可排事件最早可能開工時間最早可能完工時間最小最早可能開工時間所需機器排定事件1234562,3,2M29139

2,3,21,3,2M27912781,3,22,3,22,2,1M1398731,3,22,2,11,2,3M3M13378331,2,32,2,12,1,3M3063201,2,32,1,31,1,1M1M30023001,1,12,1,32021/4/950(2)最小最早開工時間法1,1,11,2,3時間機器機器1機器2機器3

1,1,11,2,31,3,22,1,32,2,12,3,2D＝

242354T＝排定事件1,1,12,1,31,2,32,2,11,3,22,3,2按此方法編制出的作業(yè)計劃叫做：無延遲作業(yè)計劃

1,1,12,1,31,2,32,2,12,3,21,3,2003237891372021/4/951時間機器機器1機器2機器31,1,11,2,3能動作業(yè)計劃和無延遲作業(yè)計劃盡管不一定是最優(yōu)作業(yè)計劃，但一般是較好的作業(yè)計劃，特別是無延遲作業(yè)計劃能提供令人滿意的解。一般能動作業(yè)計劃和無延遲作業(yè)計劃都有多個。一般來說，以構(gòu)成無延遲作業(yè)計劃的步驟為基礎(chǔ)的啟發(fā)式算法比以構(gòu)成能動作業(yè)計劃的步驟為基礎(chǔ)的啟發(fā)算法的效果要好。2021/4/952能動作業(yè)計劃和無延遲作業(yè)計劃盡管不一定是最優(yōu)作業(yè)計劃，但一般生產(chǎn)作業(yè)控制一、實行生產(chǎn)作業(yè)控制的原因和條件1、原因：1）加工時間估計不準(zhǔn)確2）隨機因素的影響3）加工路線的多樣性4）企業(yè)環(huán)境的動態(tài)性2、實施生產(chǎn)控制的三個條件：1）要有一個標(biāo)準(zhǔn)2）要取得實際生產(chǎn)進度與計劃偏離的信息3）要能采取糾正偏差的行動。2021/4/953生產(chǎn)作業(yè)控制一、實行生產(chǎn)作業(yè)控制的原因和條件2021/4/9二、生產(chǎn)作業(yè)控制工具1、廿特圖有兩種形式的廿特圖：作業(yè)進度圖和機器圖工作4/174/184/194/204/214/224/234/244/254/26ABC作業(yè)進度圖2021/4/954二、生產(chǎn)作業(yè)控制工具1、廿特圖工作4/4/4/4/4/4/4機器圖機器4/224/234/244/254/264/274/284/29磨床剖光機ABACBC2021/4/955機器圖機器4/224/234/244/254/264/274二、日常調(diào)度單它告訴主管哪些工件要被加工，這些工件的優(yōu)先級以及加工時間。開始日期工件號描述運行時間201203205205207208151311514315145157121534015312軸鉚釘錠子錠子測量桿軸11.420.64.38.66.54.62021/4/956二、日常調(diào)度單它告訴主管哪些工件要被加工，這些工件的優(yōu)先級以三、各種狀態(tài)和異常報告1、預(yù)計延期報告2、廢品報告3、返工報告4、作業(yè)總結(jié)報告部件號計劃日期新日期延期原因措施1712513044176534/104/114/114/155/15/14夾具損壞送去鍍金，鍍金工罷工新孔未成直線工具室返還4/15新批量開始生產(chǎn)工程部重新安裝鉆模2021/4/957三、各種狀態(tài)和異常報告1、預(yù)計延期報告部件號計劃日期新日期延2022/11/5作業(yè)計劃于排序58生產(chǎn)作業(yè)計劃的主要決策問題確定批量的大小確定適當(dāng)?shù)纳a(chǎn)順序安排合理的生產(chǎn)進度日程2021/4/9582022/11/1作業(yè)計劃于排序58生產(chǎn)作業(yè)計劃的主要決策問例題作業(yè)（按到達順序）加工時間/天交貨日期（從現(xiàn)在起天數(shù)）A35B46C27D69E12優(yōu)先調(diào)度準(zhǔn)則：FCFS、SOT、EDD、LCFS、STR2021/4/959例題作業(yè)（按到達順序）加工時間/天交貨日期（從現(xiàn)在起天數(shù)）A【例題】有5件任務(wù)都需要兩步操作（先1后2）來完成，下表給出了相應(yīng)的時間：（1）根據(jù)Johnson算法安排工作順序；（2）計算加工周期。任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.52021/4/960【例題】有5件任務(wù)都需要兩步操作（先1后2）來完成，下表任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5A,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操作22021/4/961任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.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操作2iCBDEA操作1操作22021/4/962A,3.0E,3.5D,3B,2C,11.03.06.09.練習(xí)某公司要生產(chǎn)4種產(chǎn)品，需要兩臺機器1和2。其中，有3種產(chǎn)品需要先在機器1上加工。下表給出了兩臺機器上加工各產(chǎn)品所需的時間。（1）安排生產(chǎn)順序，使得在最短時間內(nèi)完成生產(chǎn)。（2）機器1共需工作多長時間？（3）機器2應(yīng)該在機器1開始工作后多長時間開始運轉(zhuǎn)？任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.102021/4/963練習(xí)某公司要生產(chǎn)4種產(chǎn)品，需要兩臺機器1和2。其中，有3任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.109.5B,1.25A,2.10C,3.00D,2.1B,2.5A,3.2C,1.71.74.97.44.76.88.65機器1機器22021/4/964任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時間矩陣T分別為：試構(gòu)成一個能動作業(yè)計劃和無延遲作業(yè)計劃。D=1,1,11,2,31,3,22,1,32,2,22,3,1T=352243練習(xí)2021/4/965有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時間矩4，1，2M20604，1，20403，1，11182，2，11251，2，230604，1，20403，1，11182，2，11，1，1M10501，1，120604，1，20403，1，12，1，3M30802，1，30501，1，11OjM*T*T’

kTk{Ot}t2021/4/9664，1，2M20604，1，20403，1，11182，2，1694，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’

kTk{Ot}t2021/4/9671694，3，11393，2，41292，2，11，2，2M4，3，1M11219124，3，118133，3，317132，3，419131，3，3919124，3，13，2，4M491393，2，416122，3，419131，3，3891694，3，191393，2，42，2，1M191292，2，119131，3，37OjM*T*T’

kTk{Ot}t2021/4/9684，3，1M11219124，3，118133，3，317122194，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’

kTk{Ot}t2021/4/96922194，4，31819183，4，21827182，4，2，4，3M32736272，4，34，4，3M32427244，4，32433242，4，32427244，4，32433242，4，31，4，4M42426241，4，41427244，4，33，4，2M21819183，4，233242，4，326241，4，413OjM*T*T’

kTk{Ot}t15162021/4/9702，4，3M32736272，4，34，4，3M324272感謝您的閱讀收藏，謝謝！

2021/4/971感謝您的閱讀收藏，謝謝！

2021/4/971第八章制造業(yè)作業(yè)計劃與控制2021/4/972第八章制造業(yè)作業(yè)計劃與控制2021/4/91生產(chǎn)任務(wù)的最終落實MRP確定各車間的零部件投入出產(chǎn)計劃，將全廠性的產(chǎn)品出產(chǎn)計劃變成了各車間的生產(chǎn)任務(wù)。各車間要將車間的生產(chǎn)任務(wù)變成各個班組、各個工作地和各個工人的任務(wù)。將任務(wù)安排到工作地，牽涉到作業(yè)計劃。生產(chǎn)作業(yè)計劃是安排零部件（作業(yè)、活動）的產(chǎn)出數(shù)量、設(shè)備以及人工使用、投入時間及產(chǎn)出時間。2021/4/973生產(chǎn)任務(wù)的最終落實MRP確定各車間的零部件投入出產(chǎn)計劃，將全編制作業(yè)計劃要解決的問題由于每臺機器都可能被分配了多項任務(wù)，就帶來了零件在機器上加工的順序問題。編制作業(yè)計劃要解決先加工哪個工件、后加工哪個工件的加工順序問題確定機器加工每個工件的開始時間和完成時間2021/4/974編制作業(yè)計劃要解決的問題由于每臺機器都可能被分配了多項任務(wù)，第一節(jié)排序問題的基本概念一、名詞術(shù)語排序：確定工件在機器上的加工順序。作業(yè)計劃：不僅要確定工件的加工順序，而且還要確定機器加工每個工件的開始時間和完成時間。通常情況下都是按最早可能開（完）工時間來編制作業(yè)計劃。派工：按作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機床上加工。趕工：實際進度已落后于計劃進度時采取的行動。2021/4/975第一節(jié)排序問題的基本概念一、名詞術(shù)語2021/4/94“機器”，可以是工廠里的各種機床，也可以是維修工人，表示“服務(wù)者”“零件”代表“服務(wù)對象”。零件可以是單個零件，也可以是一批相同的零件“加工順序”則表示每臺機器加工n個零件的先后順序，是排序和編制作業(yè)計劃要解決的問題2021/4/976“機器”，可以是工廠里的各種機床，也可以是維修工人，表示“服二、假設(shè)條件和符號說明假設(shè)條件：1.一個工件不能同時在幾臺不同的機器上加工。2.工件在加工過程中采取平行移動方式，即當(dāng)上一道工序完工后，立即送下道工序加工。3.不允許中斷。一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其他工件。4.每道工序只在一臺機器上完成。5.工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。6.每臺機器同時只能加工一個工件2021/4/977二、假設(shè)條件和符號說明假設(shè)條件：2021/4/96有關(guān)符號Ji：工件i，i=1，2，…，nMj：機器j，j=1，2，…，npij為Ji在Mj上的加工時間ri為Ji的到達時間，指Ji從外部進入車間，可以加工的最早時間di為Ji的完工期限Ci為Ji的完工時間Cmax為最長完工時間Fi為Ji的流程時間，即工件在車間的實際停留時間Fmax為最長流程時間Li為工件的延遲時間Lmax為最長延遲時間2021/4/978有關(guān)符號Ji：工件i，i=1，2，…，n2021/4/97三、排序問題的分類根據(jù)機器數(shù)的多少單臺機器的排序問題多臺機器的排序問題對于多臺機器排序問題，根據(jù)加工路線的特征，分成單件作業(yè)排序(Job-Shop)問題流水作業(yè)排序(Flow-Shop)問題工件的加工路線不同，是單件作業(yè)排序問題的基本特征；所有工件的加工路線完全相同，是流水作業(yè)排序問題的基本特征。也就是說，每個零件都順序地經(jīng)過線上不同機器加工，它們的加工路線一致。2021/4/979三、排序問題的分類根據(jù)機器數(shù)的多少2021/4/98根據(jù)工件到達系統(tǒng)的情況靜態(tài)排序動態(tài)排序根據(jù)參數(shù)的性質(zhì)確定型排序隨機型排序根據(jù)目標(biāo)函數(shù)的情況單目標(biāo)排序多目標(biāo)排序2021/4/980根據(jù)工件到達系統(tǒng)的情況2021/4/99四參數(shù)法n/m/A/B其中，n為工件數(shù)m為機器數(shù)A車間類型。在A的位置若標(biāo)以“F”，則代表流水作業(yè)排序問題；若標(biāo)以“P”，則表示流水作業(yè)排列排序問題；若標(biāo)以“G”，則表示一般單件作業(yè)排序問題。當(dāng)m=1，則A處為空白。B為目標(biāo)函數(shù)，通常是使其值最小2021/4/981四參數(shù)法n/m/A/B2021/4/910四、甘特圖作業(yè)排序中最常用的一種工具，最早由亨利.甘特于1917年提出。兩種基本形式的甘特圖：作業(yè)進度圖和機器圖。作業(yè)進度圖表示一項工作的計劃開始日期、計劃完成日期以及現(xiàn)在的進度。

2021/4/982四、甘特圖作業(yè)排序中最常用的一種工具，最早由亨利.甘特于19例如，假設(shè)一個汽車零件制造公司有三項工作在進行中，它們分別是加工三種汽車零件A、B、C。這些工作的預(yù)定計劃和現(xiàn)在的完成情況如圖所示：2021/4/983例如，假設(shè)一個汽車零件制造公司有三項工作在進行中，它們分別是如果這三項工作都在等待進行磨削加工，之后他們要進行拋光才能最后交貨，則下圖表示了三種工作在兩種不同設(shè)備上的所需時間、時間安排和現(xiàn)在的進度。這種形式的甘特圖就稱為機器圖，它描述不同工作在每一臺機器上的工作次序，也可被用來管理生產(chǎn)進度。2021/4/984如果這三項工作都在等待進行磨削加工，之后他們要進行拋光才能最五、作業(yè)排序方案的評價標(biāo)準(zhǔn)1.工作流程時間從工件可以開始加工至完工的時間，包括在各個機器之間的移動時間、等待時間、加工時間以及由于機器故障、部件無法得到等問題引起的延誤時間等。2.加工周期完成一組工作所需的全部時間。它是從第一個工件在第一臺機器上開始加工時算起，到最后一個工件在最后一臺機器上完工時為止所經(jīng)過的時間。2021/4/985五、作業(yè)排序方案的評價標(biāo)準(zhǔn)1.工作流程時間2021/4/913.在制品庫存（WIP）在制品是對介于原材料和成品之間的生產(chǎn)過程中的產(chǎn)品的稱謂。一個工件正從一個工作地移向另一個，由于一些原因被拖延加工，正在被加工或放置于零件庫中，都可以看作在制品庫存。4.利用率用一臺機器或一個工人的有效生產(chǎn)時間占總工作時間的百分比來表示。2021/4/9863.在制品庫存（WIP）2021/4/915六、優(yōu)先調(diào)度規(guī)則調(diào)度方法：所謂調(diào)度方法，就是運用若干預(yù)先規(guī)定的優(yōu)先順序規(guī)則，順次決定下一個應(yīng)被加工的工件的排序方法。一個工作地可選擇的下一個工件會有很多種，因此，按什么樣的準(zhǔn)則來選擇，對排序方案的優(yōu)劣有很大影響。2021/4/987六、優(yōu)先調(diào)度規(guī)則調(diào)度方法：2021/4/916常用的優(yōu)先順序規(guī)則：FCFS規(guī)則（先到先服務(wù)）按訂單送到的先后順序進行加工。EDD規(guī)則優(yōu)先選擇完工期限最緊的工作。SPT規(guī)則（最短加工時間）優(yōu)先選擇加工時間最短的工件。STR規(guī)則（剩余松弛時間）優(yōu)先選擇STR最短的工件。STR為交貨前所剩余的時間與剩余的加工時間之差。MWKR規(guī)則優(yōu)先選擇余下加工時間最長的工件。LWKR規(guī)則優(yōu)先選擇余下加工時間最短的工件。MOPNR規(guī)則優(yōu)先選擇余下工序數(shù)最多的工件。RANDOM規(guī)則隨機地挑選下一個工件。。。。。。。2021/4/988常用的優(yōu)先順序規(guī)則：FCFS規(guī)則（先到先服務(wù)）按訂單送到的一般作業(yè)排序的目標(biāo)滿足顧客或下一道工序的交貨期要求流程時間最短準(zhǔn)備時間最短或成本最小化在制品庫存最低機器設(shè)備或勞動力利用最大化2021/4/989一般作業(yè)排序的目標(biāo)2021/4/918[例]

一個加工車間負(fù)責(zé)加工發(fā)動機機殼，現(xiàn)在共有5個機殼等待加工。只有一名技工在崗，做此項工作。現(xiàn)在已經(jīng)估算出各個機殼的標(biāo)準(zhǔn)加工時間，顧客也已經(jīng)明確提出了他們所希望的完工時間。下表顯示了周一上午的情況，顧客的取貨時間用從周一上午開始，還有多少工作小時來計算。發(fā)動機機殼所需標(biāo)準(zhǔn)加工時間（包括機器調(diào)整）預(yù)計顧客取貨時間（從現(xiàn)在開始算起的所需工作時間）機殼1810機殼2612機殼31520機殼4318機殼512222021/4/990[例]一個加工車間負(fù)責(zé)加工發(fā)動機機殼，現(xiàn)在共有5個機殼等待機殼加工次序開始工作加工時間結(jié)束工作流程時間預(yù)計顧客取貨時間顧客實際取貨時間提前小時數(shù)拖延小時數(shù)機殼40333181815機殼2369912123機殼198171710177機殼51712292922297機殼329154444204424總數(shù)1021201838平均數(shù)20.43.67.6平均在制品庫存=102/44=2.32個平均總庫存=120/44=2.73個SPT規(guī)則排序結(jié)果

顧客實際取貨時間基于以下假設(shè)：顧客不會在預(yù)定取貨時間之前來取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時馬上取走。流程時間=等待時間+加工時間平均在制品庫存=各工件流程時間之和÷加工周期平均總庫存=各工件實際取貨時間之和÷加工周期2021/4/991機殼加工次序開始加工結(jié)束流程預(yù)計顧客顧客實際取貨時間提前拖延機殼加工次序開始工作加工時間結(jié)束工作流程時間預(yù)計顧客取貨時間顧客實際取貨時間提前小時數(shù)拖延小時數(shù)機殼1088810102機殼286141412142機殼4143171718181機殼317153232203212機殼532124444224422總數(shù)115118336平均數(shù)23.00.67.2平均在制品庫存=115/44=2.61個平均總庫存=118/44=2.68個EDD規(guī)則排序結(jié)果

顧客實際取貨時間基于以下假設(shè)：顧客不會在預(yù)定取貨時間之前來取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時馬上取走。

比較SPT規(guī)則和EDD規(guī)則的排序結(jié)果，用SPT規(guī)則排序，其平均流程時間更短，在制品庫存更少。用EDD規(guī)則，可以給顧客提供更好的服務(wù)（平均延遲時間較少），它也提供了更低的總庫存水平。2021/4/992機殼加工次序開始加工結(jié)束流程預(yù)計顧客顧客實際取貨時間提前拖延例題作業(yè)（按到達順序）加工時間/天交貨日期（從現(xiàn)在起天數(shù)）A35B46C27D69E12優(yōu)先調(diào)度準(zhǔn)則：FCFS、SOT、EDD、LCFS、STR2021/4/993例題作業(yè)（按到達順序）加工時間/天交貨日期（從現(xiàn)在起天數(shù)）A優(yōu)先調(diào)度法則按SPT法則可使工件的平均流程時間最短，從而減少在制品量。FCFS法則來自排隊論，它對工件較公平。EDD法則可使工件延誤時間最小。MWKR法則使不同工作量的工件的完工時間盡量接近。LWKR法則，使工作量小的工件盡快完成。2021/4/994優(yōu)先調(diào)度法則按SPT法則可使工件的平均流程時間最短，從而減少第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件的加工路線都一致。加工路線一致，是指工件的流向一致，并不要求每個工件必須經(jīng)過加工路線上每臺機器加工。對于流水作業(yè)排序問題，工件在不同機器上的加工順序不盡一致。排列排序問題：所有工件在各臺機器上的加工順序都相同的情況。2021/4/995第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件一、最長流程時間Fmax的計算n/m/P/Fmax問題，n個零件要按相同的加工路線經(jīng)過m臺機器加工，目標(biāo)是使這批零件的最長流程時間最短。最長流程時間又稱加工周期，它是從第一個零件在第一臺機器開始加工時算起，到最后一個零件在最后一臺機器上完成加工時為止所經(jīng)過的時間。2021/4/996一、最長流程時間Fmax的計算n/m/P/Fmax問題，n個例有一個6/4/P/Fmax問題，其加工時間如下表所示。當(dāng)按順序S=（6，1，5，2，4，3）加工時，求Fmax。i1234564231424567455875554243312021/4/997例有一個6/4/P/Fmax問題，其加工時間如下表所示。當(dāng)ipi1pi2pi3pi46152432551445444532582175336742610121316711152027331217223035421321253238462021/4/998ipi1pi2pi3pi461524325514454445二、兩臺機器排序問題兩個或更多的作業(yè)必須在兩臺機器上以相同的工序進行加工，要使加工周期最短，約翰遜于1954年提出了一個有效算法，那就是著名的Johnson算法。約翰遜算法包括以下幾個步驟：（1）列出每個作業(yè)在兩臺機器上的加工時間。（2）選擇最短的加工時間，如果有兩個相同的值，則任選一個。（3）如果最短的加工時間來自第一臺機器，那么先完成這個作業(yè)；如果來自第二臺機器，那么這個作業(yè)就放在最后完成。然后從加工時間矩陣中劃去已排序工件的加工時間。（4）對于剩余的作業(yè)重復(fù)第二步和第三步，直到整個排序完成。2021/4/999二、兩臺機器排序問題兩個或更多的作業(yè)必須在兩臺機器上以相同的【例】求如表所示的6/2/F/Fmax問題的最優(yōu)解。i123456ai518534bi722474.5將零件2排第1位2將零件3排第6位23將零件5排第2位253將零件6排第3位2563將零件4排第5位25643將零件1排第4位2561432021/4/9100【例】求如表所示的6/2/F/Fmax問題的最優(yōu)解。i123【例題】有5件任務(wù)都需要兩步操作（先1后2）來完成，下表給出了相應(yīng)的時間：（1）根據(jù)Johnson算法安排工作順序；（2）計算加工周期。任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.52021/4/9101【例題】有5件任務(wù)都需要兩步操作（先1后2）來完成，下表任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.2B2.02.5C1.01.6D3.03.0E3.51.5A,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操作22021/4/9102任務(wù)操作1所需時間（小時）操作2所需時間（小時）A3.01.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操作2iCBDEA操作1操作22021/4/9103A,3.0E,3.5D,3B,2C,11.03.06.09.1.將所有ai≤

bi的工件按ai值不減的順序排成一個序列A；2.將ai＞bi的工件按bi值不增的順序排成一個序列B；3.將A放到B之前，就構(gòu)成了一個最優(yōu)加工順序。改進算法2021/4/91041.將所有ai≤bi的工件按ai值不減的順序排成一個序工件號123456ai518534bi722474工件最優(yōu)順序：256143

1345582747424

8

13

18

2631115222628aibi

最優(yōu)順序下的加工周期為282021/4/9105工件號123練習(xí)某公司要生產(chǎn)4種產(chǎn)品，需要兩臺機器1和2。其中，有3種產(chǎn)品需要先在機器1上加工。下表給出了兩臺機器上加工各產(chǎn)品所需的時間。（1）安排生產(chǎn)順序，使得在最短時間內(nèi)完成生產(chǎn)。（2）機器1共需工作多長時間？（3）機器2應(yīng)該在機器1開始工作后多長時間開始運轉(zhuǎn)？任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.102021/4/9106練習(xí)某公司要生產(chǎn)4種產(chǎn)品，需要兩臺機器1和2。其中，有3任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小時）A3.22.10B2.51.25C1.73.00D2.109.5B,1.25A,2.10C,3.00D,2.1B,2.5A,3.2C,1.71.74.97.44.76.88.65機器1機器22021/4/9107任務(wù)在機器1上加工所需時間（小時）在機器2上加工所需時間（小三、一般n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法是一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費(時間、占用空間等)下給出待解決組合優(yōu)化問題的可行解。啟發(fā)式方法因其易于實現(xiàn)、計算復(fù)雜度低等原因，目前應(yīng)用得最為廣泛。2021/4/9108三、一般n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法是一個（一）Palmer法1965年，D．S．Palmer提出按斜度指標(biāo)排列工件的啟發(fā)式算法，稱之為Palmer法。工件的斜度指標(biāo)可按下式計算：

k=l，2，…，m式中，m為機器數(shù)；pik為工件i在Mk上的加工時間。按照各工件λi不增的順序排列工件，可得出令人滿意的順序。2021/4/9109（一）Palmer法1965年，D．S．Palmer提出按斜2021/4/91102021/4/939例有一個4/3/F/Fmax問題，其加工時間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。i1234Pi11263Pi28429Pi34582解：對于本例，

λ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)順序。如不是這樣，則從中挑選較優(yōu)者。在最優(yōu)順序下，F(xiàn)max=28。2021/4/9111例有一個4/3/F/Fmax問題，其加工時間如下表所示，試（二）關(guān)鍵零件法步驟如下：（1）計算每個零件的總加工時間，找出加工時間最長的零件C，將其作為關(guān)鍵零件。（2）對于余下的零件，若pi1≤pim，則按pi1不減的順序排成一個序列Sa；若pi1≥pim，則按pim不增的順序排成一個序列Sb。（3）順序（Sa，C，Sb）即為所求順序。2021/4/9112（二）關(guān)鍵零件法步驟如下：2021/4/941i1234pi11263pi28429pi34582pi13111614例有一個4/3/F/Fmax問題，其加工時間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。解：總加工時間最長的為3號零件，pi1≤pi3的零件為1和2，按pi1不減的順序排成Sa=（1，2）；pi1≥pi3的零件為4號零件，Sb=（4）,這樣得到的加工順序為（1，2，3，4）。2021/4/9113i1234pi11263pi28429pi34582pi13例題用關(guān)鍵工件法求解下表的最優(yōu)排序。解：總加工時間最長的為2號零件，pi1≤pi2的零件為1和3，按pi1不減的順序排成sa=（1，3）；pi1＞pi2的零件為4號零件，sb=（4），這樣得到的順序為（1，3，2，4）。i1234pi11954pi25763pi34635pi46237i1234pi11954pi25763pi34635pi46237pi162417192021/4/9114例題用關(guān)鍵工件法求解下表的最優(yōu)排序。i1234pi119單件作業(yè)排序問題2021/4/9115單件作業(yè)排序問題2021/4/944一、問題的描述加工描述矩陣D為D=1,1,11,2,31,3,22,1,32,2,12,3,2

對于一般單件作業(yè)排序問題，每個工件都有其獨特的加工路線，工件沒有一定的流向。要描述一道工序，需要用三個參數(shù)：3個參數(shù)：i，j和k。i表示工件代號，j表示工序號，k表示完成工序i的第j道工序的機器代號。（i，j，k）表示工件i的第j道工序在機器k上進行。2021/4/9116一、問題的描述加工描述矩陣D為D=1,1,11,2,3二、兩種作業(yè)計劃的構(gòu)成各工序都按最早可能完工時間安排的作業(yè)計劃稱為能動作業(yè)計劃。各工序都按最早可能開始時間安排的作業(yè)計劃稱為無延遲作業(yè)計劃。無延遲作業(yè)計劃是沒有任何延遲出現(xiàn)的能動作業(yè)計劃。2021/4/9117二、兩種作業(yè)計劃的構(gòu)成各工序都按最早可能完工時間安排的作業(yè)計2兩種單件作業(yè)排序方法例：加工描述矩陣和加工時間矩陣如下，分別按下列兩種方法進行作業(yè)排序．

(1)最小最早完工時間法（能動作業(yè)計劃）(2)最小最早開工時間法（無延遲作業(yè)計劃）1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝2021/4/91182兩種單件作業(yè)排序方法(1)最小最早完工時間法（能動作業(yè)(l)最小最早完工時間法

1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝序列可排事件最早可能開工時間最早可能完工時間最小最早可能完工時間所需機器排定事件1234561,3,2M2141412

1,3,22,3,2M29912781,3,22,3,22,2,1M1898731,3,22,2,11,2,3M3778331,2,32,2,12,1,3M3363201,2,32,1,31,1,1M1223001,1,12,1,32021/4/9119(l)最小最早完工時間法1,1,11,2,3按此方法編制出的作業(yè)計劃叫做：能動作業(yè)計劃

1,1,11,2,31,3,22,1,32,2,12,3,2D＝

242354T＝排定事件1,1,12,1,31,2,32,2,12,3,21,3,2時間機器機器1機器2機器31,1,12,1,31,2,32,2,12,3,21,3,20032378121482021/4/9120按此方法編制出的作業(yè)計劃叫做：能動作業(yè)計劃1,1,1(2)最小最早開工時間法

1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝序列可排事件最早可能開工時間最早可能完工時間最小最早可能開工時間所需機器排定事件1234562,3,2M29139

2,3,21,3,2M27912781