1、華中科大管理學院陳榮秋馬士華1第11章 制造業作業計劃與控制Scheduling and Controlling for Manufacturing11.1 作業計劃問題的基本概念11.2 流水作業排序問題11.3 單件作業的排序問題11.4 生產作業控制 華中科大管理學院陳榮秋馬士華211.1作業計劃問題的基本概念編制作業計劃要解決的問題n編制作業計劃實質上是要將資源分配給不同的任務，按照既定的優化目標，確定各種資源利用的時間問題。n由于每臺機器都可能被分配了多項任務，而這些任務受到加工路線的約束，就帶來了零件在機器上加工的順序問題。華中科大管理學院陳榮秋馬士華3 11.1作業計劃問題的基本

2、概念（續）有關的名詞術語n編制作業計劃或日程安排(Scheduling)n排序(Sequencing)n派工(Dispatching)n控制(Controlling)n趕工(Expediting) n“調度”是作業計劃編制后實施生產控制所采取的一切行動，“編制作業計劃”是加工制造發生之前的活動華中科大管理學院陳榮秋馬士華411.1作業計劃問題的基本概念（續）n“機器”，可以是工廠里的各種機床，也可以是維修工人；可以是輪船要停靠的碼頭，也可以是電子的計算機中央處理單元、存貯器和輸入、輸出單元。一句話，表示“服務者”n“零件”代表“服務對象”。零件可以是單個零件，也可以是一批相同的零件n“加工路線

3、”是零件加工的工藝過程決定的，它是零件加工在技術上的約束 n“加工順序”則表示每臺機器加工n個零件的先后順序，是排序和編制作業計劃要解決的問題華中科大管理學院陳榮秋馬士華511.2 流水作業排序問題流水車間(Flow shop):工件的加工路線都一致，典型的如流水線11.2.1 最長流程時間的計算 11.2.2 兩臺機器排序問題的最優算法 11.2.3 多臺機器排序問題的啟發式算法Work Center #1Work Center #2Output華中科大管理學院陳榮秋馬士華611.2.1 最長流程時間的計算工件代號i 1 4 6 3 5 2Pi1 4 5 3 4 8 6Pi2 3 9 1 3

4、 7 5Pi3 7 6 8 2 5 9Pi4 5 6 3 9 2 44 9 12 16 24 307 18 19 22 31 3614 24 32 34 39 4819 30 35 44 46 52華中科大管理學院陳榮秋馬士華711.2.2 兩臺機器排序問題的 最優算法約翰森法則n如果Min(ai, bj) pim 則按pim不增的順序排成一個序列Sb;n3. 順序（Sa,C,Sb）即為所求順序。華中科大管理學院陳榮秋馬士華1311.2.3 多臺機器排序問題的 啟發式算法（續） 舉例工件i 1 2 3 4Pi1 2 1 6 3Pi2 4 8 2 9Pi3 5 4 8 211 13 16 14C

5、Sa (2,1)Sb(4)所求順序：（2,1,3,4）華中科大管理學院陳榮秋馬士華1411.2.4 相同零件不同移動方 式下加工周期的計算當n個零件相同，則無排序問題。但不同移動方式下的加工周期不同三種典型的移動方式n順序移動方式：一批零件全部加工完成后，整批移動到下道工序加工n平行移動方式：單個零件加工完成后，立即移動到下道工序加工n平行順序移動方式：兩者混合華中科大管理學院陳榮秋馬士華15順序移動方式 加工周期時間工序 1 2 3 4順序移動方式順序移動方式華中科大管理學院陳榮秋馬士華16 設零件批量為n（件），工序數目為m，一批零件不計算工序間運輸時間，只考慮加工時間，設其加工的周期為T

6、（分鐘），零件在i道工序的單件工時為 （分鐘/件），i=1.2n. 則該批零件的加工周期為： it121.mimiTntntntnt順序移動方式（續）華中科大管理學院陳榮秋馬士華17平行移動方式工序 1 2 34時間 加工周期華中科大管理學院陳榮秋馬士華18平行移動方式（續）零件平行移動的加工周期 為： T平12111.(1)mmiiTttntnttnt平華中科大管理學院陳榮秋馬士華19平行順序移動方式 特點：既保持一批零件順序加工，有盡可能使相鄰工序加工時間平行進行。如圖所示： 時間工序1234 加工 周期華中科大管理學院陳榮秋馬士華20平行順序移動方式（續）平行順序移動加工周期計算 111

7、(1)mmiiiiTtnt平 順=n華中科大管理學院陳榮秋馬士華2111.3 單件作業排序問題11.3.1 問題的描述11.3.2 兩種作業計劃的構成11.3.3 求解一般n/m/G/Fmax問題的啟發式方法華中科大管理學院陳榮秋馬士華2211.3.1 問題的描述D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5加工描述矩陣D和加工時間矩陣T對應華中科大管理學院陳榮秋馬士華2311.3.2 兩種作業計劃的構成符號說明n每安排一道工序稱為一“步”nSt:t步之前已排序工序構成的部分作業計劃；nOt:t步可排序工序的集合；nTk為Ot中工序Ok的最早可

8、能開始時間；nTk為Ot中工序Ok的最早可能完成時間。華中科大管理學院陳榮秋馬士華2411.3.2 兩種作業計劃的構成能動作業計劃的構成n（1）設t=1,S1為空集，O1為各工件第一道工序的集合。n（2）求T* = minTk,并求出T*所出現的機器M*。如果M*有多臺，則任選一臺。n（3）從Ot中選出滿足以下兩個條件的工序Oj：需要M*加工，且Tj T* 。n（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1.n（5）若還有未安排的工序，轉步驟（2）；否則，停止。華中科大管理學院陳榮秋馬士華25能動作業計劃的構成tOtTkTkT*M*Oj11,1,1

9、2,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華中科大管理學院陳榮秋馬士華26能動作業計劃的甘特圖2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70時間時間機器 M1M2M3華中科大管理學院陳榮秋馬士華2711.3.2 兩種作業計劃的構成（續）無延遲作業計劃的構成n（1）設t=1,S1為空集，O1為各工件第一道工序的集合。n（2）求T

10、* = minTk,并求出T*所出現的機器M*。如果M*有多臺，則任選一臺。n（3）從Ot中選出滿足以下兩個條件的工序Oj：需要M*加工，且Tj=T* 。n（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1.n（5）若還有未安排的工序，轉步驟（2）；否則，停止。華中科大管理學院陳榮秋馬士華28無延遲作業計劃的構成tOtTkTkT*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,2

11、7781277M2M22,3,261,3,2121312M21,3,2華中科大管理學院陳榮秋馬士華29無延遲作業計劃的甘特圖2,3,21,1,1 2,2,12,1,3 1,2,3 3 7 7 12 13 2 3 70時間時間機器 M1M2M31,3,2華中科大管理學院陳榮秋馬士華3011.3.3 三類啟發式算法（1）優先調度法則n構成兩種作業計劃的第（3）步一般都有多道工序可以滿足，按不同的優先調度法則來選擇工序，可以得出滿足不同目標函數的作業計劃n計算量小n已經提出100多種優先調度法則華中科大管理學院陳榮秋馬士華31優先調度法則nFCFS（first come, first served）

12、選擇最早進入可排序集合的工序nSPT( shortest processing time）選擇加工時間最短的工序nEDD（earliest due date）選擇完工期限最緊的工序nSCR(smallest critical ratio)選擇臨界比最小的工件nMWKR(most work remaining)選擇余下加工時間最長的工件nLWKR(least work remaining)選擇余下加工時間最短的工件nMOPNR(most operations remaining)選擇余下工序數最多的工件nRANDOM 隨機挑選一個工件nRushTop Priority華中科大管理學院陳榮秋馬士華

13、3211.3.3 三類啟發式算法（續）（2）隨機抽樣法n從全部能動計劃或無延遲計劃中隨機抽樣，得出多個作業計劃，從中取優。（3）概率調度法n將優先調度法則與隨機抽樣法結合n對不同工件將優先調度法則分配不同的挑選概率，效果較好華中科大管理學院陳榮秋馬士華3311.4 生產作業控制實行生產作業控制的原因生產環境的變化計劃的失誤執行的原因：執行過程中，有可能會出現操作人員執行不力、效率不高和工作態度等現象，造成計劃完不成執行因素的影響華中科大管理學院陳榮秋馬士華3411.4 生產作業控制（續） 生產作業控制的程序制定生產作業監控體系監控實際生產過程 評估偏差情況 采取糾偏措施華中科大管理學院陳榮秋馬

14、士華3511.4 生產作業控制（續） 生產作業控制的功能為每個車間的工單指派優先級維護車間在制品數量將車間工單信息傳送到相應辦公室提供實際產出數據來為能力控制服務根據車間工單對機位的要求，為在制品庫存管理提供數量信息測量人員和設備的效率、利用率和產量。華中科大管理學院陳榮秋馬士華36華中科大管理學院陳榮秋馬士華3711.4 生產作業控制（續） 生產作業控制的主要工具實際生產中，有不少工具可以用來進行生產作業控制，這些工具容易通過運用適當的軟件來生成，主要包括：n調度單n日報、月報n例外報告、異常報告n輸入/輸出（Input/output control，I/O）報告華中科大管理學院陳榮秋馬士華

15、3811.4 生產作業控制（續） 漏斗模型模型介紹德國漢諾威大學的Bechte和Wiendall等人于20世紀80年代初在實施輸入/輸出控制時提出了漏斗模型（Funnel Model）。漏斗模型的基本原則：工作中心的輸入永遠不能超過工作中心的輸出。當工作中心的輸入超過輸出，就會拖欠訂單，結果將會出現作業推遲、客戶不滿、下游作業或相關作業的延期。華中科大管理學院陳榮秋馬士華39注：曲線圖的垂直段表示某天到達或完成的一個或多個工件之間所包含的工作量；水平段表示相鄰兩個到達或完成的任務之間的時間間隔。如果運輸時間不變，輸入曲線與上道工序的輸出曲線相對應。華中科大管理學院陳榮秋馬士華4011.4 生產作業控制（