生產(chǎn)與運作管理chapt制造業(yè)作業(yè)計劃

第11章制造業(yè)作業(yè)計劃與控制SchedulingandControllingforManufacturing11.1作業(yè)計劃問題的基本概念11.2流水作業(yè)排序問題11.3單件作業(yè)的排序問題11.4生產(chǎn)作業(yè)控制

第一頁，共四十一頁。1華中科大管理學(xué)院陳榮秋馬士華11.1作業(yè)計劃問題的基本概念編制作業(yè)計劃要解決的問題編制作業(yè)計劃實質(zhì)上是要將資源分配給不同的任務(wù)，按照既定的優(yōu)化目標(biāo)，確定各種資源利用的時間問題。由于每臺機器都可能被分配了多項任務(wù)，而這些任務(wù)受到加工路線的約束，就帶來了零件在機器上加工的順序問題。第二頁，共四十一頁。2華中科大管理學(xué)院陳榮秋馬士華11.1作業(yè)計劃問題的基本概念（續(xù)）有關(guān)的名詞術(shù)語編制作業(yè)計劃或日程安排(Scheduling)排序(Sequencing)派工(Dispatching)控制(Controlling)趕工(Expediting)“調(diào)度”是作業(yè)計劃編制后實施生產(chǎn)控制所采取的一切行動，“編制作業(yè)計劃”是加工制造發(fā)生之前的活動第三頁，共四十一頁。3華中科大管理學(xué)院陳榮秋馬士華11.1作業(yè)計劃問題的基本概念（續(xù)）“機器”，可以是工廠里的各種機床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計算機中央處理單元、存貯器和輸入、輸出單元。一句話，表示“服務(wù)者”“零件”代表“服務(wù)對象”。零件可以是單個零件，也可以是一批相同的零件“加工路線”是零件加工的工藝過程決定的，它是零件加工在技術(shù)上的約束“加工順序”則表示每臺機器加工n個零件的先后順序，是排序和編制作業(yè)計劃要解決的問題第四頁，共四十一頁。4華中科大管理學(xué)院陳榮秋馬士華11.2流水作業(yè)排序問題流水車間(Flowshop):工件的加工路線都一致，典型的如流水線11.2.1最長流程時間的計算11.2.2兩臺機器排序問題的最優(yōu)算法11.2.3多臺機器排序問題的啟發(fā)式算法Work

Center#1WorkCenter#2Output第五頁，共四十一頁。5華中科大管理學(xué)院陳榮秋馬士華11.2.1最長流程時間的計算工件代號i146352Pi1453486Pi2391375Pi3768259Pi4563924491216243071819223136142432343948193035444652第六頁，共四十一頁。6華中科大管理學(xué)院陳榮秋馬士華11.2.2兩臺機器排序問題的最優(yōu)算法約翰森法則如果Min(ai,bj)<Min(aj,bi),則工件i應(yīng)該排在工件j之前。約翰森算法（1）從加工時間矩陣中找出最短加工時間；（2）若最短加工時間出現(xiàn)在機器M1

上，則對應(yīng)工件應(yīng)該盡可能往前排；若最短加工時間出現(xiàn)在機器M2上，則對應(yīng)工件應(yīng)該盡可能往后排。第七頁，共四十一頁。7華中科大管理學(xué)院陳榮秋馬士華11.2.2兩臺機器排序問題的最優(yōu)算法（續(xù)）然后從加工時間矩陣中劃去已排序工件的加工時間。若最短加工時間有多個，則任挑一個。（3）若所有工件都已排序，停止。否則，轉(zhuǎn)步驟（1）。第八頁，共四十一頁。8華中科大管理學(xué)院陳榮秋馬士華將工件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)加工順序為S=(2,5,6,1,4,3),Fmax=28I123456Ai518534Bi72247411.2.2兩臺機器排序問題的最優(yōu)算法（續(xù)）第九頁，共四十一頁。9華中科大管理學(xué)院陳榮秋馬士華11.2.2兩臺機器排序問題的最優(yōu)算法（續(xù)）Johnson算法的改進1.將所有ai≤

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

1345582747424

8

13

18

2631115222628aibi最優(yōu)順序下的加工周期為28第十一頁，共四十一頁。11華中科大管理學(xué)院陳榮秋馬士華11.2.3多臺機器排序問題的啟發(fā)式算法關(guān)鍵工件法1.計算每個工件的總加工時間，將加工時間最長的工件作為關(guān)鍵工件C；2.對于余下的工件，若pi1≤pim則按pi1不減的順序排成一個序列Sa

,若pi1>pim則按pim不增的順序排成一個序列Sb;3.順序（Sa,C,Sb）即為所求順序。第十二頁，共四十一頁。12華中科大管理學(xué)院陳榮秋馬士華11.2.3多臺機器排序問題的啟發(fā)式算法（續(xù)）舉例工件i1234Pi12163Pi24829Pi3548211131614CSa(2,1)Sb(4)所求順序：（2,1,3,4）第十三頁，共四十一頁。13華中科大管理學(xué)院陳榮秋馬士華11.2.4相同零件不同移動方式下加工周期的計算當(dāng)n個零件相同，則無排序問題。但不同移動方式下的加工周期不同三種典型的移動方式順序移動方式：一批零件全部加工完成后，整批移動到下道工序加工平行移動方式：單個零件加工完成后，立即移動到下道工序加工平行順序移動方式：兩者混合第十四頁，共四十一頁。14華中科大管理學(xué)院陳榮秋馬士華順序移動方式

加工周期時間工序1234順序移動方式第十五頁，共四十一頁。15華中科大管理學(xué)院陳榮秋馬士華

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

順序移動方式（續(xù)）第十六頁，共四十一頁。16華中科大管理學(xué)院陳榮秋馬士華平行移動方式工序1234時間加工周期第十七頁，共四十一頁。17華中科大管理學(xué)院陳榮秋馬士華平行移動方式（續(xù)）零件平行移動的加工周期為：

第十八頁，共四十一頁。18華中科大管理學(xué)院陳榮秋馬士華平行順序移動方式特點：既保持一批零件順序加工，有盡可能使相鄰工序加工時間平行進行。如圖所示：時間工序1234加工周期第十九頁，共四十一頁。19華中科大管理學(xué)院陳榮秋馬士華平行順序移動方式（續(xù)）平行順序移動加工周期計算

第二十頁，共四十一頁。20華中科大管理學(xué)院陳榮秋馬士華11.3單件作業(yè)排序問題11.3.1問題的描述11.3.2兩種作業(yè)計劃的構(gòu)成11.3.3求解一般n/m/G/Fmax問題的啟發(fā)式方法第二十一頁，共四十一頁。21華中科大管理學(xué)院陳榮秋馬士華11.3.1問題的描述D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345加工描述矩陣D和加工時間矩陣T對應(yīng)第二十二頁，共四十一頁。22華中科大管理學(xué)院陳榮秋馬士華11.3.2兩種作業(yè)計劃的構(gòu)成符號說明每安排一道工序稱為一“步”{St}:t步之前已排序工序構(gòu)成的部分作業(yè)計劃；{Ot}:t步可排序工序的集合；Tk為{Ot}中工序Ok的最早可能開始時間；T’k為{Ot}中工序Ok的最早可能完成時間。第二十三頁，共四十一頁。23華中科大管理學(xué)院陳榮秋馬士華11.3.2兩種作業(yè)計劃的構(gòu)成能動作業(yè)計劃的構(gòu)成（1）設(shè)t=1,{S1}為空集，{O1}為各工件第一道工序的集合。（2）求T*=min{T’k},并求出T*所出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。（3）從{Ot}中選出滿足以下兩個條件的工序Oj：需要M*加工，且Tj<T*。（4）將選定的工序Oj放入{St},從{Ot}中消去Oj,并將Oj的緊后工序放入{Ot}，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。第二十四頁，共四十一頁。24華中科大管理學(xué)院陳榮秋馬士華能動作業(yè)計劃的構(gòu)成t{Ot}TkT`kT*M*Oj11,1,12,1,300232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,173877M12,2,151,3,22,3,2778128M21,3,262,3,281313M22,3,2第二十五頁，共四十一頁。25華中科大管理學(xué)院陳榮秋馬士華能動作業(yè)計劃的甘特圖2,3,21,1,12,2,11,3,22,1,31,2,33778132370時間機器M1M2M3第二十六頁，共四十一頁。26華中科大管理學(xué)院陳榮秋馬士華11.3.2兩種作業(yè)計劃的構(gòu)成（續(xù)）無延遲作業(yè)計劃的構(gòu)成（1）設(shè)t=1,{S1}為空集，{O1}為各工件第一道工序的集合。（2）求T*=min{Tk},并求出T*所出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。（3）從{Ot}中選出滿足以下兩個條件的工序Oj：需要M*加工，且Tj=T*。（4）將選定的工序Oj放入{St},從{Ot}中消去Oj,并將Oj的緊后工序放入{Ot}，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。第二十七頁，共四十一頁。27華中科大管理學(xué)院陳榮秋馬士華無延遲作業(yè)計劃的構(gòu)成t{Ot}TkT`kT*M*Oj11,1,12,1,3002300M1M31,1,121,2,32,1,320630M32,1,331,2,32,2,1337733M3M11,2,341,3,22,2,173873M12,2,151,3,22,3,27781277M2M22,3,261,3,2121312M21,3,2第二十八頁，共四十一頁。28華中科大管理學(xué)院陳榮秋馬士華無延遲作業(yè)計劃的甘特圖2,3,21,1,12,2,12,1,31,2,337712132370時間機器M1M2M31,3,2第二十九頁，共四十一頁。29華中科大管理學(xué)院陳榮秋馬士華11.3.3三類啟發(fā)式算法（1）優(yōu)先調(diào)度法則構(gòu)成兩種作業(yè)計劃的第（3）步一般都有多道工序可以滿足，按不同的優(yōu)先調(diào)度法則來選擇工序，可以得出滿足不同目標(biāo)函數(shù)的作業(yè)計劃計算量小已經(jīng)提出100多種優(yōu)先調(diào)度法則第三十頁，共四十一頁。30華中科大管理學(xué)院陳榮秋馬士華優(yōu)先調(diào)度法則FCFS（firstcome,firstserved）選擇最早進入可排序集合的工序SPT(shortestprocessingtime）選擇加工時間最短的工序EDD（earliestduedate）選擇完工期限最緊的工序SCR(smallestcriticalratio)選擇臨界比最小的工件MWKR(mostworkremaining)選擇余下加工時間最長的工件LWKR(leastworkremaining)選擇余下加工時間最短的工件MOPNR(mostoperationsremaining)選擇余下工序數(shù)最多的工件RANDOM隨機挑選一個工件RushTopPriority第三十一頁，共四十一頁。31華中科大管理學(xué)院陳榮秋馬士華11.3.3三類啟發(fā)式算法（續(xù)）（2）隨機抽樣法從全部能動計劃或無延遲計劃中隨機抽樣，得出多個作業(yè)計劃，從中取優(yōu)。（3）概率調(diào)度法將優(yōu)先調(diào)度法則與隨機抽樣法結(jié)合對不同工件將優(yōu)先調(diào)度法則分配不同的挑選概率，效果較好第三十二頁，共四十一頁。32華中科大管理學(xué)院陳榮秋馬士華11.4生產(chǎn)作業(yè)控制實行生產(chǎn)作業(yè)控制的原因生產(chǎn)環(huán)境的變化計劃的失誤執(zhí)行的原因：執(zhí)行過程中，有可能會出現(xiàn)操作人員執(zhí)行不力、效率不高和工作態(tài)度等現(xiàn)象，造成計劃完不成執(zhí)行因素的影響第三十三頁，共四十一頁。33華中科大管理學(xué)院陳榮秋馬士華11.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的程序制定生產(chǎn)作業(yè)監(jiān)控體系監(jiān)控實際生產(chǎn)過程評估偏差情況采取糾偏措施第三十四頁，共四十一頁。34華中科大管理學(xué)院陳榮秋馬士華11.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的功能為每個車間的工單指派優(yōu)先級維護車間在制品數(shù)量將車間工單信息傳送到相應(yīng)辦公室提供實際產(chǎn)出數(shù)據(jù)來為能力控制服務(wù)根據(jù)車間工單對機位的要求，為在制品庫存管理提供數(shù)量信息測量人員和設(shè)備的效率、利用率和產(chǎn)量。第三十五頁，共四十一頁。35華中科大管理學(xué)院陳榮秋馬士華第三十六頁，共四十一頁。36華中科大管理學(xué)院陳榮秋馬士華11.4生產(chǎn)作業(yè)控制（續(xù)）生產(chǎn)作業(yè)控制的主要工具實際生產(chǎn)中，有不少工具可以用來進行生產(chǎn)作業(yè)控制，這些工具容易通過運用適當(dāng)?shù)能浖砩?，主要包括：調(diào)度單日報、月報例外報告、異常報告輸入/輸出（Input/outputcontrol，I/O）報告第三十七頁，共四十一頁。37華中科大管理學(xué)院陳榮秋馬士華11.4生產(chǎn)作業(yè)控制（續(xù)）漏斗模型模型介紹德國漢諾威大學(xué)的Bechte和Wiendall等人于20世紀(jì)80年代初在實施輸入/輸出控制時提出了漏斗模型