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

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

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

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

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

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

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

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

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

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

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

n個(gè)工件全部經(jīng)由一臺(tái)機(jī)器處理

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

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

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

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

（2）求解加工周期

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

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

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

求最優(yōu)順序算法步驟的改進(jìn)把Johnson算法作些改變，改變后的算法按以下步驟進(jìn)行：①將所有ai≤bi的零件按ai值不減的順序排成一個(gè)序列A。②將所有ai＞bi的零件按bi值不增的順序排成一個(gè)序列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法則只是一個(gè)充分條件，不是必要條件。不符合這個(gè)法則的加工順序，也可能是最優(yōu)順序。如對(duì)例11-2順序(2，5，6，4，1，3)不符合Johnson法則，但它也是一個(gè)最優(yōu)順序

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

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

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

關(guān)鍵工件法舉例J1J2J3J4J5J6機(jī)器1pi15541210機(jī)器2pi25553610機(jī)器3pi3833474機(jī)器4pi4282156機(jī)器5pi55212810總和252315112840找出關(guān)鍵工件：工作負(fù)荷最大的40，對(duì)應(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è)計(jì)劃問(wèn)題一、任務(wù)分配問(wèn)題二、單間作業(yè)排序問(wèn)題三、優(yōu)先派工法則一、任務(wù)分配問(wèn)題把零件分配給工人或機(jī)器加工，將區(qū)域分配給銷(xiāo)售人員，將出故障的機(jī)器分配給維修小組等，都是任務(wù)分配問(wèn)題。求解任務(wù)分配問(wèn)題的目標(biāo)是使任務(wù)與資源得到最佳匹配。匈牙利算法1、將每行的元素減去行中的最小元素，如果某列中沒(méi)有出現(xiàn)0元素，再將該列元素減去列中的最小元素。2、測(cè)試是否已達(dá)到最佳分配組合。求出能夠穿越所有0的最小線數(shù)，如果此數(shù)等于矩陣的階，直接進(jìn)入第4步。否則繼續(xù)第3步。3、將沒(méi)有被直線覆蓋的元素減去其中的最小元素，并將各直線交點(diǎn)上的元素加上該最小元素。然后返回第2步。4、進(jìn)行分配：從0元素最少的行或列開(kāi)始，選擇一個(gè)0，然后劃去同行和同列的其他0。如此反復(fù)進(jìn)行，直到所有0元素都被選擇或劃去為止。例：根據(jù)給定數(shù)據(jù)，求解各項(xiàng)作業(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，故試分配成功。分配方案如下：分