第十章-作業(yè)計(jì)劃與控制課件

第十章作業(yè)計(jì)劃與控制丁秋雷第十章作業(yè)計(jì)劃與控制丁秋雷2

通過MRP確定了各車間零部件的投入出產(chǎn)計(jì)劃，將全廠性的生產(chǎn)計(jì)劃變成了各車間的生產(chǎn)任務(wù)。各車間要完成既定的生產(chǎn)任務(wù)，還必須將零部件投入出產(chǎn)計(jì)劃轉(zhuǎn)變?yōu)檐囬g生產(chǎn)作業(yè)計(jì)劃，即：將車間的生產(chǎn)任務(wù)變成各個(gè)工段、班組、工作地的任務(wù)。將任務(wù)安排到工作地，就涉及到任務(wù)分配和作業(yè)排序等問題。1.1作業(yè)計(jì)劃的必要性[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃2通過MRP確定了各車間零部件的投入出產(chǎn)計(jì)劃，將全廠性的生3

一個(gè)排序的例子

[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃3一個(gè)排序的例子

[關(guān)鍵內(nèi)容]:4

（a）裝配順序?yàn)锳→B→C→D，總裝配時(shí)間為48小時(shí)（b）裝配順序?yàn)镃→B→D→A，總裝配時(shí)間為45小時(shí)（c）裝配順序?yàn)镈→C→A→B，總裝配時(shí)間為51小時(shí)4（a）裝配順序?yàn)锳→B→C→D，總裝配時(shí)間為48小時(shí)（b5

排序給出零部件在一臺(tái)或一組設(shè)備上加工的先后順序，實(shí)質(zhì)上是要解決如何按時(shí)間的先后，將有限的資源分配給不同的工作任務(wù)使預(yù)定的目標(biāo)最優(yōu)化的問題。編制作業(yè)計(jì)劃不僅要解決先加工哪個(gè)工件、后加工哪個(gè)工件的加工順序問題，還包括確定機(jī)器加工每個(gè)工件的開始時(shí)間和完成時(shí)間。編制作業(yè)計(jì)劃與排序的概念和目的都是不同的。但是，在工件的加工順序確定以后，作業(yè)計(jì)劃也就確定了，因此往往將“排序”和“編制作業(yè)計(jì)劃”等同。1.2排序與編制作業(yè)計(jì)劃的差別[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃5排序給出零部件在一臺(tái)或一組設(shè)備上加工的先后順序，實(shí)質(zhì)上是6

確定出最佳的作業(yè)順序看似容易，只要列出所有的順序，然后再?gòu)闹刑舫鲎詈玫木涂梢粤耍獙?shí)現(xiàn)這種想法幾乎是不可能的。例如，考慮32項(xiàng)任務(wù)（工件），有32！種方案，假定計(jì)算機(jī)每秒鐘可以檢查1billion個(gè)順序,全部檢驗(yàn)完畢需要8.41015個(gè)世紀(jì)。以上問題還沒有考慮其他的約束條件,如機(jī)器、人力資源、廠房場(chǎng)地等，如果加上這些約束條件，所需要的時(shí)間更無法想象了。所以，很有必要去尋找一些有效算法，解決管理中的實(shí)際問題。1.3排序的難度[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃6確定出最佳的作業(yè)順序看似容易，只要列出所有的順序，然后再7

根據(jù)排序規(guī)則對(duì)每一個(gè)到達(dá)的訂單安排作業(yè)順序工作地工件排隊(duì)等待加工來自上游工作地的訂單加工完畢的訂單流向下一工作地單件車間制定作業(yè)計(jì)劃示意圖7根據(jù)排序規(guī)則對(duì)每一個(gè)到達(dá)的訂單安排作業(yè)順序工作地工件排來8

作業(yè)計(jì)劃：不僅要確定工件的加工順序，而且還要確定機(jī)器加工每個(gè)工件的開始時(shí)間和完成時(shí)間。通常情況下都是按最早可能開（完）工時(shí)間來編制作業(yè)計(jì)劃，是加工制造發(fā)生之前的活動(dòng)。排序：確定零件在機(jī)器上的加工順序。派工：按作業(yè)計(jì)劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機(jī)床上加工。調(diào)度：是作業(yè)計(jì)劃編制后實(shí)施生產(chǎn)控制所采取的行動(dòng)。2.1名詞術(shù)語[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃8作業(yè)計(jì)劃：不僅要確定工件的加工順序，而且還要確定機(jī)器加工9

一個(gè)零件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工，每臺(tái)機(jī)器同時(shí)只能加工一個(gè)零件；零件在加工過程中采取平行移動(dòng)方式，即上一道工序完工后，立即送下道工序加工；不允許中斷，零件一旦開始加工，必須一直進(jìn)行到完工，不得中途停止并插入其它零件；每道工序只在一臺(tái)機(jī)器上完成；零件數(shù)、機(jī)器數(shù)和加工時(shí)間已知。2.2假設(shè)條件[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃9一個(gè)零件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工，每臺(tái)機(jī)器同時(shí)只能10

2.3排序的分類排序問題分類按機(jī)器單臺(tái)機(jī)器排序問題多臺(tái)機(jī)器排序問題單件作業(yè)排序問題流水線作業(yè)排序問題按零件到達(dá)車間的情況靜態(tài)的排序問題動(dòng)態(tài)的排序問題按目標(biāo)函數(shù)的性質(zhì)按參數(shù)確定型排序問題隨機(jī)型排序問題單目標(biāo)的排序問題多目標(biāo)的排序問題[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃102.3排序的分類排序問題分類按機(jī)器單臺(tái)機(jī)器排序問題單11

按機(jī)器的種類和數(shù)量不同，分為單臺(tái)機(jī)器的排序問題和多臺(tái)機(jī)器的排序問題對(duì)于多臺(tái)機(jī)器排序，根據(jù)加工路線的特征，分成：?jiǎn)渭鳂I(yè)排序(Job-Shop)問題流水作業(yè)排序(Flow-Shop)問題2.3排序的分類工件的加工路線不同，是單件作業(yè)排序問題的基本特征；所有工件的加工路線完全相同，是流水作業(yè)排序問題的基本特征。也就是說，每個(gè)零件都順序地經(jīng)過線上不同機(jī)器加工，它們的加工路線一致。[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃11按機(jī)器的種類和數(shù)量不同，分為單臺(tái)機(jī)器的排序問題和多臺(tái)機(jī)12

排序問題常用四個(gè)符號(hào)來描述:n/m/A/B其中：n—工件數(shù)m—機(jī)器數(shù)A—車間類型B—目標(biāo)函數(shù)，通常使其值最小，如B=Fmax，是使最長(zhǎng)流程時(shí)間最短。例如：4/2/P/Fmax表示4個(gè)工件在2臺(tái)機(jī)器上流水作業(yè)時(shí)以最長(zhǎng)流程時(shí)間最短為目標(biāo)的排序。2.4排序問題的一般表示方法[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃12排序問題常用四個(gè)符號(hào)來描述:n/m/A/B2.413

2.5生產(chǎn)調(diào)度問題優(yōu)化的主要目標(biāo)

1基于經(jīng)濟(jì)的調(diào)度目標(biāo)：生產(chǎn)費(fèi)用最小，利潤(rùn)最大，庫(kù)存費(fèi)用最少等2最大能力指標(biāo)：包括最大生產(chǎn)率、最短的生產(chǎn)周期等3客戶滿意度指標(biāo)：包括最短的延遲，最小提前或者拖后懲罰，平均延遲時(shí)間小等目標(biāo)之間往往相互沖突，即某個(gè)目標(biāo)性能的改善可能導(dǎo)致另一個(gè)或者另幾個(gè)目標(biāo)性能的降低132.5生產(chǎn)調(diào)度問題優(yōu)化的主要目標(biāo)1基于經(jīng)濟(jì)的調(diào)度目14

n個(gè)工件全部經(jīng)由一臺(tái)機(jī)器處理3.1定義J1J2Jn機(jī)器到達(dá)系統(tǒng)工件的集合離開系統(tǒng)（機(jī)器）[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃14n個(gè)工件全部經(jīng)由一臺(tái)機(jī)器處理3.1定義J1機(jī)器到達(dá)系15

平均流程最短最大延期量最小

3.2常見單臺(tái)機(jī)器排序問題的目標(biāo)函數(shù)定義:為n個(gè)零件經(jīng)由一臺(tái)機(jī)器的平流程時(shí)間，流程時(shí)間=等待時(shí)間+加工時(shí)間目標(biāo)函數(shù)：定義:為最大延遲量。目標(biāo)函數(shù)：[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃15平均流程最短3.2常見單臺(tái)機(jī)器排序問題的目標(biāo)函數(shù)定義16

根據(jù)排序目標(biāo)的不同，可以選擇不同的排序規(guī)則，有時(shí)又稱為確定優(yōu)先權(quán)(Priorities)。常見的優(yōu)先權(quán)規(guī)則(Priorityrules)有：SPT---ShortestProcessTime,EDD---EarliestDueDate等,分別用于解決不同的問題。按什么樣的準(zhǔn)則來選擇，對(duì)排序方案的優(yōu)劣有很大影響。3.2常見單臺(tái)機(jī)器排序問題的目標(biāo)函數(shù)[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃16根據(jù)排序目標(biāo)的不同，可以選擇不同的排序規(guī)則，有時(shí)又稱為17

SPT（Shortestprocessingtime）法則優(yōu)先選擇加工時(shí)間最短的工序使工件的平均流程時(shí)間最短，從而減少在制品量EDD（Earliestduedate）法則優(yōu)先選擇交貨期最早的工件可使工件的平均延期時(shí)間最小FCFS（Firstcomefirstserved）法則優(yōu)先選擇最早進(jìn)入可排工序集合的工件來自排隊(duì)論，對(duì)工件較公平CR（CriticalRatio）法則CR是用交貨日期減去當(dāng)前日期的差值除以剩余的工作日數(shù)。關(guān)鍵比率最小的任務(wù)先執(zhí)行。保證工件的延期數(shù)量最小3.3常用的優(yōu)先順序規(guī)則[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃17SPT（Shortestprocessingtim18

MWKR（Mostworkremaining）法則優(yōu)先選擇余下加工時(shí)間最長(zhǎng)的工件不同工作量的工件的完工時(shí)間盡量接近LWKR（Leastworkremaining）法則優(yōu)先選擇余下加工時(shí)間最短的工件使工作量小的工件盡快完成STR（SlackTimeRemaining）法則：STR是交貨期前所剩余時(shí)間減去剩余的加工時(shí)間所得的差值。STR最短的任務(wù)最先進(jìn)行。使任何任務(wù)（訂單）最大延期最小RANDOM法則：隨機(jī)地挑一個(gè)工件3.3常用的優(yōu)先順序規(guī)則[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃18MWKR（Mostworkremaining）法則19

例：一個(gè)加工車間負(fù)責(zé)加工發(fā)動(dòng)機(jī)機(jī)殼，現(xiàn)在共有5個(gè)機(jī)殼等待加工。只有一名技工在崗，做此項(xiàng)工作?，F(xiàn)在已經(jīng)估算出各個(gè)機(jī)殼的標(biāo)準(zhǔn)加工時(shí)間，顧客也已經(jīng)明確提出了他們所希望的完工時(shí)間，采用SPT法則和EDD法則，求工件的加工順序。19例：一個(gè)加工車間負(fù)責(zé)加工發(fā)動(dòng)機(jī)機(jī)殼，現(xiàn)在共202021

EDD規(guī)則（優(yōu)先選擇完工期限最緊的工作）排序結(jié)果

比較SPT規(guī)則和EDD規(guī)則的排序結(jié)果，用SPT規(guī)則排序，其平均流程時(shí)間更短，減少在制品量，但平均延遲較大。用EDD規(guī)則，可以給顧客提供更好的服務(wù)（平均延遲時(shí)間較少），它也提供了更低的總庫(kù)存水平，但平均流程時(shí)間較長(zhǎng)。21EDD規(guī)則（優(yōu)先選擇完工期限最緊的工作）排序結(jié)果22

流水車間(Flowshop)：工件的加工路線都一致。在流水線上制造不同的零件，即流水作業(yè)的排序問題。上面說的加工線路一致，是指工件的流向一致，并不是指每個(gè)工件必須經(jīng)過加工線路上的每臺(tái)機(jī)器加工。如果某些工件不經(jīng)某些機(jī)器加工，則設(shè)相應(yīng)的加工時(shí)間為零。本節(jié)主要考慮：（1）最長(zhǎng)流程時(shí)間的計(jì)算（2）兩臺(tái)機(jī)器排序問題的最優(yōu)算法4.1前言[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃22流水車間(Flowshop)：工件的加工路線都一致。23

n/m/P/Fmax問題，其中n為工件數(shù)，m為機(jī)器數(shù)，P表示流水作業(yè)的排序問題，F(xiàn)max為目標(biāo)函數(shù)。n個(gè)零件要按相同的加工路線經(jīng)過m臺(tái)機(jī)器加工，目標(biāo)是使這批零件的最長(zhǎng)流程時(shí)間最短。最長(zhǎng)流程時(shí)間又稱加工周期，它是從第一個(gè)零件在第一臺(tái)機(jī)器開始加工時(shí)算起，到最后一個(gè)零件在最后一臺(tái)機(jī)器上完成加工時(shí)為止所經(jīng)過的時(shí)間。假設(shè)：所有工件的到達(dá)時(shí)間都為零4.2最長(zhǎng)流程時(shí)間的計(jì)算

[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃23n/m/P/Fmax問題，其中n為工件數(shù)，m為機(jī)器數(shù)24

例：6/4/P/Fmax問題，加工時(shí)間如表所示。當(dāng)按順序S=(6,1,5,2,4,3)加工時(shí)，求Fmax。序號(hào)為3的工件在序號(hào)為2的機(jī)器上的加工時(shí)間為6[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃24例：6/4/P/Fmax問題，加工時(shí)間如表所示。當(dāng)按25

例：6/4/P/Fmax問題，加工時(shí)間如表所示。當(dāng)按順序S=(6,1,5,2,4,3)加工時(shí)，求Fmax。按順序S=(6,1,5,2,4,3)列出加工時(shí)間矩陣。

615243Pi1244213Pi2544576Pi3555857Pi41432342712134+max{7,6}=1111

15202733

1722303542

2125323846610121316[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃25例：6/4/P/Fmax問題，加工時(shí)間如表所示。當(dāng)按26

約翰森算法（1）從加工時(shí)間矩陣中找出最短加工時(shí)間；（2）若最短加工時(shí)間出現(xiàn)在機(jī)器M1上，則對(duì)應(yīng)工件應(yīng)該盡可能往前排；若最短加工時(shí)間出現(xiàn)在機(jī)器M2上，則對(duì)應(yīng)工件應(yīng)該盡可能往后排。然后從加工時(shí)間矩陣中劃去已排序工件的加工時(shí)間。若最短加工時(shí)間有多個(gè)，則任挑一個(gè)。（3）若所有工件都已排序，停止。否則，轉(zhuǎn)步驟1。4.3兩臺(tái)機(jī)器排序問題的最優(yōu)算法[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃26約翰森算法4.3兩臺(tái)機(jī)器排序問題的最優(yōu)算法[關(guān)鍵內(nèi)容27例：將工件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)加工順序?yàn)镾=(2,5,6,1,4,3),Fmax=28I123456Ai518534Bi722474[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃27例：將工件2排在第1位2I28

約翰森算法的改進(jìn)（1）將所有ai≤bi的工件按ai值不減的順序排成一個(gè)序列A；（2）將ai＞bi的工件按bi值不增的順序排成一個(gè)序列B；（3）將A放到B之前，就構(gòu)成了一個(gè)最優(yōu)加工順序。4.3兩臺(tái)機(jī)器排序問題的最優(yōu)算法[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序問題5.服務(wù)業(yè)的作業(yè)計(jì)劃28約翰森算法的改進(jìn)4.3兩臺(tái)機(jī)器排序問題的最優(yōu)算法[關(guān)29例：工件號(hào)123456

ai518534

bi722474最優(yōu)順序256143

134558274742

4

8

13

18

2631115222628

ai

bi最優(yōu)順序下的加工周期為28[關(guān)鍵內(nèi)容]:1.引言2.排序問題的基本概念3.單臺(tái)機(jī)器的排序問題4.兩臺(tái)（或多臺(tái)）機(jī)器流水作業(yè)的排序