第十章作業計劃教材第11章P2871第十章作業計劃教學目的：了解車間作業管理的主要工作了解作業排序的目標與分類掌握制造業作業排序的一般方法與數學方法2學習內容編制生產作業計劃的實質作業計劃編制的相關概念2臺機器排序問題的最優算法n/m/P/Fmax的啟發式算法指派問題及其啟發式算法3？MRP后企業該干什么通過MRP確定各車間的零部件投入出產計劃，從而將全廠性的產品出產計劃變成了各車間的生產任務。各車間要完成生產任務還必須將零部件投入出產計劃轉化為車間生產作業計劃，將計劃安排到具體的機器和個人。因而牽涉到任務分配和作業排序問題。4任務分配問題假定甲單位有甲、乙、丙、丁、戊五個員工，需要在一定的生產技術組織條件下，完成A、B、C、D、E五項任務，每個員工完成每項工作所需要耗費的工作時間不同。問：員工與任務之間應當如何進行配置，才能保證完成工作任務的時間最短？5123？從哪一項工作開始4.5小時8.5小時4.5小時擬稿時間5小時7小時8小時審稿時間作業排序問題61車間作業管理的工作內容核實MRP產生的計劃清單檢查物料、能力、工具等的可用性下達生產訂單說明零件加工工序順序和時間監控在制品生產與車間生產相關的其它工作72生產作業計劃

2.1編制生產作業計劃的實質-1將資源分配給不同的任務，按照既定的優化目標，確定各種資源利用的時間問題，包括確定零部件產品的加工順序，加工任務的分配和加工每件零件開始時間和完成時間的確定。82.2有關的名詞術語排序確定零件在機器上的加工順序。調度作業計劃編制之后實施生產控制采取的一切行動。派工在作業計劃制定后，按照作業計劃要求，將具體的生產任務分配到具體的機床和工人。92.3排程的基本要求一個好的排程能滿足什么要求?完成時間最短設備使用率最大化在制品庫存量最小等待時間最少對于這些要求衡量的標準是什么?成本與利潤

每件工作的平均完成時間設備運行的時間百分比系統的平均庫存數量平均延遲天數102.4排程問題的分類-1按機器種類和數量分類單臺機器的排序問題多臺機器的排序問題單件作業排序問題(Job-Shop)－零件加工路線不同流水作業排序問題(Flow-Shop)－所有零件的加工路線完全相同112.4排程問題的分類-2按工件到達車間的情況不同靜態排序問題－所有零件都已到達，一次排序動態排序問題－零件陸續到達，隨時排序按參數的性質確定型排序問題－加工時間等參數為已知量隨機型排序問題－加工時間等參數為隨機變量12零件數機器數車間類型目標函數N個零件經過3臺設備加工的流水作業排列排序問題，目標函數是使最長完工時間C最短F：流水線作業排序問題

P：流水線作業排列排序問題

G：一般單件作業排序問題

B：目標函數，通常是使其最小2.5排序問題的四參數表示方法-Conway133作業排序的一般方法－－甘特圖

3.1概述甘特圖（Ganttchart）又叫橫道圖、條狀圖(Barchart)。它是以圖示的方式通過活動列表和時間刻度形象地表示出任何特定項目的活動順序與持續時間。它是在第一次世界大戰時期發明的，以亨利·L·甘特先生的名字命名，他制定了一個完整地用條形圖表示進度的標志系統。由于甘特圖形象簡單，在簡單、短期的項目中，甘特圖都得到了最廣泛的運用。14甘特圖153.2甘特圖的含義-1甘特圖內在思想簡單，基本是一條線條圖，橫軸表示時間，縱軸表示活動(項目)，線條表示在整個期間上計劃和實際的活動完成情況。它直觀地表明任務計劃在什么時候進行，及實際進展與計劃要求的對比。管理者由此極為便利地弄清一項任務(項目)還剩下哪些工作要做，并可評估工作是提前還是滯后，亦或正常進行。是一種理想的控制工具。163.2甘特圖的含義-2甘特圖包含以下三個含義：1、以圖形或表格的形式顯示活動；2、現在是一種通用的顯示進度的方法；3、構造時應包括實際日歷天和持續時間，并且不要將周末和節假日算在進度之內。173.3兩種基本形式的甘特圖作業進度圖表示一項工作的計劃開始日期、計劃完成日期以及現在的進度。機器圖描述不同工作在每一臺機器上的工作次序，也可用來管理生產進度。18SMTWTFSDayJobJobAJob

BJobCRepairUsedtomonitorjobprogressTodayGanttSchedulingChart注明：計劃使用時間實際工作進度19UsedtodescribetheworksequenceoneachmachineGanttMachineChartWorkCenterMTWThFSheetMetalJob

AJobFMechanicalJobDJobGElectricalJobBJobHPaintingJobCJobEJobI注明設備空閑時間203.4甘特圖的優點圖形化概要，通用技術，易于理解；中小型項目一般不超過30項活動；有專業軟件（微軟項目管理軟件(MicrosoftProject）支持，無須擔心復雜計算和分析。213.5甘特圖的不足甘特圖事實上僅僅部分地反映了項目管理的三重約束（時間、成本和范圍），因為它主要關注進程管理（時間）；軟件的不足。盡管能夠通過項目管理軟件描繪出項目活動的內在關系，但是如果關系過多，紛繁蕪雜的線圖必將增加甘特圖的閱讀難度；224流水車間作業計劃問題

4.1加工周期的計算-1n個不同的零件要按相同的加工路線經過m臺機器加工，目標是使這批零件的加工周期最短，這種流水車間作業排序問題是本節所討論的n/m/P/Fmax問題。加工周期又稱為最長流程時間，它是從第一個零件在第一臺機器開始加工時算起，到最后一個零件在最后一臺機器上完成加工時為止所經過的時間。234.1加工周期的計算-2按給出的順序S列出加工時間矩陣。將每個零件的完工時間標在其右上角。對于第一行第一列的元素其完工時間為自身加工時間；對于第一行的其它元素，只需從左到右依次將上一列的數值加上計算列的加工時間；對于第一列的其它元素，只需從上到下依次將上一行的數值加上計算行的加工時間；對于其它元素則要從本行前一列右上角數字和本列上一行的右上角數字中取大者，加上元素的加工時間。最后一行的最后一列右上角數字，即為加工周期。24i123456Pi1423142Pi2456745Pi3587555Pi4424331例：有一個6/4/P/Fmax問題，其加工時間如下表，當按照順序S=（6，1，5，2，4，3）加工時，求Fmax25i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi411342132523233844626123？從哪一項工作開始4.5小時8.5小時4.5小時擬稿時間5小時7小時8小時審稿時間27優先規則：Johnson規則列好時間表，從中選最小；若在第一列，將其排在首；若在第二列，將其排在尾。J1J2J3J412n/2/P/Fmax4.22臺機器排序問題的最優算法28

工作中心1工作中心2工作數據輸入時間（h）核對時間（h）A2.51.7B3.82.6C1.91.0D1.83.029工作中心1工作中心2A2.502.5B6.3CD1.810ABC9.9D3.013iABCDPi1.810Pi8.91.09.93.01330工作數據輸入時間（h）核對時間（h）A2.51.7B3.82.6C1.91.0D1.83.0——C排序方案：31工作數據輸入時間（h）核對時間（h）A2.51.7

B3.82.6D1.83.0——C排序方案：——A32工作數據輸入時間（h）核對時間（h）B3.82.6D1.8

3.0——C排序方案：——AD——33——C排序方案：——AD——B工作中心1工作中心2D1.801.8B5.6AC1.910D

3.04.83.8BA9.9C1.01134工作中心1工作中心2D1.801.8B5.6AC1.910D

3.04.83.8BA9.9C1.011新排序方案：D—B—A—C工作中心1工作中心2A2.502.5B6.3CD1.810ABC9.9D3.013原方案：D—B—A—C35123？從哪一項工作開始4.5小時8.5小時4.5小時擬稿時間5小時7小時8小時審稿時間36工作擬稿時間（h）審稿時間（h）A84.5B58.5C74.5試求1、最優排序方案B—C—A2、不同排序方案下的Fmax/B—A—C24.52637Palmer法（帕爾默法）關鍵工件法CDS法Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi345824.3一般n/m/P/Fmax問題的啟發式算法384.3.1Palmer法1965年，帕爾默（D.S.Palmer）指出按斜度指標排列零件的啟發式算法。計算零件的斜度指標按照各零件不增的順序排列零件39Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi3458212得到加工工序Fmax＝28（1，2，3，4）或（2，1，3，4）404.3.2關鍵零件法（陳榮秋）計算最長加工時間的工件C（j=m）對余下工件，若，按不減順序排成Sa若，按不增順序排成Sb順序（Sa，C，Sb）即所求41Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi34582Pi13111614123424.3.3CDS法－窮舉法-1坎貝爾（Campbell）、杜德克（Dudek）、史密斯（Smith）三人提出了一個啟發式算法。是Johnson算法解一般n/m/P/Fmax的運用。對加工時間和用Johnson算法求m-1次加工順序，求其中最好。434.3.3CDS法－窮舉法-2窮舉法的操作步驟如下：取首末兩道工序，用約翰遜法排序，求Fmax取首兩道工序的和及尾兩道工序的和，用約翰遜法排序，求Fmax取首三道工序的和及尾三道工序的和，用約翰遜法排序，求Fmax以此類推，直到所有的（m-1）種都考慮后，比較得到的Fmax，找出其中最小的為最優。44Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi34582i1234L=1Pi11263Pi34582L=2Pi1+Pi296812Pi2+Pi31291011L=1,(1,2,3,4)L=2,(2,3,1,4)45i1234Pi11/12/36/93/12Pi28/94/132/159/24Pi34/135/188/262/28L=1,(1,2,3,4)i2314Pi12/26/81/93/12Pi24/62/108/189/27Pi35/118/194/232/29L=2,(2,3,1,4)465單件車間作業計劃問題單件車間作業計劃問題是十分復雜的一種作業計劃問題。它不僅包括排序問題，還包括任務分配問題。475.1任務分配問題-1

－指派問題（AssignmentProblem）在編制生產作業計劃分配生產任務時，會碰到這樣的問題：有若干項任務，要分配給若干小組或人去完成，由于每個人或小組完成各項任務的效率不同，應如何分配才能發揮每個小組或個人的優勢，使完成任務總的效率最高呢？把零件分配給工人或機器加工，將區域分配給銷售人員，將出故障的機器分配給維修小組都是任務分配問題。48AB

CD

泌尿科心臟病科整形外科產科指派問題（AssignmentProblem）495.1任務分配問題（指派問題）-2一種求解特殊的可將任務或工作分配給相應的資源的線性規劃模型的方法重要特征：一件工作（一個服務對象）僅分配給一個服務者《運籌學》清華大學出版社2001年134第五章整數規劃第5節指派問題505.2匈牙利法

5.2.1概述匈牙利法（TheHungarianmethodofassignment）是由匈牙利數學家考尼格（Konig）提出的，因此得名。目標成本最小或利潤最大515.2匈牙利法

5.2.2步驟行減最小，列減最小。最少直線蓋住表中所有零。直線數＝行列數則到第4)步，否則到第3）步未蓋住數減最小，將最小加到直線相交處，重復2)最佳分配出現在表中零位置。525.2匈牙利法

5.2.3示例假定甲單位有甲、乙、丙、丁、戊五個員工，需要在一定的生產技術組織條件下，完成A、B、C、D、E五項任務，每個員工完成每項工作所需要耗費的工作時間，如表1所示。請求出：員工與任務之間應當如何進行配置，才能保證完成工作任務的時間最短？53員工任務甲乙丙丁戊A10591811B131961214C32445D189121715E116141910表1各員工完成任務時間匯總表單位：小時54解：1.以各個員工完成各項任務的時間構造矩陣1。1059181113196121432445189121715116141910矩陣1552．對矩陣1進行行約減，即每一行數據減去本行數據中的最小數，得矩陣2。5041367130681022390386508134矩陣2563．檢查矩陣2，若矩陣2各行各列均有“0”，則跳過此步，否則進行列約減，即每一列數據減去本列數據中的最小數，得矩陣3。4041136130450020080363408111矩陣3574．從含“0”最多的行或列開始畫“蓋0”線。即畫最少的線將矩陣三中的0全部覆蓋住，得矩陣4。4041136130450020080363408111矩陣4585．數據轉換。若“蓋0”線的數目等于矩陣的維數則跳過此步，若“蓋0”線的數目小于矩陣得維數則進行數據轉換，本例屬于后一種情況，應進行轉換，操作步驟如下：（1）找出未被“蓋0”線覆蓋的數中的最小值例中

＝1。（2）將未被“蓋0”線覆蓋住的數減去。（3）將“蓋0”線交叉點的數加上。59本例結果見表2－10矩陣5。3041025130340130070352308100矩陣5606．重復4步和5步（計算過程見矩陣5a和矩陣5b），直到“蓋0”線的數目等于矩陣的維數。本例最終矩陣見表矩陣6。3041025130340130070352308100矩陣5a6100472213004046034032200870矩陣5b00472213004046034032200870矩陣6627.求最優解。對n維矩陣，找出不同行、不同列的n個“0”，每個“0”的位置代表一對配置關系，具體步驟如下：（1）先找只含有一個“0”的行（或列），將該行（或列）中的“0”打“√”。（2）將帶“√”的“0”所在列（或行）中的“0”打“”。（3）重復（1）步和（2）步至結束。若所有行列均含有多個“0”，則從“0”的數目最少的行或列中任選一個“0”打“√”。6300472213004046034032200870矩陣7√√√√√64其結果如矩陣7所示，即員工甲負責任務A，員工乙負責任務D，員工丙負責任務B，員工丁負責任務C，員工戊負責任務E，參照表1各員工完成任務時間匯總表，得出表2所示的員工配置最終結果。65員工任務甲乙丙丁戊A10B6C4D9E10表2各員工配置最終結果

單位：小時665.3一般n/m/G/Fmax問題的啟發式算法

5.3.1基本法則-1先到先服務原則（FCFS）：按照訂單到達的先后順序進行加工。交貨期最早原則（EDD）：按照交貨期由早到晚的順序進行加工。后到先服務原則（LCFS）：后到的訂單放在先到的上面，操作員在操作的時候會先加工上面的訂單。FirstcomefirstserveEarliestduedateLastcomefirstserve675.3一般n/m/G/Fmax問題的啟發式算法

5.3.1基本法則-2最短加工時間準則（SPT）：優先安排加工時間最短的任務。最短松弛時間準則（SST）：按照松弛時間有短到長進行