生產(chǎn)運(yùn)作管理課件：制造業(yè)生產(chǎn)作業(yè)計(jì)劃與控制

制造業(yè)生產(chǎn)作業(yè)計(jì)劃與控制調(diào)度—Scheduling調(diào)度(scheduling)詳細(xì)地計(jì)劃了短期內(nèi)要做的事，是將任務(wù)分配至資源的過程。將訂單、設(shè)備和人員分配到工作中心或者其他地方。（assignment）建立任務(wù)優(yōu)先級(jí)（sequencing）按照調(diào)度好的工作開始執(zhí)行。（dispatching）作業(yè)排序問題假設(shè)條件①一個(gè)零件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工。②零件在加工過程中采取平行移動(dòng)方式，即當(dāng)上一道工序完工后，立即送下道工序加工。③不允許中斷。當(dāng)一個(gè)零件一旦開始加工，必須一直進(jìn)行到完工，不得中途停止插入其它零件。④每道工序只在一臺(tái)機(jī)器上完成。⑤零件數(shù)、機(jī)器數(shù)和加工時(shí)間已知。⑥每臺(tái)機(jī)器同時(shí)只能加工一個(gè)零件。

Makespan完工時(shí)間Flowtime流程時(shí)間工件1工件2工件3排序問題表示法n/m/A/B,n為工件數(shù)，m機(jī)器數(shù)，A作業(yè)車間類型，B為目標(biāo)函數(shù)F：流水作業(yè)排序問題在流水生產(chǎn)線上制造不同的零件，遇到的就是流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個(gè)工件的加工路線都一致。P：流水作業(yè)排列排序問題F:(m1:j1,j2,j3m2:j2,j3,j1)P:(m1:j1,j2,j3m2:j1,j2,j3)G：一般單件作業(yè)排序問題每個(gè)工件有獨(dú)特的加工路線，工件沒有一定的流向?qū)τ谝话闱樾?，排列排序問題的最優(yōu)解不一定是相應(yīng)的流水作業(yè)排序問題的最優(yōu)解，但一般是比較好的解；對(duì)于僅有2臺(tái)和3臺(tái)機(jī)器的特殊情況，可以證明，排列排序問題下的最優(yōu)解一定是相應(yīng)流水作業(yè)排序問題的最優(yōu)解。加工周期的計(jì)算例：6/4/P/Fmax問題，按順序S=（6，1，5，2，4，3）加工，求Fmax

.i123456423142456745587555424331加工時(shí)間矩陣i615243244213544576555857143234i615243244213544576555857143234i615243224641021211331657411415520727633512517522830535742113421325232338446相同零件不同移動(dòng)方式下加工周期的計(jì)算

順序移動(dòng)方式完工時(shí)間時(shí)間工序1234順序移動(dòng)方式

平行移動(dòng)方式工序1234時(shí)間

完工時(shí)間特點(diǎn)：加工周期短，但運(yùn)輸頻繁，設(shè)備空閑時(shí)間多而零碎，不便利用。tL為最長的單件工序時(shí)間。

平行順序移動(dòng)方式

時(shí)間工序1234

完工時(shí)間

n項(xiàng)作業(yè)的單機(jī)調(diào)度（n/1）例：5個(gè)顧客在每周開始時(shí)后下訂單，數(shù)據(jù)如下。所有作業(yè)要使用唯一一臺(tái)復(fù)印機(jī)，使流程時(shí)間最小化。作業(yè)（按到達(dá)順序）加工時(shí)間（天）到期日（距離到期日的天數(shù)）A35B46C27D69E12FCFS原則（first-come，first-serverd）作業(yè)（按到達(dá)順序）加工時(shí)間（天）到期日流程時(shí)間（天）A350+3=3B463+4=7C277+2=9D699+6=15E1215+1=16總流程時(shí)間=3+7+9+15+16=50天平均每個(gè)作業(yè)延遲（0+1+2+6+14）/5=4.6天SOT原則（shortestoperatingtime）作業(yè)（按到達(dá)順序）加工時(shí)間（天）到期日流程時(shí)間（天）E120+1=1C271+2=3A353+3=6B466+4=10D6910+6=16總流程時(shí)間=1+3+6+10+16=36天平均每個(gè)作業(yè)延遲（0+0+1+4+7）/5=2.4天EDD原則（earliestduedatefirst）作業(yè)（按到達(dá)順序）加工時(shí)間（天）到期日流程時(shí)間（天）E120+1=1A351+3=4B464+4=8C278+2=10D6910+6=16總流程時(shí)間=1+4+8+10+16=39天平均每個(gè)作業(yè)延遲（0+0+2+3+7）/5=2.4天LCFS原則（Lastcome，firstserve）Randomn項(xiàng)作業(yè)的雙機(jī)調(diào)度問題（n/2）兩個(gè)或兩個(gè)以上的任務(wù)必須依照共同的工序在兩臺(tái)機(jī)器上進(jìn)行加工。約翰森法則（Johnson’srules）-最優(yōu)（1）列出兩臺(tái)機(jī)器上的每項(xiàng)任務(wù)的操作時(shí)間。（2）選擇最短操作時(shí)間。（3）如果操作時(shí)間最短的任務(wù)是第一臺(tái)機(jī)器能做出來的，那么就最先完成這項(xiàng)任務(wù)；如果操作時(shí)間最短的任務(wù)是第二臺(tái)機(jī)器能做出來的，那么就最后再做這項(xiàng)任務(wù)。如果兩臺(tái)機(jī)器能達(dá)到同樣的操作時(shí)間，那么就在第一臺(tái)機(jī)器上完成這項(xiàng)任務(wù)。（4）重復(fù)第2和第3步驟直到任務(wù)完成為止。例i123456ai518534bi722474將工件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

=？Johnson算法的改進(jìn)1.將所有ai≤bi的工件按ai值不減的順序排成一個(gè)序列A；2.將ai＞bi的工件按bi值不增的順序排成一個(gè)序列B；3.將A放到B之前，就構(gòu)成了一個(gè)最優(yōu)加工順序。工件號(hào)

1

2

3

4

5

6ai

5

1

8

5

3

4bi

7

2

2

4

7

4工件最優(yōu)順序：25

6

1

4

3

1

3

4

5

5

8

27

4

7

4

24

8

13

18

263

11

15

22

26

28aibi

最優(yōu)順序下的完工時(shí)間為28(2,5,6,4,1,3)?Jonhson法則只是充分條件，不是必要條件。最優(yōu)排序n項(xiàng)作業(yè)的n機(jī)調(diào)度（任務(wù)分配問題）

把n項(xiàng)任務(wù)分給n臺(tái)機(jī)器加工，有n!方案例：由4個(gè)零件可以分配給4臺(tái)機(jī)器加工，所需加工時(shí)間如下，求分配方案使總加工時(shí)間最小。M1M2M3M4J19735J2781211J34687J46111310匈牙利算法(1)從加工時(shí)間(費(fèi)用)矩陣每一行所有元素減去該行最小的元素，使每行至少出現(xiàn)一個(gè)零元素。(2)從實(shí)施第(1)步得到的矩陣中的每一列所有元素減去該列最小的元素，使每列至少出現(xiàn)一個(gè)零元素。(3)從實(shí)施第(2)步得到的矩陣中，劃出能覆蓋盡可能多的零元素的直線，如果線條數(shù)等于矩陣的行數(shù)，則已找到最優(yōu)矩陣，轉(zhuǎn)第(6)步；否則，轉(zhuǎn)第(4)步。(4)從矩陣中未被線條穿過的元素中減去這些元素中的最小數(shù)，并將這個(gè)最小數(shù)加到直線交叉的元素上，其余元素不變。(5)重復(fù)步驟(3)和步驟(4)，直到獲得最優(yōu)矩陣。（6）從僅有一個(gè)零的行或列開始，找出零元素對(duì)應(yīng)的分配方案，每行和每列僅能確定一個(gè)元素，最后使每行和每列都有一個(gè)零元素。零元素對(duì)應(yīng)的就是最優(yōu)分配方案。M1M2M3M4J19735J2781211J34687J46111310M1M2M3M4J16402J20154J30243J40574M1M2M3M4J16402J20154J30243J40574M1M2M3M4J16300J20052J30141J40472M1M2M3M4J16300J20052J30141J40472M1M2M3M4J16300J20052J30141J40472M1M2M3M4J16300J20052J30141J40472M1M2M3M4J16300J20041J30130J40461M1M2M3M4J17400J20041J30130J40461M1M2M3M4J17400J20041J30130J40461M1M2M3M4J17400J20041J30130J40461M1M2M3M4J17400J20041J30130J40461M1M2M3M4J17400J20041J30130J40461n項(xiàng)作業(yè)的m機(jī)調(diào)度（n/m）

例：一個(gè)4/3/F/Fmax問題，加工時(shí)間如下：i1234126384294582關(guān)鍵零件法1.計(jì)算每個(gè)工件的總加工時(shí)間，將加工時(shí)間最長的工件作為關(guān)鍵工件C；2.對(duì)于余下的工件，若pi1≤pim，則按pi1不減的順序排成一個(gè)序列Sa,若

pi1>pim

則按pim不增的順序排成一個(gè)序列Sb;3.順序（Sa,C,Sb）即為所求順序。

單件作業(yè)排序問題的描述加工描述矩陣D和加工時(shí)間矩陣T對(duì)應(yīng)D=1,1,1

1,2,3

1,3,22,1,3

2,2,1

2,3,2T=241345生產(chǎn)作業(yè)控制實(shí)行生產(chǎn)作業(yè)控制的原因和條件原因加工時(shí)間估計(jì)不準(zhǔn)確隨機(jī)因素的影響加工路線的多樣性企業(yè)環(huán)境的動(dòng)態(tài)性實(shí)施生產(chǎn)控制的條件要有控制標(biāo)準(zhǔn)——生產(chǎn)計(jì)劃和作業(yè)計(jì)劃取得實(shí)際進(jìn)度偏離計(jì)劃的信息能夠采取糾正行動(dòng)特點(diǎn)單件小批生產(chǎn)大量大批生產(chǎn)零件的流動(dòng)瓶