《生產(chǎn)與運(yùn)作管理》(第四版)-第9章-制造業(yè)作業(yè)計(jì)劃與控制課件

生產(chǎn)與運(yùn)作管理

Production&OperationsManagement華中科技大學(xué)管理學(xué)院TheSchoolofManagement，HUST陳榮秋馬士華RongqiuChenandShihuaMa華中科大管理學(xué)院陳榮秋馬士華1生產(chǎn)與運(yùn)作管理

Production&Operation1第9章制造業(yè)作業(yè)計(jì)劃與控制SchedulingandControllingforManufacturing9.1作業(yè)計(jì)劃問題的基本概念9.2流水作業(yè)排序問題9.3單件作業(yè)的排序問題9.4生產(chǎn)作業(yè)控制

華中科大管理學(xué)院陳榮秋馬士華2第9章制造業(yè)作業(yè)計(jì)劃與控制SchedulingandC2作業(yè)計(jì)劃問題的基本概念編制作業(yè)計(jì)劃要解決的問題編制作業(yè)計(jì)劃實(shí)質(zhì)上是要將資源分配給不同的任務(wù)，按照既定的優(yōu)化目標(biāo)，確定各種資源利用的時(shí)間問題。由于每臺(tái)機(jī)器都可能被分配了多項(xiàng)任務(wù)，而這些任務(wù)受到加工路線的約束，就帶來了零件在機(jī)器上加工的順序問題。有關(guān)名詞術(shù)語9.1.2假設(shè)條件與符號(hào)說明華中科大管理學(xué)院陳榮秋馬士華3作業(yè)計(jì)劃問題的基本概念編制作業(yè)計(jì)劃要解決的問題華中科大管理學(xué)3

9.1.1有關(guān)的名詞術(shù)語編制作業(yè)計(jì)劃或排程(Scheduling)排序(Sequencing)派工(Dispatching)控制(Controlling)趕工(Expediting)“調(diào)度”是作業(yè)計(jì)劃編制后實(shí)施生產(chǎn)控制所采取的一切行動(dòng)，“編制作業(yè)計(jì)劃”是加工制造發(fā)生之前的活動(dòng)，屬于計(jì)劃范疇。華中科大管理學(xué)院陳榮秋馬士華49.1.1有關(guān)的名詞術(shù)語編制作業(yè)計(jì)劃或排程(Schedu4有關(guān)名詞術(shù)語（續(xù)）“機(jī)器”，可以是工廠里的各種機(jī)床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計(jì)算機(jī)中央處理單元、存貯器和輸入、輸出單元。一句話，表示“服務(wù)者”。“零件”代表“服務(wù)對(duì)象”。零件可以是單個(gè)零件，也可以是一批相同的零件?！凹庸ぢ肪€”是零件加工的工藝過程決定的，它是零件加工在技術(shù)上的約束。“加工順序”則表示每臺(tái)機(jī)器加工n個(gè)零件的先后順序，是排序和編制作業(yè)計(jì)劃要解決的問題。華中科大管理學(xué)院陳榮秋馬士華5有關(guān)名詞術(shù)語（續(xù)）“機(jī)器”，可以是工廠里的各種機(jī)床，也可以是59.1.2假設(shè)條件與符號(hào)說明假設(shè)條件①一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工。②工件在加工過程中采取平行移動(dòng)方式，即當(dāng)上一道工序完工后，立即送下道工序加工。③不允許中斷。當(dāng)一個(gè)工件一旦開始加工，必須一直進(jìn)行到完工，不得中途停止插入其它工件。④每道工序只在一臺(tái)機(jī)器上完成。⑤工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無關(guān)。⑥每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。華中科大管理學(xué)院陳榮秋馬士華69.1.2假設(shè)條件與符號(hào)說明假設(shè)條件華中科大管理學(xué)院陳榮秋69.1.2假設(shè)條件與符號(hào)說明（續(xù)）符號(hào)說明Ji─工件i，i＝1,2,…,n。Mj─機(jī)器j，j＝1,2,…,m。pij─Ji在Mj上的加工時(shí)間，Ji的總加工時(shí)間為Pi＝∑pijri─Ji的到達(dá)時(shí)間，或準(zhǔn)備就緒時(shí)間，指Ji從外部進(jìn)入車間，可以開始加工的最早時(shí)間。di─Ji的完工期限。Ci─Ji的完工時(shí)間,Ci＝ri＋∑(wij+pij)=ri+Wi+Pi.Cmax─最長完工時(shí)間,Cmax＝max{Ci}.華中科大管理學(xué)院陳榮秋馬士華79.1.2假設(shè)條件與符號(hào)說明（續(xù)）符號(hào)說明華中科大管理學(xué)院79.1.2假設(shè)條件與符號(hào)說明（續(xù)）Fi─Ji的流程時(shí)間，即工件在車間的實(shí)際停留時(shí)間,Fi＝CI-ri＝Wi+Pi.Fmax─最長流程時(shí)間，F(xiàn)max＝max{Fi}.Li─工件延遲時(shí)間，Li＝Ci－di＝ri＋Pi.+Wi－di＝(Pi.+Wi)－(di-ri)＝Fi－ai.當(dāng)Li＞0(正延遲)，說明Ji的實(shí)際完工時(shí)間超過了完工期限；當(dāng)Li＜0(負(fù)延遲)，說明Ji提前完工；當(dāng)Li＝0(零延遲)，Ji按期完工。Lmax─最長延遲時(shí)間，Lmax＝max{Li}.華中科大管理學(xué)院陳榮秋馬士華89.1.2假設(shè)條件與符號(hào)說明（續(xù)）Fi─Ji的流程時(shí)間，即89.2流水作業(yè)排序問題流水車間(Flowshop):工件的加工路線都一致，典型的如流水線9.2.1最長流程時(shí)間的計(jì)算9.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法9.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法相同零件、不同移動(dòng)方式下加工周期的計(jì)算Work

Center#1WorkCenter#2Output華中科大管理學(xué)院陳榮秋馬士華99.2流水作業(yè)排序問題流水車間(Flowshop):工件99.2.1最長流程時(shí)間的計(jì)算工件代號(hào)i146352Pi1453486Pi2391375Pi3768259Pi4563924491216243071819223136142432343948193035444652華中科大管理學(xué)院陳榮秋馬士華109.2.1最長流程時(shí)間的計(jì)算工件代號(hào)i1109.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法約翰森法則如果Min(ai,bj)<Min(aj,bi),則工件i應(yīng)該排在工件j之前。約翰森算法（1）從加工時(shí)間矩陣中找出最短加工時(shí)間；（2）若最短加工時(shí)間出現(xiàn)在機(jī)器M1

上，則對(duì)應(yīng)工件應(yīng)該盡可能往前排；若最短加工時(shí)間出現(xiàn)在機(jī)器M2

上，則對(duì)應(yīng)工件應(yīng)該盡可能往后排。華中科大管理學(xué)院陳榮秋馬士華119.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法約翰森法則華中科大管119.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）然后從加工時(shí)間矩陣中劃去已排序工件的加工時(shí)間。若最短加工時(shí)間有多個(gè)，則任挑一個(gè)。（3）若所有工件都已排序，停止。否則，轉(zhuǎn)步驟（1）。華中科大管理學(xué)院陳榮秋馬士華129.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）然后從加工時(shí)間12將工件2排在第1位2將工件3排在第6位2

3將工件5排在第2位2

5

3將工件6排在第3位2

5

6

3將工件4排在第5位2

5

6

4

3將工件1排在第4位2

5

6

1

4

3最優(yōu)加工順序?yàn)镾=(2,5,6,1,4,3),Fmax=28I123456Ai518534Bi7224749.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）華中科大管理學(xué)院陳榮秋馬士華13將工件2排在第1位2I139.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）Johnson算法的改進(jìn)1.將所有ai≤

bi的工件按ai值不減的順序排成一個(gè)序列A；2.將ai＞bi的工件按bi值不增的順序排成一個(gè)序列B；3.將A放到B之前，就構(gòu)成了一個(gè)最優(yōu)加工順序。華中科大管理學(xué)院陳榮秋馬士華149.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）Johnso149.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）舉例工件號(hào)123456ai518534bi722474工件最優(yōu)順序：256143

1345582747424

8

13

18

2631115222628aibi

最優(yōu)順序下的加工周期為28華中科大管理學(xué)院陳榮秋馬士華159.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）舉例工件號(hào)159.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法關(guān)鍵工件法1.計(jì)算每個(gè)工件的總加工時(shí)間，將加工時(shí)間最長的工件作為關(guān)鍵工件C；2.對(duì)于余下的工件，若pi1≤pim則按pi1不減的順序排成一個(gè)序列Sa

,若pi1>pim

則按pim不增的順序排成一個(gè)序列Sb;3.順序（Sa,C,Sb）即為所求順序。華中科大管理學(xué)院陳榮秋馬士華169.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法關(guān)鍵工件法華中科大169.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法（續(xù)）舉例工件i1234Pi12163Pi24829Pi3548211131614CSa(2,1)Sb(4)所求順序：（2,1,3,4）華中科大管理學(xué)院陳榮秋馬士華179.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法（續(xù)）舉例工件i179.2.4相同零件不同移動(dòng)方式下加工周期的計(jì)算當(dāng)n個(gè)零件相同，則無排序問題。但不同移動(dòng)方式下的加工周期不同三種典型的移動(dòng)方式順序移動(dòng)方式：一批零件全部加工完成后，整批移動(dòng)到下道工序加工平行移動(dòng)方式：?jiǎn)蝹€(gè)零件加工完成后，立即移動(dòng)到下道工序加工平行順序移動(dòng)方式：兩者混合華中科大管理學(xué)院陳榮秋馬士華189.2.4相同零件不同移動(dòng)方式下加工周期的計(jì)算當(dāng)n個(gè)零件18順序移動(dòng)方式時(shí)間M1t2t1t3t4t4工序M2M3M4T順O華中科大管理學(xué)院陳榮秋馬士華19順序移動(dòng)方式時(shí)間M1t2t1t3t4工序M2M3M4T順O華19

設(shè)零件批量為n（件），工序數(shù)目為m，一批零件不計(jì)算工序間運(yùn)輸時(shí)間，只考慮加工時(shí)間，設(shè)其加工的周期為T（分鐘），零件在i道工序的單件工時(shí)為（分鐘/件），i=1.2…n.

則該批零件的加工周期為：

順序移動(dòng)方式（續(xù)）華中科大管理學(xué)院陳榮秋馬士華20設(shè)零件批量為n（件），工序數(shù)目為m，一批零件不計(jì)算工序20平行移動(dòng)方式時(shí)間M1工序M2M3M4T平Ot2t1t3t4華中科大管理學(xué)院陳榮秋馬士華21平行移動(dòng)方式時(shí)間M1工序M2M3M4T平Ot2t1t3t4華21平行移動(dòng)方式（續(xù)）零件平行移動(dòng)的加工周期為：

為最長單件工序時(shí)間華中科大管理學(xué)院陳榮秋馬士華22平行移動(dòng)方式（續(xù)）零件平行移動(dòng)的加工周期為：為最長22平行順序移動(dòng)方式

特點(diǎn)：既保持一批零件順序加工，有盡可能使相鄰工序加工時(shí)間平行進(jìn)行。如圖所示：時(shí)間M1工序M2M3M4T平順Ot1t2t3t4華中科大管理學(xué)院陳榮秋馬士華23平行順序移動(dòng)方式特點(diǎn)：既保持一批零件順序加工，23平行順序移動(dòng)方式（續(xù)）平行順序移動(dòng)加工周期計(jì)算

華中科大管理學(xué)院陳榮秋馬士華24平行順序移動(dòng)方式（續(xù)）平行順序移動(dòng)加工周期計(jì)算華中科249.3單件作業(yè)排序問題9.3.1任務(wù)分配問題9.3.2單件作業(yè)排序問題的描述9.3.3優(yōu)先派工準(zhǔn)則9.3.4求解一般n/m/G/Fmax問題的啟發(fā)式方法華中科大管理學(xué)院陳榮秋馬士華259.3單件作業(yè)排序問題9.3.1任務(wù)分配問題華中科大管理259.3.1任務(wù)分配問題M1M2M3M4

J1J2J3J4973578121146876111310有4個(gè)零件可以分配給4臺(tái)機(jī)器加工，其所需加工時(shí)間如圖所示。即，零件1分配給機(jī)器1加工，需要9個(gè)時(shí)間單位；分配給機(jī)器2加工，需要7個(gè)時(shí)間單位；分配給機(jī)器3加工，需要3個(gè)時(shí)間單位；分配給機(jī)器4加工，需要5個(gè)時(shí)間單位，等等。如果有n個(gè)零件要分配給n臺(tái)機(jī)器加工，則有n!種不同的分配方案。通過匈牙利算法可以較方便地找到最優(yōu)分配方案。華中科大管理學(xué)院陳榮秋馬士華269.3.1任務(wù)分配問題M1M2M3269.3.1任務(wù)分配問題（續(xù)）匈牙利算法(1)從加工時(shí)間(費(fèi)用)矩陣每一行所有元素減去該行最小的元素，使每行至少出現(xiàn)一個(gè)零元素。(2)從實(shí)施第(1)步得到的矩陣中的每一列所有元素減去該列最小的元素，使每列至少出現(xiàn)一個(gè)零元素。(3)從實(shí)施第(2)步得到的矩陣中，劃出能覆蓋盡可能多的零元素的直線，如果線條數(shù)等于矩陣的行數(shù)，則已找到最優(yōu)矩陣，轉(zhuǎn)第(6)步；否則，轉(zhuǎn)第(4)步。華中科大管理學(xué)院陳榮秋馬士華279.3.1任務(wù)分配問題（續(xù)）匈牙利算法華中科大管理學(xué)院陳榮279.3.1任務(wù)分配問題（續(xù)）(4)從矩陣中未被線條穿過的元素中減去這些元素中的最小數(shù)，并將這個(gè)最小數(shù)加到直線交叉的元素上，其余元素不變。(5)重復(fù)步驟(3)和步驟(4)，直到獲得最優(yōu)矩陣。（6）從僅有一個(gè)零的行或列開始，找出零元素對(duì)應(yīng)的分配方案，每行和每列僅能確定一個(gè)元素，最后使每行和每列都有一個(gè)零元素。零元素對(duì)應(yīng)的就是最優(yōu)分配方案。華中科大管理學(xué)院陳榮秋馬士華289.3.1任務(wù)分配問題（續(xù)）(4)從矩陣中未被線條穿過的元28M1M2M3M4J1J2J3J49735378121174687

461113106

(a)M1M2M3M4J1J2J3J464020154024305740102

(b)9.3.1任務(wù)分配問題（續(xù)）行最小數(shù)列最小數(shù)華中科大管理學(xué)院陳榮秋馬士華29M1M2M3M4J19729M1M2M3M4J1J2J3J4300005201410472(C)M1M2M3M4J1J2J3J430005200300361(d)9.3.1任務(wù)分配問題（續(xù)）華中科大管理學(xué)院陳榮秋馬士華30M1M2M3M4J1330M1M2M3M4J1J2J3J47300105300300361(ｅ)M1M2M3M4J1J2J3J430005300300361(ｆ)9.3.1任務(wù)分配問題（續(xù)）華中科大管理學(xué)院陳榮秋馬士華31M1M2M3M4J173319.3.2單件作業(yè)排序問題的描述D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345加工描述矩陣D和加工時(shí)間矩陣T對(duì)應(yīng)華中科大管理學(xué)院陳榮秋馬士華329.3.2單件作業(yè)排序問題的描述D=1,1,11,2,329.3.3優(yōu)先派工準(zhǔn)則按什么樣的法則來選擇可安排的工序，對(duì)作業(yè)計(jì)劃的優(yōu)劣有很大影響。迄今，人們已提出了100多個(gè)優(yōu)先派工法則，下面列出4個(gè)進(jìn)行比較：①

FCFS(FirstComeFirstServed)法則優(yōu)先選擇最早進(jìn)入可排工序集合的工件。②

SPT(ShortestProcessingTime)法則優(yōu)先選擇加工時(shí)間最短的工序。③

EDD(EarliestDueDate)法則優(yōu)先選擇完工期限緊的工件。④

LPT(LongestProcessingTime)法則優(yōu)先選擇加工時(shí)間最長的工件。華中科大管理學(xué)院陳榮秋馬士華339.3.3優(yōu)先派工準(zhǔn)則按什么樣的法則來選擇可安排的工序，對(duì)339.3.3優(yōu)先派工準(zhǔn)則（續(xù)）例：有6項(xiàng)任務(wù)A，B，C，D，E，F(xiàn)要完成。每項(xiàng)任務(wù)所需時(shí)間和完工期限如下表所示。分別按（1）FCFS，（2）SPT，（3）EDD和（4）LPT法則，來確定完成任務(wù)的先后次序及相應(yīng)的指標(biāo)。華中科大管理學(xué)院陳榮秋馬士華349.3.3優(yōu)先派工準(zhǔn)則（續(xù)）例：有6項(xiàng)任務(wù)A，B，C，D，349.3.3優(yōu)先派工準(zhǔn)則（續(xù)）如果任務(wù)下達(dá)的順序是A-B-C-D-E-F，按FCFS法則，任務(wù)的流程時(shí)間就是每件任務(wù)的等待時(shí)間加上加工時(shí)間。華中科大管理學(xué)院陳榮秋馬士華359.3.3優(yōu)先派工準(zhǔn)則（續(xù)）如果任務(wù)下達(dá)的順序是A-B-C359.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照FCFS法則，可以得到下列結(jié)果：①平均流程時(shí)間=累計(jì)流程時(shí)間/任務(wù)數(shù)=120/6=20天②利用率=累計(jì)加工時(shí)間/累計(jì)流程時(shí)間=41/120=34.2%③系統(tǒng)中平均在制品數(shù)量=累計(jì)流程時(shí)間/累計(jì)加工時(shí)間件任務(wù)④平均延遲時(shí)間=延遲時(shí)間總和/任務(wù)數(shù)=54/6=9天華中科大管理學(xué)院陳榮秋馬士華369.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照FCFS法則，可以得到下369.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按SPT法則，處理任務(wù)的的流程時(shí)間就是每件任務(wù)的等待時(shí)間加上加工時(shí)間。華中科大管理學(xué)院陳榮秋馬士華379.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按SPT法則，處理任務(wù)的的流程379.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照SPT法則，得到下列結(jié)果：①平均流程時(shí)間=108/6=18天②利用率=41/108=38%③系統(tǒng)中平均在制品數(shù)量件任務(wù)④平均延遲時(shí)間天華中科大管理學(xué)院陳榮秋馬士華389.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照SPT法則，得到下列結(jié)果：389.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按EDD法則，處理任務(wù)的先后次序是C-A-E-B-D-F，如下表所示。

華中科大管理學(xué)院陳榮秋馬士華399.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按EDD法則，處理任務(wù)的先后次399.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照EDD法則，得到下列結(jié)果：①平均流程時(shí)間天②利用率=41/110=37.3%③系統(tǒng)中平均在制品數(shù)量件任務(wù)④任務(wù)平均延遲時(shí)間天華中科大管理學(xué)院陳榮秋馬士華409.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照EDD法則，得到下列結(jié)果：409.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按LPT法則，處理任務(wù)的先后次序是F-D-B-E-C-A，如下表所示。

華中科大管理學(xué)院陳榮秋馬士華419.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按LPT法則，處理任務(wù)的先后次419.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照LPT法則，得到下列結(jié)果：①平均流程時(shí)間天②利用率=41/179=22.9%③系統(tǒng)中平均在制品數(shù)量件任務(wù)④任務(wù)平均延遲時(shí)間=108/6=18天華中科大管理學(xué)院陳榮秋馬士華429.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照LPT法則，得到下列結(jié)果：429.3.3優(yōu)先派工準(zhǔn)則（續(xù)）（1）按照LPT法則進(jìn)行作業(yè)排序，各項(xiàng)指標(biāo)最差。（2）按SPT法則可使工件的平均流程時(shí)間最短，使平均在制品數(shù)量最少。（3）FCFS法則對(duì)工件較公平，這一點(diǎn)在對(duì)顧客服務(wù)中尤其重要，但在多數(shù)情況下都不具有優(yōu)勢(shì)。（4）EDD法則可使工件的平均延遲時(shí)間最小，其它指標(biāo)也不錯(cuò)。華中科大管理學(xué)院陳榮秋馬士華439.3.3優(yōu)先派工準(zhǔn)則（續(xù)）（1）按照LPT法則進(jìn)行作業(yè)排43求解一般n/m/G/Fmax問題的啟發(fā)式方法（1）兩種作業(yè)計(jì)劃的構(gòu)成能動(dòng)作業(yè)計(jì)劃無延遲作業(yè)計(jì)劃（2）三類啟發(fā)式算法運(yùn)用優(yōu)先派工法則隨即抽樣法概率調(diào)度法華中科大管理學(xué)院陳榮秋馬士華44求解一般n/m/G/Fmax問題的啟發(fā)式方法（1）兩種作業(yè)計(jì)44（1）兩種作業(yè)計(jì)劃的構(gòu)成符號(hào)說明每安排一道工序稱為一“步”{St}:t步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃；{Ot}:t步可排序工序的集合；Tk為{Ot}中工序Ok的最早可能開始時(shí)間；T’k為{Ot}中工序Ok的最早可能完成時(shí)間。華中科大管理學(xué)院陳榮秋馬士華45（1）兩種作業(yè)計(jì)劃的構(gòu)成符號(hào)說明華中科大管理學(xué)院陳榮秋馬士華45（1）兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）能動(dòng)作業(yè)計(jì)劃的構(gòu)成（1）設(shè)t=1,{S1}為空集，{O1}為各工件第一道工序的集合。（2）求T*=min{T’k},并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺(tái)，則任選一臺(tái)。（3）從{Ot}中選出滿足以下兩個(gè)條件的工序Oj：需要M*加工，且Tj<T*

。（4）將選定的工序Oj放入{St},從{Ot}中消去Oj,并將Oj的緊后工序放入{Ot}，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。華中科大管理學(xué)院陳榮秋馬士華46（1）兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）能動(dòng)作業(yè)計(jì)劃的構(gòu)成華中科大管46能動(dòng)作業(yè)計(jì)劃的構(gòu)成華中科大管理學(xué)院陳榮秋馬士華47能動(dòng)作業(yè)計(jì)劃的構(gòu)成華中科大管理學(xué)院陳榮秋馬士華4747能動(dòng)作業(yè)計(jì)劃的甘特圖2,3,21,1,12,2,11,3,22,1,31,2,33778132370時(shí)間機(jī)器M1M2M3華中科大管理學(xué)院陳榮秋馬士華48能動(dòng)作業(yè)計(jì)劃的甘特圖2,3,21,1,12,489.3.2兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）無延遲作業(yè)計(jì)劃的構(gòu)成（1）設(shè)t=1,{S1}為空集，{O1}為各工件第一道工序的集合。（2）求T*=min{Tk},并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺(tái)，則任選一臺(tái)。（3）從{Ot}中選出滿足以下兩個(gè)條件的工序Oj：需要M*加工，且Tj=T*

。（4）將選定的工序Oj放入{St},從{Ot}中消去Oj,并將Oj的緊后工序放入{Ot}，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。華中科大管理學(xué)院陳榮秋馬士華499.3.2兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）無延遲作業(yè)計(jì)劃的構(gòu)成華中49無延遲作業(yè)計(jì)劃的構(gòu)成華中科大管理學(xué)院陳榮秋馬士華50無延遲作業(yè)計(jì)劃的構(gòu)成華中科大管理學(xué)院陳榮秋馬士華5050無延遲作業(yè)計(jì)劃的甘特圖2,3,21,1,12,2,12,1,31,2,337712132370時(shí)間機(jī)器M1M2M31,3,2華中科大管理學(xué)院陳榮秋馬士華51無延遲作業(yè)計(jì)劃的甘特圖2,3,21,1,1251（2）三類啟發(fā)式算法優(yōu)先調(diào)度法則構(gòu)成兩種作業(yè)計(jì)劃的第（3）步一般都有多道工序可以滿足，按不同的優(yōu)先調(diào)度法則來選擇工序，可以得出滿足不同目標(biāo)函數(shù)的作業(yè)計(jì)劃計(jì)算量小已經(jīng)提出100多種優(yōu)先調(diào)度法則華中科大管理學(xué)院陳榮秋馬士華52（2）三類啟發(fā)式算法優(yōu)先調(diào)度法則華中科大管理學(xué)院陳榮秋馬士華52優(yōu)先調(diào)度法則FCFS（firstcome,firstserved）選擇最早進(jìn)入可排序集合的工序SPT(shortestprocessingtime）選擇加工時(shí)間最短的工序EDD（earliestduedate）選擇完工期限最緊的工序SCR(smallestcriticalratio)選擇臨界比最小的工件MWKR(mostworkremaining)選擇余下加工時(shí)間最長的工件LWKR(leastworkremaining)選擇余下加工時(shí)間最短的工件MOPNR(mostoperationsremaining)選擇余下工序數(shù)最多的工件RANDOM隨機(jī)挑選一個(gè)工件RushTopPriority華中科大管理學(xué)院陳榮秋馬士華53優(yōu)先調(diào)度法則TopPriority華中科大管理學(xué)院陳榮秋馬53（2）三類啟發(fā)式算法（續(xù)）隨機(jī)抽樣法從全部能動(dòng)計(jì)劃或無延遲計(jì)劃中隨機(jī)抽樣，得出多個(gè)作業(yè)計(jì)劃，從中取優(yōu)。概率調(diào)度法將優(yōu)先調(diào)度法則與隨機(jī)抽樣法結(jié)合對(duì)不同工件將優(yōu)先調(diào)度法則分配不同的挑選概率，效果較好華中科大管理學(xué)院陳榮秋馬士華54（2）三類啟發(fā)式算法（續(xù)）隨機(jī)抽樣法華中科大管理學(xué)院陳榮秋馬549.4生產(chǎn)作業(yè)控制實(shí)行生產(chǎn)作業(yè)控制的原因生產(chǎn)環(huán)境的變化計(jì)劃的失誤執(zhí)行的原因：執(zhí)行過程中，有可能會(huì)出現(xiàn)操作人員執(zhí)行不力、效率不高和工作態(tài)度等現(xiàn)象，造成計(jì)劃完不成執(zhí)行因素的影響華中科大管理學(xué)院陳榮秋馬士華559.4生產(chǎn)作業(yè)控制實(shí)行生產(chǎn)作業(yè)控制的原因華中科大管理學(xué)院陳559.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的程序制定生產(chǎn)作業(yè)監(jiān)控體系監(jiān)控實(shí)際生產(chǎn)過程評(píng)估偏差情況采取糾偏措施華中科大管理學(xué)院陳榮秋馬士華569.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的程序制定生產(chǎn)作569.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的功能為每個(gè)車間的工單指派優(yōu)先級(jí)維護(hù)車間在制品數(shù)量將車間工單信息傳送到相應(yīng)辦公室提供實(shí)際產(chǎn)出數(shù)據(jù)來為能力控制服務(wù)根據(jù)車間工單對(duì)機(jī)位的要求，為在制品庫存管理提供數(shù)量信息測(cè)量人員和設(shè)備的效率、利用率和產(chǎn)量。華中科大管理學(xué)院陳榮秋馬士華579.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的功能為每個(gè)車間57華中科大管理學(xué)院陳榮秋馬士華58華中科大管理學(xué)院陳榮秋馬士華58589.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的主要工具實(shí)際生產(chǎn)中，有不少工具可以用來進(jìn)行生產(chǎn)作業(yè)控制，這些工具容易通過運(yùn)用適當(dāng)?shù)能浖砩?，主要包括：調(diào)度單日?qǐng)?bào)、月報(bào)例外報(bào)告、異常報(bào)告輸入/輸出（Input/outputcontrol，I/O）報(bào)告華中科大管理學(xué)院陳榮秋馬士華599.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的主要工具實(shí)際生599.4生產(chǎn)作業(yè)控制（續(xù)）漏斗模型模型介紹德國漢諾威大學(xué)的Bechte和Wiendall等人于20世紀(jì)80年代初在實(shí)施輸入/輸出控制時(shí)提出了漏斗模型（FunnelModel）。漏斗模型的基本原則：工作中心的輸入永遠(yuǎn)不能超過工作中心的輸出。當(dāng)工作中心的輸入超過輸出，就會(huì)拖欠訂單，結(jié)果將會(huì)出現(xiàn)作業(yè)推遲、客戶不滿、下游作業(yè)或相關(guān)作業(yè)的延期。華中科大管理學(xué)院陳榮秋馬士華609.4生產(chǎn)作業(yè)控制（續(xù)）漏斗模型模型介紹華中科大管理60注：曲線圖的垂直段表示某天到達(dá)或完成的一個(gè)或多個(gè)工件之間所包含的工作量；水平段表示相鄰兩個(gè)到達(dá)或完成的任務(wù)之間的時(shí)間間隔。如果運(yùn)輸時(shí)間不變，輸入曲線與上道工序的輸出曲線相對(duì)應(yīng)。華中科大管理學(xué)院陳榮秋馬士華61注：曲線圖的垂直段表示某天到達(dá)或完成的一個(gè)或多個(gè)工件之間所包619.4生產(chǎn)作業(yè)控制（續(xù)）控制規(guī)則在一段較長的時(shí)間內(nèi)（如數(shù)周）內(nèi)，若工況穩(wěn)定，輸入輸出兩條曲線可以近似地用兩條直線來表示，其斜率（平均生產(chǎn)率）等于平均在制品庫存/平均通過時(shí)間實(shí)際實(shí)踐中，可以采用四個(gè)規(guī)則來調(diào)整輸入、輸出、在制品庫存和通過時(shí)間：若希望保持在制品庫存量，可暫時(shí)增加或減少輸入。若希望改變?cè)谥破穾齑媪?，可暫時(shí)增加或減少輸入。若希望平均通過時(shí)間在所控制的范圍內(nèi)，則適當(dāng)調(diào)整平均在制品庫存與生產(chǎn)率的比例。要使各個(gè)工件的平均通過時(shí)間穩(wěn)定，可以采用FIFO規(guī)則來安排各工件的加工順序。華中科大管理學(xué)院陳榮秋馬士華629.4生產(chǎn)作業(yè)控制（續(xù)）控制規(guī)則在一段較長的時(shí)間內(nèi)（62謝謝！華中科大管理學(xué)院陳榮秋馬士華63謝謝！華中科大管理學(xué)院陳榮秋馬士華6363生產(chǎn)與運(yùn)作管理

Production&OperationsManagement華中科技大學(xué)管理學(xué)院TheSchoolofManagement，HUST陳榮秋馬士華RongqiuChenandShihuaMa華中科大管理學(xué)院陳榮秋馬士華64生產(chǎn)與運(yùn)作管理

Production&Operation64第9章制造業(yè)作業(yè)計(jì)劃與控制SchedulingandControllingforManufacturing9.1作業(yè)計(jì)劃問題的基本概念9.2流水作業(yè)排序問題9.3單件作業(yè)的排序問題9.4生產(chǎn)作業(yè)控制

華中科大管理學(xué)院陳榮秋馬士華65第9章制造業(yè)作業(yè)計(jì)劃與控制SchedulingandC65作業(yè)計(jì)劃問題的基本概念編制作業(yè)計(jì)劃要解決的問題編制作業(yè)計(jì)劃實(shí)質(zhì)上是要將資源分配給不同的任務(wù)，按照既定的優(yōu)化目標(biāo)，確定各種資源利用的時(shí)間問題。由于每臺(tái)機(jī)器都可能被分配了多項(xiàng)任務(wù)，而這些任務(wù)受到加工路線的約束，就帶來了零件在機(jī)器上加工的順序問題。有關(guān)名詞術(shù)語9.1.2假設(shè)條件與符號(hào)說明華中科大管理學(xué)院陳榮秋馬士華66作業(yè)計(jì)劃問題的基本概念編制作業(yè)計(jì)劃要解決的問題華中科大管理學(xué)66

9.1.1有關(guān)的名詞術(shù)語編制作業(yè)計(jì)劃或排程(Scheduling)排序(Sequencing)派工(Dispatching)控制(Controlling)趕工(Expediting)“調(diào)度”是作業(yè)計(jì)劃編制后實(shí)施生產(chǎn)控制所采取的一切行動(dòng)，“編制作業(yè)計(jì)劃”是加工制造發(fā)生之前的活動(dòng)，屬于計(jì)劃范疇。華中科大管理學(xué)院陳榮秋馬士華679.1.1有關(guān)的名詞術(shù)語編制作業(yè)計(jì)劃或排程(Schedu67有關(guān)名詞術(shù)語（續(xù)）“機(jī)器”，可以是工廠里的各種機(jī)床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計(jì)算機(jī)中央處理單元、存貯器和輸入、輸出單元。一句話，表示“服務(wù)者”?！傲慵贝怼胺?wù)對(duì)象”。零件可以是單個(gè)零件，也可以是一批相同的零件?！凹庸ぢ肪€”是零件加工的工藝過程決定的，它是零件加工在技術(shù)上的約束。“加工順序”則表示每臺(tái)機(jī)器加工n個(gè)零件的先后順序，是排序和編制作業(yè)計(jì)劃要解決的問題。華中科大管理學(xué)院陳榮秋馬士華68有關(guān)名詞術(shù)語（續(xù)）“機(jī)器”，可以是工廠里的各種機(jī)床，也可以是689.1.2假設(shè)條件與符號(hào)說明假設(shè)條件①一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工。②工件在加工過程中采取平行移動(dòng)方式，即當(dāng)上一道工序完工后，立即送下道工序加工。③不允許中斷。當(dāng)一個(gè)工件一旦開始加工，必須一直進(jìn)行到完工，不得中途停止插入其它工件。④每道工序只在一臺(tái)機(jī)器上完成。⑤工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無關(guān)。⑥每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。華中科大管理學(xué)院陳榮秋馬士華699.1.2假設(shè)條件與符號(hào)說明假設(shè)條件華中科大管理學(xué)院陳榮秋699.1.2假設(shè)條件與符號(hào)說明（續(xù)）符號(hào)說明Ji─工件i，i＝1,2,…,n。Mj─機(jī)器j，j＝1,2,…,m。pij─Ji在Mj上的加工時(shí)間，Ji的總加工時(shí)間為Pi＝∑pijri─Ji的到達(dá)時(shí)間，或準(zhǔn)備就緒時(shí)間，指Ji從外部進(jìn)入車間，可以開始加工的最早時(shí)間。di─Ji的完工期限。Ci─Ji的完工時(shí)間,Ci＝ri＋∑(wij+pij)=ri+Wi+Pi.Cmax─最長完工時(shí)間,Cmax＝max{Ci}.華中科大管理學(xué)院陳榮秋馬士華709.1.2假設(shè)條件與符號(hào)說明（續(xù)）符號(hào)說明華中科大管理學(xué)院709.1.2假設(shè)條件與符號(hào)說明（續(xù)）Fi─Ji的流程時(shí)間，即工件在車間的實(shí)際停留時(shí)間,Fi＝CI-ri＝Wi+Pi.Fmax─最長流程時(shí)間，F(xiàn)max＝max{Fi}.Li─工件延遲時(shí)間，Li＝Ci－di＝ri＋Pi.+Wi－di＝(Pi.+Wi)－(di-ri)＝Fi－ai.當(dāng)Li＞0(正延遲)，說明Ji的實(shí)際完工時(shí)間超過了完工期限；當(dāng)Li＜0(負(fù)延遲)，說明Ji提前完工；當(dāng)Li＝0(零延遲)，Ji按期完工。Lmax─最長延遲時(shí)間，Lmax＝max{Li}.華中科大管理學(xué)院陳榮秋馬士華719.1.2假設(shè)條件與符號(hào)說明（續(xù)）Fi─Ji的流程時(shí)間，即719.2流水作業(yè)排序問題流水車間(Flowshop):工件的加工路線都一致，典型的如流水線9.2.1最長流程時(shí)間的計(jì)算9.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法9.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法相同零件、不同移動(dòng)方式下加工周期的計(jì)算Work

Center#1WorkCenter#2Output華中科大管理學(xué)院陳榮秋馬士華729.2流水作業(yè)排序問題流水車間(Flowshop):工件729.2.1最長流程時(shí)間的計(jì)算工件代號(hào)i146352Pi1453486Pi2391375Pi3768259Pi4563924491216243071819223136142432343948193035444652華中科大管理學(xué)院陳榮秋馬士華739.2.1最長流程時(shí)間的計(jì)算工件代號(hào)i1739.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法約翰森法則如果Min(ai,bj)<Min(aj,bi),則工件i應(yīng)該排在工件j之前。約翰森算法（1）從加工時(shí)間矩陣中找出最短加工時(shí)間；（2）若最短加工時(shí)間出現(xiàn)在機(jī)器M1

上，則對(duì)應(yīng)工件應(yīng)該盡可能往前排；若最短加工時(shí)間出現(xiàn)在機(jī)器M2

上，則對(duì)應(yīng)工件應(yīng)該盡可能往后排。華中科大管理學(xué)院陳榮秋馬士華749.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法約翰森法則華中科大管749.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）然后從加工時(shí)間矩陣中劃去已排序工件的加工時(shí)間。若最短加工時(shí)間有多個(gè)，則任挑一個(gè)。（3）若所有工件都已排序，停止。否則，轉(zhuǎn)步驟（1）。華中科大管理學(xué)院陳榮秋馬士華759.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）然后從加工時(shí)間75將工件2排在第1位2將工件3排在第6位2

3將工件5排在第2位2

5

3將工件6排在第3位2

5

6

3將工件4排在第5位2

5

6

4

3將工件1排在第4位2

5

6

1

4

3最優(yōu)加工順序?yàn)镾=(2,5,6,1,4,3),Fmax=28I123456Ai518534Bi7224749.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）華中科大管理學(xué)院陳榮秋馬士華76將工件2排在第1位2I769.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）Johnson算法的改進(jìn)1.將所有ai≤

bi的工件按ai值不減的順序排成一個(gè)序列A；2.將ai＞bi的工件按bi值不增的順序排成一個(gè)序列B；3.將A放到B之前，就構(gòu)成了一個(gè)最優(yōu)加工順序。華中科大管理學(xué)院陳榮秋馬士華779.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）Johnso779.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）舉例工件號(hào)123456ai518534bi722474工件最優(yōu)順序：256143

1345582747424

8

13

18

2631115222628aibi

最優(yōu)順序下的加工周期為28華中科大管理學(xué)院陳榮秋馬士華789.2.2兩臺(tái)機(jī)器排序問題的最優(yōu)算法（續(xù)）舉例工件號(hào)789.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法關(guān)鍵工件法1.計(jì)算每個(gè)工件的總加工時(shí)間，將加工時(shí)間最長的工件作為關(guān)鍵工件C；2.對(duì)于余下的工件，若pi1≤pim則按pi1不減的順序排成一個(gè)序列Sa

,若pi1>pim

則按pim不增的順序排成一個(gè)序列Sb;3.順序（Sa,C,Sb）即為所求順序。華中科大管理學(xué)院陳榮秋馬士華799.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法關(guān)鍵工件法華中科大799.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法（續(xù)）舉例工件i1234Pi12163Pi24829Pi3548211131614CSa(2,1)Sb(4)所求順序：（2,1,3,4）華中科大管理學(xué)院陳榮秋馬士華809.2.3多臺(tái)機(jī)器排序問題的啟發(fā)式算法（續(xù)）舉例工件i809.2.4相同零件不同移動(dòng)方式下加工周期的計(jì)算當(dāng)n個(gè)零件相同，則無排序問題。但不同移動(dòng)方式下的加工周期不同三種典型的移動(dòng)方式順序移動(dòng)方式：一批零件全部加工完成后，整批移動(dòng)到下道工序加工平行移動(dòng)方式：?jiǎn)蝹€(gè)零件加工完成后，立即移動(dòng)到下道工序加工平行順序移動(dòng)方式：兩者混合華中科大管理學(xué)院陳榮秋馬士華819.2.4相同零件不同移動(dòng)方式下加工周期的計(jì)算當(dāng)n個(gè)零件81順序移動(dòng)方式時(shí)間M1t2t1t3t4t4工序M2M3M4T順O華中科大管理學(xué)院陳榮秋馬士華82順序移動(dòng)方式時(shí)間M1t2t1t3t4工序M2M3M4T順O華82

設(shè)零件批量為n（件），工序數(shù)目為m，一批零件不計(jì)算工序間運(yùn)輸時(shí)間，只考慮加工時(shí)間，設(shè)其加工的周期為T（分鐘），零件在i道工序的單件工時(shí)為（分鐘/件），i=1.2…n.

則該批零件的加工周期為：

順序移動(dòng)方式（續(xù)）華中科大管理學(xué)院陳榮秋馬士華83設(shè)零件批量為n（件），工序數(shù)目為m，一批零件不計(jì)算工序83平行移動(dòng)方式時(shí)間M1工序M2M3M4T平Ot2t1t3t4華中科大管理學(xué)院陳榮秋馬士華84平行移動(dòng)方式時(shí)間M1工序M2M3M4T平Ot2t1t3t4華84平行移動(dòng)方式（續(xù)）零件平行移動(dòng)的加工周期為：

為最長單件工序時(shí)間華中科大管理學(xué)院陳榮秋馬士華85平行移動(dòng)方式（續(xù)）零件平行移動(dòng)的加工周期為：為最長85平行順序移動(dòng)方式

特點(diǎn)：既保持一批零件順序加工，有盡可能使相鄰工序加工時(shí)間平行進(jìn)行。如圖所示：時(shí)間M1工序M2M3M4T平順Ot1t2t3t4華中科大管理學(xué)院陳榮秋馬士華86平行順序移動(dòng)方式特點(diǎn)：既保持一批零件順序加工，86平行順序移動(dòng)方式（續(xù)）平行順序移動(dòng)加工周期計(jì)算

華中科大管理學(xué)院陳榮秋馬士華87平行順序移動(dòng)方式（續(xù)）平行順序移動(dòng)加工周期計(jì)算華中科879.3單件作業(yè)排序問題9.3.1任務(wù)分配問題9.3.2單件作業(yè)排序問題的描述9.3.3優(yōu)先派工準(zhǔn)則9.3.4求解一般n/m/G/Fmax問題的啟發(fā)式方法華中科大管理學(xué)院陳榮秋馬士華889.3單件作業(yè)排序問題9.3.1任務(wù)分配問題華中科大管理889.3.1任務(wù)分配問題M1M2M3M4

J1J2J3J4973578121146876111310有4個(gè)零件可以分配給4臺(tái)機(jī)器加工，其所需加工時(shí)間如圖所示。即，零件1分配給機(jī)器1加工，需要9個(gè)時(shí)間單位；分配給機(jī)器2加工，需要7個(gè)時(shí)間單位；分配給機(jī)器3加工，需要3個(gè)時(shí)間單位；分配給機(jī)器4加工，需要5個(gè)時(shí)間單位，等等。如果有n個(gè)零件要分配給n臺(tái)機(jī)器加工，則有n!種不同的分配方案。通過匈牙利算法可以較方便地找到最優(yōu)分配方案。華中科大管理學(xué)院陳榮秋馬士華899.3.1任務(wù)分配問題M1M2M3899.3.1任務(wù)分配問題（續(xù)）匈牙利算法(1)從加工時(shí)間(費(fèi)用)矩陣每一行所有元素減去該行最小的元素，使每行至少出現(xiàn)一個(gè)零元素。(2)從實(shí)施第(1)步得到的矩陣中的每一列所有元素減去該列最小的元素，使每列至少出現(xiàn)一個(gè)零元素。(3)從實(shí)施第(2)步得到的矩陣中，劃出能覆蓋盡可能多的零元素的直線，如果線條數(shù)等于矩陣的行數(shù)，則已找到最優(yōu)矩陣，轉(zhuǎn)第(6)步；否則，轉(zhuǎn)第(4)步。華中科大管理學(xué)院陳榮秋馬士華909.3.1任務(wù)分配問題（續(xù)）匈牙利算法華中科大管理學(xué)院陳榮909.3.1任務(wù)分配問題（續(xù)）(4)從矩陣中未被線條穿過的元素中減去這些元素中的最小數(shù)，并將這個(gè)最小數(shù)加到直線交叉的元素上，其余元素不變。(5)重復(fù)步驟(3)和步驟(4)，直到獲得最優(yōu)矩陣。（6）從僅有一個(gè)零的行或列開始，找出零元素對(duì)應(yīng)的分配方案，每行和每列僅能確定一個(gè)元素，最后使每行和每列都有一個(gè)零元素。零元素對(duì)應(yīng)的就是最優(yōu)分配方案。華中科大管理學(xué)院陳榮秋馬士華919.3.1任務(wù)分配問題（續(xù)）(4)從矩陣中未被線條穿過的元91M1M2M3M4J1J2J3J49735378121174687

461113106

(a)M1M2M3M4J1J2J3J464020154024305740102

(b)9.3.1任務(wù)分配問題（續(xù)）行最小數(shù)列最小數(shù)華中科大管理學(xué)院陳榮秋馬士華92M1M2M3M4J19792M1M2M3M4J1J2J3J4300005201410472(C)M1M2M3M4J1J2J3J430005200300361(d)9.3.1任務(wù)分配問題（續(xù)）華中科大管理學(xué)院陳榮秋馬士華93M1M2M3M4J1393M1M2M3M4J1J2J3J47300105300300361(ｅ)M1M2M3M4J1J2J3J430005300300361(ｆ)9.3.1任務(wù)分配問題（續(xù)）華中科大管理學(xué)院陳榮秋馬士華94M1M2M3M4J173949.3.2單件作業(yè)排序問題的描述D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345加工描述矩陣D和加工時(shí)間矩陣T對(duì)應(yīng)華中科大管理學(xué)院陳榮秋馬士華959.3.2單件作業(yè)排序問題的描述D=1,1,11,2,959.3.3優(yōu)先派工準(zhǔn)則按什么樣的法則來選擇可安排的工序，對(duì)作業(yè)計(jì)劃的優(yōu)劣有很大影響。迄今，人們已提出了100多個(gè)優(yōu)先派工法則，下面列出4個(gè)進(jìn)行比較：①

FCFS(FirstComeFirstServed)法則優(yōu)先選擇最早進(jìn)入可排工序集合的工件。②

SPT(ShortestProcessingTime)法則優(yōu)先選擇加工時(shí)間最短的工序。③

EDD(EarliestDueDate)法則優(yōu)先選擇完工期限緊的工件。④

LPT(LongestProcessingTime)法則優(yōu)先選擇加工時(shí)間最長的工件。華中科大管理學(xué)院陳榮秋馬士華969.3.3優(yōu)先派工準(zhǔn)則按什么樣的法則來選擇可安排的工序，對(duì)969.3.3優(yōu)先派工準(zhǔn)則（續(xù)）例：有6項(xiàng)任務(wù)A，B，C，D，E，F(xiàn)要完成。每項(xiàng)任務(wù)所需時(shí)間和完工期限如下表所示。分別按（1）FCFS，（2）SPT，（3）EDD和（4）LPT法則，來確定完成任務(wù)的先后次序及相應(yīng)的指標(biāo)。華中科大管理學(xué)院陳榮秋馬士華979.3.3優(yōu)先派工準(zhǔn)則（續(xù)）例：有6項(xiàng)任務(wù)A，B，C，D，979.3.3優(yōu)先派工準(zhǔn)則（續(xù)）如果任務(wù)下達(dá)的順序是A-B-C-D-E-F，按FCFS法則，任務(wù)的流程時(shí)間就是每件任務(wù)的等待時(shí)間加上加工時(shí)間。華中科大管理學(xué)院陳榮秋馬士華989.3.3優(yōu)先派工準(zhǔn)則（續(xù)）如果任務(wù)下達(dá)的順序是A-B-C989.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照FCFS法則，可以得到下列結(jié)果：①平均流程時(shí)間=累計(jì)流程時(shí)間/任務(wù)數(shù)=120/6=20天②利用率=累計(jì)加工時(shí)間/累計(jì)流程時(shí)間=41/120=34.2%③系統(tǒng)中平均在制品數(shù)量=累計(jì)流程時(shí)間/累計(jì)加工時(shí)間件任務(wù)④平均延遲時(shí)間=延遲時(shí)間總和/任務(wù)數(shù)=54/6=9天華中科大管理學(xué)院陳榮秋馬士華999.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照FCFS法則，可以得到下999.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按SPT法則，處理任務(wù)的的流程時(shí)間就是每件任務(wù)的等待時(shí)間加上加工時(shí)間。華中科大管理學(xué)院陳榮秋馬士華1009.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按SPT法則，處理任務(wù)的的流程1009.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照SPT法則，得到下列結(jié)果：①平均流程時(shí)間=108/6=18天②利用率=41/108=38%③系統(tǒng)中平均在制品數(shù)量件任務(wù)④平均延遲時(shí)間天華中科大管理學(xué)院陳榮秋馬士華1019.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照SPT法則，得到下列結(jié)果：1019.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按EDD法則，處理任務(wù)的先后次序是C-A-E-B-D-F，如下表所示。

華中科大管理學(xué)院陳榮秋馬士華1029.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按EDD法則，處理任務(wù)的先后次1029.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照EDD法則，得到下列結(jié)果：①平均流程時(shí)間天②利用率=41/110=37.3%③系統(tǒng)中平均在制品數(shù)量件任務(wù)④任務(wù)平均延遲時(shí)間天華中科大管理學(xué)院陳榮秋馬士華1039.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照EDD法則，得到下列結(jié)果：1039.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按LPT法則，處理任務(wù)的先后次序是F-D-B-E-C-A，如下表所示。

華中科大管理學(xué)院陳榮秋馬士華1049.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按LPT法則，處理任務(wù)的先后次1049.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照LPT法則，得到下列結(jié)果：①平均流程時(shí)間天②利用率=41/179=22.9%③系統(tǒng)中平均在制品數(shù)量件任務(wù)④任務(wù)平均延遲時(shí)間=108/6=18天華中科大管理學(xué)院陳榮秋馬士華1059.3.3優(yōu)先派工準(zhǔn)則（續(xù)）按照LPT法則，得到下列結(jié)果：1059.3.3優(yōu)先派工準(zhǔn)則（續(xù)）（1）按照LPT法則進(jìn)行作業(yè)排序，各項(xiàng)指標(biāo)最差。（2）按SPT法則可使工件的平均流程時(shí)間最短，使平均在制品數(shù)量最少。（3）FCFS法則對(duì)工件較公平，這一點(diǎn)在對(duì)顧客服務(wù)中尤其重要，但在多數(shù)情況下都不具有優(yōu)勢(shì)。（4）EDD法則可使工件的平均延遲時(shí)間最小，其它指標(biāo)也不錯(cuò)。華中科大管理學(xué)院陳榮秋馬士華1069.3.3優(yōu)先派工準(zhǔn)則（續(xù)）（1）按照LPT法則進(jìn)行作業(yè)排106求解一般n/m/G/Fmax問題的啟發(fā)式方法（1）兩種作業(yè)計(jì)劃的構(gòu)成能動(dòng)作業(yè)計(jì)劃無延遲作業(yè)計(jì)劃（2）三類啟發(fā)式算法運(yùn)用優(yōu)先派工法則隨即抽樣法概率調(diào)度法華中科大管理學(xué)院陳榮秋馬士華107求解一般n/m/G/Fmax問題的啟發(fā)式方法（1）兩種作業(yè)計(jì)107（1）兩種作業(yè)計(jì)劃的構(gòu)成符號(hào)說明每安排一道工序稱為一“步”{St}:t步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃；{Ot}:t步可排序工序的集合；Tk為{Ot}中工序Ok的最早可能開始時(shí)間；T’k為{Ot}中工序Ok的最早可能完成時(shí)間。華中科大管理學(xué)院陳榮秋馬士華108（1）兩種作業(yè)計(jì)劃的構(gòu)成符號(hào)說明華中科大管理學(xué)院陳榮秋馬士華108（1）兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）能動(dòng)作業(yè)計(jì)劃的構(gòu)成（1）設(shè)t=1,{S1}為空集，{O1}為各工件第一道工序的集合。（2）求T*=min{T’k},并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺(tái)，則任選一臺(tái)。（3）從{Ot}中選出滿足以下兩個(gè)條件的工序Oj：需要M*加工，且Tj<T*

。（4）將選定的工序Oj放入{St},從{Ot}中消去Oj,并將Oj的緊后工序放入{Ot}，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。華中科大管理學(xué)院陳榮秋馬士華109（1）兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）能動(dòng)作業(yè)計(jì)劃的構(gòu)成華中科大管109能動(dòng)作業(yè)計(jì)劃的構(gòu)成華中科大管理學(xué)院陳榮秋馬士華110能動(dòng)作業(yè)計(jì)劃的構(gòu)成華中科大管理學(xué)院陳榮秋馬士華47110能動(dòng)作業(yè)計(jì)劃的甘特圖2,3,21,1,12,2,11,3,22,1,31,2,33778132370時(shí)間機(jī)器M1M2M3華中科大管理學(xué)院陳榮秋馬士華111能動(dòng)