5作業(yè)計劃與控制11.13

第5章作業(yè)計劃與控制

OperationsSchedulingandControlling排序問題的基本概念單臺機(jī)器的排序問題多臺機(jī)器的排序問題生產(chǎn)作業(yè)控制編制作業(yè)計劃要解決的問題任務(wù)分配：每個工人、每個工作地的日生產(chǎn)任務(wù)編制作業(yè)計劃（Scheduling）：將資源分配給不同的任務(wù)，按照既定的優(yōu)化目標(biāo)，確定各種資源利用的時間問題工廠：對每個工人和工作地安排每天的生產(chǎn)任務(wù)，規(guī)定開始時間和完成時間醫(yī)院：安排病人手術(shù)——安排手術(shù)室、配備手術(shù)器械、手術(shù)醫(yī)師和護(hù)士學(xué)校：安排上課時間表，使學(xué)生能按規(guī)定的時間到規(guī)定的教室聽事先安排的教師講課項目計劃管理：作業(yè)計劃生產(chǎn)排序：通過排序方法編制生產(chǎn)計劃，提高生產(chǎn)效率5.1排序的基本概念

作業(yè)計劃與排序是一回事么？作業(yè)計劃是安排零部件（作業(yè)、活動）的出產(chǎn)數(shù)量、設(shè)備及人工使用、投入時間及出產(chǎn)時間。排序，給出零部件在一臺或一組設(shè)備上加工的先后順序的工作。編制作業(yè)計劃與排序的概念和目的都是不同的。但是，編制作業(yè)計劃的主要工作之一就是要確定出最佳的作業(yè)順序。根據(jù)排序規(guī)則對每一個到達(dá)的工件安排作業(yè)順序工作地工件排隊等待加工來自上游工作地的工件加工完畢的工件流向下一工作地排序的概念生產(chǎn)作業(yè)排序就是指對于等候某個設(shè)備或工作中心加工的多個任務(wù)，確定這些任務(wù)加工的先后次序。目的：提高設(shè)備或工作中心的效率、減少在制品占用量、縮短生產(chǎn)周期、保證按期交貨作業(yè)排序（sequencing）的目標(biāo)作業(yè)排序是解決各個生產(chǎn)層次中生產(chǎn)任務(wù)的加工順序問題，既包括哪個生產(chǎn)任務(wù)先投產(chǎn)，哪個生產(chǎn)任務(wù)后投入，還包括在同一設(shè)備上不同工件的加工順序。作業(yè)排序（sequencing）：確定工件在設(shè)備上的加工順序。作業(yè)計劃（scheduling）：不僅包括確定工件的加工順序，還包括確定設(shè)備加工每個工件的開始時間和結(jié)束時間。排序的目標(biāo)：如何在盡可能滿足各種約束條件的情況下，給出一個令人滿意的排序方案。一、有關(guān)的名詞術(shù)語排序(Sequencing)：確定零件在機(jī)器上的加工順序編制作業(yè)計劃(Scheduling)：加工制造發(fā)生之前的活動（火車時刻表）。包括確定加工順序、加工任務(wù)的分配和加工每個零件的開始和完成時間調(diào)度：作業(yè)計劃編制后實(shí)施生產(chǎn)控制所采取的一切行動（火車運(yùn)行的安排，發(fā)生晚點(diǎn)后的處理）派工（Dispatching）：在作業(yè)計劃制定以后，按照作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)通過工票或施工單的形式下達(dá)到具體的機(jī)床和工人趕工（Expediting）：在實(shí)際進(jìn)度已落后于計劃進(jìn)度時采取的行動控制（Controlling）：機(jī)器：表示“服務(wù)者”，可以是工廠里的各種機(jī)床，也可以是維修工人；可以是輪船要停靠的碼頭，也可以是電子的計算機(jī)中央處理單元、存貯器和輸入、輸出單元零件：代表“服務(wù)對象”?？梢允菃蝹€零件，也可以是一批相同的零件加工路線：零件加工經(jīng)過不同機(jī)器構(gòu)成的路線。（某零件要經(jīng)過車、銑、占、磨的路線加工，我們可以用M1,M2,M3,M4來表示）加工順序：表示每臺機(jī)器加工n個零件的先后順序，是排序要解決的問題4參數(shù)表示法R.W.Conway等人在《TheoryofScheduling》中提出的表示方法，該方法只用4個參數(shù)就可以表示大多數(shù)不同的排序問題。即：

n/m/A/Bn──零件數(shù)m──機(jī)器數(shù)A──作業(yè)類型在A的位置若標(biāo)以“F”，則代表流水作業(yè)排序問題若標(biāo)以“P”，則表示流水作業(yè)排列排序問題若標(biāo)以“G”，則表示一般單件作業(yè)排序問題當(dāng)m＝1，則A處為空白，因?yàn)閷τ趩闻_機(jī)器的排序問題來說，無所謂加工路線問題B──目標(biāo)函數(shù)，通常是使其值最小例：二、排序常用的符號

Ji----工件i，i=1,2,....ndi----工件i的交貨期Pi----工件i的加工時間,,pij----工件i在機(jī)器j上的加工時間,j=1,…,mWi----工件i在系統(tǒng)內(nèi)的等待時間,,wij----工件i在機(jī)器j前的等待時間,j=1,…,m

Ci----工件i的完成時間,在工件都已到達(dá)的情況下,Ci=Pi+WiFi----工件i的流程時間，在工件都已到達(dá)的情況下,Fi=Pi+WiLi----工件i的延誤時間,Li=Ci-di,Li<=0按期或完成提前；Li>0延誤Ti----工件i的延期量,Ti=max{0,Li}Ei----工件i提前完成的時間作業(yè)排序的基本分析

1、作業(yè)排序的一般假設(shè)：（1）一臺設(shè)備不得同時加工兩個或兩個以上的任務(wù)；（2）一個任務(wù)不能同時在幾臺設(shè)備上加工；（3）每個任務(wù)必須按照工藝順序進(jìn)行加工。

2、作業(yè)排序所需的有關(guān)生產(chǎn)信息：任務(wù)Ji在第j個工序Oij（j=1,2,…，Ni，i=1,2,…，M）在相應(yīng)的設(shè)備上Mij（i,j=1,2,…N）上所需要的加工時間為tij，Ji的可能開始時刻為ri和應(yīng)完工的交貨期di。

3、作業(yè)排序的一般結(jié)論：

平均流程時間的最優(yōu)排序方案對于平均完工時間、平均延遲以及平均等待時間也是最優(yōu)的。但是這一結(jié)論對于Fmax和其他最大值目標(biāo)是不成立的。排序問題分類按機(jī)器單臺機(jī)器排序問題多臺機(jī)器排序問題單件作業(yè)排序問題流水線作業(yè)排序問題按零件到達(dá)車間的情況靜態(tài)的排序問題動態(tài)的排序問題按目標(biāo)函數(shù)的性質(zhì)分類按參數(shù)確定型排序問題隨機(jī)型排序問題三、排序問題的分類單臺機(jī)器的排序問題

n個工件全部經(jīng)由一臺機(jī)器處理

J1J2J3Jn機(jī)器到達(dá)系統(tǒng)工件的集合離開系統(tǒng)（機(jī)器）

為實(shí)現(xiàn)任務(wù)總等待時間最短的目標(biāo)，保證盡可能多的對象早日加工出來，加速資金周轉(zhuǎn)，只需根據(jù)最短加工時間準(zhǔn)則對加工對象排序即可。n項任務(wù)在兩臺機(jī)器的排序問題

n個工件都必須經(jīng)過機(jī)器1和機(jī)器2的加工，即工藝路線是一致的。機(jī)器1到達(dá)系統(tǒng)工件的集合離開系統(tǒng)（機(jī)器）J1J2J3Jn機(jī)器211.2流水作業(yè)排序問題流水線是流水車間(Flowshop)典型的代表，每個零件的加工路線都一致。只要加工路線一致：M1，M2,

M3，…..，Mm,不要求每個零件都經(jīng)過每臺機(jī)器加工流水線加工方式一、最長流程時間Fmax的計算最長流程時間又稱作加工周期（1）問題的描述和表示描述：n個不同零件要按相同的加工路線經(jīng)過m臺機(jī)器加工，目標(biāo)是使這批零件的加工周期最短（加工路線確定，對不同的零件，根據(jù)目標(biāo)求各個零件的加工次序）表示

（2）求解加工周期

加工周期是指第一個零件在第一臺機(jī)器上開始加工到最后一個零件在最后一臺機(jī)器上完成加工為止，所需要的時間假設(shè)，n個零件的加工順序?yàn)镾=(S1,S2……,Sn)Si為排在i位加工的零件代號CkSi表示零件Si在機(jī)器Mk上的完工時間PSik表示零件Si在Mk上的加工時間k=1,2,3,……,m，i=1,2,3,……,n總加工周期的計算方法工件在兩臺設(shè)備上的加工時間工件編號J1J2J3J4J5設(shè)備A36715設(shè)備B28643例:在設(shè)備A和B上安排5個工件的加工任務(wù)，每項任務(wù)的作業(yè)時間如下表所示。求:該順序的總加工周期Fmax。圖解法：30AB0表格法工件編號J1J2J3J4J5設(shè)備A3369716117522設(shè)備B25817623427330Fmax=306/4/p/Fmax問題，當(dāng)按順序S＝(6,1,5,2,4,3)加工時，求Fmax.

加工周期為46（1）描述和表示描述：n個零件經(jīng)過2臺機(jī)器加工，使加工周期最短的流水作業(yè)排序問題表示（2）求解方法Johnson算法二、2臺機(jī)器的排序問題求解算法n/2/F/Fmax問題的最優(yōu)算法Johnson算法：

(1)列出所有工件在兩臺設(shè)備上的作業(yè)時間。(2)找出作業(yè)時間最小者。(3)如果該最小值是在設(shè)備1上，將對應(yīng)的工件排在前面，如果該最小值是在設(shè)備2上，則將對應(yīng)的工件排在后面。(4)排除已安排好的工件，在剩余的工件中重復(fù)步驟(2)和(3)，直到所有工件都安排完畢。例：某一班組有A、B兩臺設(shè)備，要完成5個工件的加工任務(wù)。每個工件在設(shè)備上的加工時間如下表所示。求總加工周期最短的作業(yè)順序。工件在兩臺設(shè)備上的加工時間工件編號J1J2J3J4J5設(shè)備A36715設(shè)備B28643

求最優(yōu)順序算法步驟的改進(jìn)把Johnson算法作些改變，改變后的算法按以下步驟進(jìn)行：①將所有ai≤bi的零件按ai值不減的順序排成一個序列A。②將所有ai＞bi的零件按bi值不增的順序排成一個序列B。③將A放到B之前，就構(gòu)成了最優(yōu)加工順序

序列A為(2，5，6，1)，序列B為(4，3)，構(gòu)成最優(yōu)順序?yàn)?2，5，6，1，4，3)，與Johnson算法結(jié)果一致。

Johnson法則只是一個充分條件，不是必要條件。不符合這個法則的加工順序，也可能是最優(yōu)順序。如對例11-2順序(2，5，6，4，1，3)不符合Johnson法則，但它也是一個最優(yōu)順序

對于3臺機(jī)器的流水車間排序問題，只有幾種特殊類型的問題找到了有效算法。對于一般的流水車間排列排序問題，可以用分支定界法。一般的流水車間排列排序問題如想求得精確解可用分支界定法，但計算量比較大，以至于計算機(jī)也無法求解，因此常用一些啟發(fā)式算法求近似解

（一）Palmer法按零件的斜度指標(biāo)排列零件的啟發(fā)式算法零件的斜度指標(biāo)三、一般n/m/P/Fmax問題的啟發(fā)式算法按照各零件λi不增的順序排列零件，可得出令人滿意的順序，如果排列的結(jié)果有多個，可以通過計算Fmax，取其中最優(yōu)Fmax對應(yīng)的排序作為排序結(jié)果。例，有一個4/3/F/Fmax問題，其加工時間如下表所示，試用Palmer法求解

Plamer法解：計算λi按照Palmer計算公式步驟1計算,找出其中最大者，定義為關(guān)鍵工件JC。步驟2除JC外，將滿足pi1<=pim的工件，按ti1值的大小，從小到大排在JC的前面。步驟3除JC外，將滿足pi1>pim的工件，按tim值的大小，從大到小排在JC的后面。步驟4如有多個方案，可再加比較，從中選優(yōu)。（二）關(guān)鍵工件法

關(guān)鍵工件法舉例J1J2J3J4J5J6機(jī)器1pi15541210機(jī)器2pi25553610機(jī)器3pi3833474機(jī)器4pi4282156機(jī)器5pi55212810總和252315112840找出關(guān)鍵工件：工作負(fù)荷最大的40，對應(yīng)的是工件6，所以JC=J6確定排在關(guān)鍵工件前面的工件：滿足步驟2條件的有J4,J5,J1，所以有J4–J5–J1-J6–確定排在關(guān)鍵工件后面的工件：滿足步驟3條件的有J2,J3,所以有–J6–J2–J3最后有：J4–J5–J1–J6–J2–J3

關(guān)鍵零件法求近優(yōu)解舉例第三節(jié)單件作業(yè)計劃問題一、任務(wù)分配問題二、單間作業(yè)排序問題三、優(yōu)先派工法則一、任務(wù)分配問題把零件分配給工人或機(jī)器加工，將區(qū)域分配給銷售人員，將出故障的機(jī)器分配給維修小組等，都是任務(wù)分配問題。求解任務(wù)分配問題的目標(biāo)是使任務(wù)與資源得到最佳匹配。匈牙利算法1、將每行的元素減去行中的最小元素，如果某列中沒有出現(xiàn)0元素，再將該列元素減去列中的最小元素。2、測試是否已達(dá)到最佳分配組合。求出能夠穿越所有0的最小線數(shù)，如果此數(shù)等于矩陣的階，直接進(jìn)入第4步。否則繼續(xù)第3步。3、將沒有被直線覆蓋的元素減去其中的最小元素，并將各直線交點(diǎn)上的元素加上該最小元素。然后返回第2步。4、進(jìn)行分配：從0元素最少的行或列開始，選擇一個0，然后劃去同行和同列的其他0。如此反復(fù)進(jìn)行，直到所有0元素都被選擇或劃去為止。例：根據(jù)給定數(shù)據(jù)，求解各項作業(yè)與機(jī)器的最佳分配。機(jī)器ABCD工作18624工作2671110工作33576工作4510129解：1、行作業(yè)與列作業(yè)：保證每行每列都有0存在。機(jī)器ABCD工作16300工作20052工作30141工作404722、用最少的直線劃去所有0元素。機(jī)器ABCD工作16300工作20052工作30141工作404723、將剩余元素減去其中的最小元素1，并將各直線交點(diǎn)的元素加上1。機(jī)器ABCD工作17400工作20041工作30130工作40461機(jī)器ABCD工作17400工作20041工作30130工作404614、用最少的直線劃去所有0元素。5、分配機(jī)器ABCD工作17400工作20041工作30130工作40461所選0元素的數(shù)目等于4，故試分配成功。分配方案如下：分