第十章作業(yè)計(jì)劃

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

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

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

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

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

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

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

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

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

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

工作中心1工作中心2工作數(shù)據(jù)輸入時(shí)間（h）核對(duì)時(shí)間（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ù)輸入時(shí)間（h）核對(duì)時(shí)間（h）A2.51.7B3.82.6C1.91.0D1.83.0——C排序方案：31工作數(shù)據(jù)輸入時(shí)間（h）核對(duì)時(shí)間（h）A2.51.7

B3.82.6D1.83.0——C排序方案：——A32工作數(shù)據(jù)輸入時(shí)間（h）核對(duì)時(shí)間（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？從哪一項(xiàng)工作開始4.5小時(shí)8.5小時(shí)4.5小時(shí)擬稿時(shí)間5小時(shí)7小時(shí)8小時(shí)審稿時(shí)間36工作擬稿時(shí)間（h）審稿時(shí)間（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ā)式算法。計(jì)算零件的斜度指標(biāo)按照各零件不增的順序排列零件39Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi3458212得到加工工序Fmax＝28（1，2，3，4）或（2，1，3，4）404.3.2關(guān)鍵零件法（陳榮秋）計(jì)算最長(zhǎng)加工時(shí)間的工件C（j=m）對(duì)余下工件，若，按不減順序排成Sa若，按不增順序排成Sb順序（Sa，C，Sb）即所求41Example:4/3/P/Fmaxi1234Pi11263Pi28429Pi34582Pi13111614123424.3.3CDS法－窮舉法-1坎貝爾（Campbell）、杜德克（Dudek）、史密斯（Smith）三人提出了一個(gè)啟發(fā)式算法。是Johnson算法解一般n/m/P/Fmax的運(yùn)用。對(duì)加工時(shí)間和用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è)計(jì)劃問題單件車間作業(yè)計(jì)劃問題是十分復(fù)雜的一種作業(yè)計(jì)劃問題。它不僅包括排序問題，還包括任務(wù)分配問題。475.1任務(wù)分配問題-1

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

CD

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

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

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

5.2.3示例假定甲單位有甲、乙、丙、丁、戊五個(gè)員工，需要在一定的生產(chǎn)技術(shù)組織條件下，完成A、B、C、D、E五項(xiàng)任務(wù)，每個(gè)員工完成每項(xiàng)工作所需要耗費(fèi)的工作時(shí)間，如表1所示。請(qǐng)求出：?jiǎn)T工與任務(wù)之間應(yīng)當(dāng)如何進(jìn)行配置，才能保證完成工作任務(wù)的時(shí)間最短？53員工任務(wù)甲乙丙丁戊A10591811B131961214C32445D189121715E116141910表1各員工完成任務(wù)時(shí)間匯總表單位：小時(shí)54解：1.以各個(gè)員工完成各項(xiàng)任務(wù)的時(shí)間構(gòu)造矩陣1。1059181113196121432445189121715116141910矩陣1552．對(duì)矩陣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步（計(jì)算過程見矩陣5a和矩陣5b），直到“蓋0”線的數(shù)目等于矩陣的維數(shù)。本例最終矩陣見表矩陣6。3041025130340130070352308100矩陣5a6100472213004046034032200870矩陣5b00472213004046034032200870矩陣6627.求最優(yōu)解。對(duì)n維矩陣，找出不同行、不同列的n個(gè)“0”，每個(gè)“0”的位置代表一對(duì)配置關(guān)系，具體步驟如下：（1）先找只含有一個(gè)“0”的行（或列），將該行（或列）中的“0”打“√”。（2）將帶“√”的“0”所在列（或行）中的“0”打“”。（3）重復(fù)（1）步和（2）步至結(jié)束。若所有行列均含有多個(gè)“0”，則從“0”的數(shù)目最少的行或列中任選一個(gè)“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ù)時(shí)間匯總表，得出表2所示的員工配置最終結(jié)果。65員工任務(wù)甲乙丙丁戊A10B6C4D9E10表2各員工配置最終結(jié)果

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

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

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