第十章作業(yè)計劃

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

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

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

P：流水線作業(yè)排列排序問題

G：一般單件作業(yè)排序問題

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

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

BJobCRepairUsedtomonitorjobprogressTodayGanttSchedulingChart注明：計劃使用時間實(shí)際工作進(jìn)度19UsedtodescribetheworksequenceoneachmachineGanttMachineChartWorkCenterMTWThFSheetMetalJob

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

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

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

B3.82.6D1.83.0——C排序方案：——A32工作數(shù)據(jù)輸入時間（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、最優(yōu)排序方案B—C—A2、不同排序方案下的Fmax/B—A—C24.52637Palmer法（帕爾默法）關(guān)鍵工件法CDS法Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi345824.3一般n/m/P/Fmax問題的啟發(fā)式算法384.3.1Palmer法1965年，帕爾默（D.S.Palmer）指出按斜度指標(biāo)排列零件的啟發(fā)式算法。計算零件的斜度指標(biāo)按照各零件不增的順序排列零件39Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi3458212得到加工工序Fmax＝28（1，2，3，4）或（2，1，3，4）404.3.2關(guān)鍵零件法（陳榮秋）計算最長加工時間的工件C（j=m）對余下工件，若，按不減順序排成Sa若，按不增順序排成Sb順序（Sa，C，Sb）即所求41Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi34582Pi13111614123424.3.3CDS法－窮舉法-1坎貝爾（Campbell）、杜德克（Dudek）、史密斯（Smith）三人提出了一個啟發(fā)式算法。是Johnson算法解一般n/m/P/Fmax的運(yùn)用。對加工時間和用Johnson算法求m-1次加工順序，求其中最好。434.3.3CDS法－窮舉法-2窮舉法的操作步驟如下：取首末兩道工序，用約翰遜法排序，求Fmax取首兩道工序的和及尾兩道工序的和，用約翰遜法排序，求Fmax取首三道工序的和及尾三道工序的和，用約翰遜法排序，求Fmax以此類推，直到所有的（m-1）種都考慮后，比較得到的Fmax，找出其中最小的為最優(yōu)。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單件車間作業(yè)計劃問題單件車間作業(yè)計劃問題是十分復(fù)雜的一種作業(yè)計劃問題。它不僅包括排序問題，還包括任務(wù)分配問題。475.1任務(wù)分配問題-1

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

CD

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

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

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

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

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

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

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

5.3.1基本法則-2最短加工時間準(zhǔn)則（SPT）：優(yōu)先安排加工時間最短的任務(wù)。最短松弛時間準(zhǔn)則（SST）：按照松弛時間有短到長進(jìn)行