運營管理- 作業(yè)計劃課件

Scheduling

作業(yè)計劃

Scheduling

作業(yè)計劃運營管理--作業(yè)計劃作業(yè)計劃的目的作業(yè)計劃的目的作業(yè)計劃(Scheduling)作業(yè)計劃(Scheduling):作業(yè)計劃是安排零部件（作業(yè)、活動）的出產(chǎn)數(shù)量、設(shè)備及人工使用、投入時間及出產(chǎn)時間。

滿足交貨期要求

使在制品庫存最小

使平均流程時間最小

提供準(zhǔn)確的工件狀態(tài)信息

提高機器/工人的時間利用率

減少調(diào)整準(zhǔn)備時間

使生產(chǎn)和人工成本最低作業(yè)計劃(Scheduling)作業(yè)計劃(Scheduli甘特圖普利茅斯福特龐蒂亞克任務(wù)4/204/224/234/244/254/264/214/174/184/19當(dāng)前日期計劃時間實際進度活動開始活動結(jié)束非工作時間甘特圖普利茅斯福特龐蒂亞克任務(wù)4/204/224/234/2甘特圖醫(yī)院手術(shù)室甘特圖醫(yī)院手術(shù)室制定作業(yè)計劃的主要原則

工件流動(物流)帶來價值

=現(xiàn)金流物流通過車間的速度

=效率將工件流安排成一連續(xù)過程

–流程上一步接一步避免工作中斷動態(tài)安排作業(yè)計劃未完成任務(wù)要能夠及時反饋投入工作地的任務(wù)與能力要匹配發(fā)現(xiàn)瓶頸

–動態(tài)特征找出工程設(shè)計與制造執(zhí)行過程之間的不相容性制定作業(yè)計劃的主要原則 工件流動(物流)帶來價值=現(xiàn)金流大量生產(chǎn)類型的作業(yè)計劃

成批生產(chǎn)類型的作業(yè)計劃

單件小批生產(chǎn)類型作業(yè)計劃另外，還有其他分類：

車間作業(yè)計劃

人力計劃

設(shè)施計劃

車輛調(diào)度計劃

供應(yīng)商計劃

工程項目計劃

動態(tài)計劃和靜態(tài)計劃作業(yè)計劃的種類

大量生產(chǎn)類型的作業(yè)計劃作業(yè)計劃的種類 排序的基本概念

(Sequencing)在編制作業(yè)計劃過程中,有一個問題需要管理人員注意,即投入生產(chǎn)過程的作業(yè)順序的安排.排序:給出零部件在一臺或一組設(shè)備上加工的先后順序的工作。編制作業(yè)計劃的主要工作之一就是要確定出最佳的作業(yè)順序。

排序的基本概念(Sequencing)在編制作業(yè)計劃過程運營管理--作業(yè)計劃運營管理--作業(yè)計劃根據(jù)機器數(shù)的多少

單臺機器的排序問題;多臺機器的排序問題

根據(jù)加工路線的特征單件車間排序(JobShop);流水型排序(FlowShop)

根據(jù)工件到達系統(tǒng)的情況

靜態(tài)排序;動態(tài)排序根據(jù)參數(shù)的性質(zhì)確定型排序;隨機型排序

根據(jù)要實現(xiàn)的目標(biāo)

單目標(biāo)排序;多目標(biāo)排序

排序問題的分類根據(jù)機器數(shù)的多少排序問題的分類運營管理--作業(yè)計劃

Ji----工件i，i=1,2,....ndi----工件i的交貨期

Pi----工件i的加工時間,,pij----工件i在機器j上的加工時間,j=1,…,m

Wi----工件i在系統(tǒng)內(nèi)的等待時間,,wij----工件i在機器j前的等待時間,j=1,…,m

Ci----工件i的完成時間,在工件都已到達的情況下,Ci=Pi+Wi

Fi----工件i的流程時間，在工件都已到達的情況下,Fi=Pi+Wi

Li----工件i的延誤時間,Li=Ci-di,Li<=0按期或完成提前；

Li>0延誤

Ti----工件i的延期量,Ti=max{0,Li}Ei----工件i提前完成的時間排序常用的符號Wi----工件i在系統(tǒng)內(nèi)的等待時間,ShippingDepartment生產(chǎn)流程RawMaterialsLegend:BatchofpartsWorkstationShippingDepartment生產(chǎn)流程RawMat單臺機器的排序問題

單臺機器排序問題

n個工件全部經(jīng)由一臺機器處理

J1J2J3Jn

機器到達系統(tǒng)工件的集合離開系統(tǒng)（機器）單臺機器的排序問題單臺機器排序問題J1機器到達系統(tǒng)工件根據(jù)排序目標(biāo)的不同，可以選擇不同的排序規(guī)則，有時又稱為確定優(yōu)先權(quán)(Priorities)。常見的優(yōu)先權(quán)規(guī)則(Priorityrules)有：最短加工時間SPT---ShortestProcessTime,最早交付時間EDD---EarliestDueDate先到先得FCFS---FirstComeFirstServedCR關(guān)鍵比例---CriticalRate排序規(guī)則根據(jù)排序目標(biāo)的不同，可以選擇不同的排序規(guī)則，有時又稱為確定優(yōu)平均流程時間最短的排序問題

求平均流程時間最短的作業(yè)順序，采用SPT原則。

按工件加工時間的長短，按不減的順序從小到大安排各項作業(yè)。

例：一個車間有一臺加工中心，現(xiàn)有5個工件需要該機器加工。相關(guān)的加工時間和要求完成時間（交貨期）如下表所示，求平均流程時間最短的作業(yè)順序。

J1

J2

J3

J4

J5

加工時間

11

29

31

1

2

交貨期

61

45

31

33

32

平均流程時間最短的排序問題求平均流程時間最短的作業(yè)順序解：根據(jù)SPT原則，得出：J4-J5-J1-J2-J3

有關(guān)項目的計算：

加工時間

完成時間交貨期

延遲

J4

1

1

33

0

J5

2

3

32

0

J1

11

14

61

0

J229

43

45

0

31

74

31

43

J3

解：根據(jù)SPT原則，得出：

加工時間完成時間交貨期延最大延期量最小的排序問題

求最大延期量最小的作業(yè)順序采用EDD原則。

EDD(EarliestDueDate):Jobsaresequencedinincreasingorderoftheirduedates.例：借用上面的例子，求最大延期量最小的作業(yè)順序。解：根據(jù)EDD原則，得出：J3-J5-J4-J2-J1

加工時間

完成時間

交貨期

延遲

J3

31

31

31

0

J5

2

33

32

1

J4

1

34

33

1

J2

29

63

45

18

J1

11

74

61

13

最大延期量最小的排序問題求最大延期量最小的作業(yè)順序采用ED平均延遲=33/5=6.6

=18

進一步考慮：在最大延期量不變的情況下，如何使平均流程時間縮短？如果想同時滿足這兩個目標(biāo)，就是多目標(biāo)排序。平均延遲=33/5=6.6=18進一步考慮：在最大延期量綜合原則例:在一臺設(shè)備上安排6個工件的加工任務(wù)，每項任務(wù)的作業(yè)時間和交貨期如下表所示。J1J2

J3

J4

J5

J6

作業(yè)時間324865交貨期要求6310202830在滿足Tmax最小的情況下，使平均流程時間最小。綜合原則例:在一臺設(shè)備上安排6個工件的加工任務(wù)，每項任務(wù)的1、首先使用EDD規(guī)則排序

J2J1

J3

J4

J5

J6

2、求出所有作業(yè)的總操作時間TT=283、求出交貨期不小于T的任務(wù)項，然后按其加工時間的大小調(diào)整，將加工時間上的任務(wù)調(diào)整到后面。如本例，J5，J6滿足要求，因為t5>t6,所以：J2J1

J3

J4

J6

J5

4、去掉已調(diào)整的任務(wù)，重復(fù)2-4步。

最后得最優(yōu)解：

J2J1

J3

J4

J6

J5

F=13.671、首先使用EDD規(guī)則排序J2J1J3J4Jn項任務(wù)在兩臺機器的排序問題

SchedulingnJobsonTwoMachines兩臺機器排序問題的含義n個工件都必須經(jīng)過機器1和機器2的加工，即工藝路線是一致的。

機器1到達系統(tǒng)工件的集合離開系統(tǒng)（機器）J1J2J3Jn

機器2n項任務(wù)在兩臺機器的排序問題

SchedulingnJo兩臺機器排序問題的目標(biāo)

兩臺機器排序的目標(biāo)是使最大完成時間（總加工周期）Fmax最短。

Fmax的含義見如下的甘特圖(GanttChart)。多臺機器排序的目標(biāo)一般也是使最大完成時間（總加工周期）

Fmax最短。Fmax

時間

機器

A

B在機器A上的作業(yè)時間總加工周期兩臺機器排序問題的目標(biāo)兩臺機器排序的目標(biāo)是使最大完成時間（總加工周期的計算方法工件在兩臺設(shè)備上的加工時間工件編號

J1J2J3J4J5

設(shè)備A

36715

設(shè)備B

28643

例:在設(shè)備A和B上安排5個工件的加工任務(wù)，每項任務(wù)的作業(yè)時間如下表所示。求:該順序的總加工周期Fmax。圖解法：30AB0總加工周期的計算方法工件在兩臺設(shè)備上的加工時間工件編號實現(xiàn)兩臺機器排序的最大完成時間Fmax最短的目標(biāo)，一優(yōu)化算法就是著名的約翰遜法(Johnson’sLaw)。其具體求解過程如下例所示。約翰遜法解決這種問題分為4個步驟：

(1)列出所有工件在兩臺設(shè)備上的作業(yè)時間。

(2)找出作業(yè)時間最小者。

(3)如果該最小值是在設(shè)備1上，將對應(yīng)的工件排在前面，如果該最小值是在設(shè)備2上，則將對應(yīng)的工件排在后面。

(4)排除已安排好的工件，在剩余的工件中重復(fù)步驟(2)和(3)，直到所有工件都安排完畢。

兩臺機器排序問題實現(xiàn)兩臺機器排序的最大完成時間Fmax最短的目標(biāo)，一優(yōu)化算法EliminateM3fromconsideration.ThenextshortesttimeisM2atWorkstation1,soscheduleM2first.EliminateM5fromconsideration.ThenextshortesttimeisM1atworkstation#1,soscheduleM1next.EliminateM1andtheonlyjobremainingtobescheduledisM4.約翰遜法則attheMorrisMachineCo.

時間(hr)工件 工序1 工序2M1 12 22M2 4 5M3 5 3M4 15 16M5 10 8Sequence=M1M2M3M4M5Shortesttimeis3hoursatworkstation2,soschedulejobM3last.EliminateM2fromconsideration.ThenextshortesttimeisM5atworkstation#2,soscheduleM5nexttolast.EliminateM3fromconsideratioWorkstationM2(4)M1(12)M4(15)M5(10)M3(5)Idle—availableforfurtherwork051015202530Day35404550556065Idle2M2(5)M1(22)M4(16)M5(8)M3(3)Idle1GanttChartfortheMorrisMachineCompanyRepairSchedule約翰遜法則attheMorrisMachineCo.

WorkstationM2(4)M1(12)M4(15例：某一班組有A、B兩臺設(shè)備，要完成5個工件的加工任務(wù)。每個工件在設(shè)備上的加工時間如下表所示。求總加工周期最短的作業(yè)順序。

工件在兩臺設(shè)備上的加工時間

工件編號

J1J2J3J4J5

設(shè)備A

36715

設(shè)備B

28643

例：某一班組有A、B兩臺設(shè)備，要完成5個工件的加工任務(wù)。每個解：由約翰遜法可知，表5-8中最小加工時間值是1個時間單位，它又是出現(xiàn)在設(shè)備1上，根據(jù)約翰遜法的規(guī)則，應(yīng)將對應(yīng)的工件4排在第一位，即得：

J4-*-*-*-*

去掉J4，在剩余的工件中再找最小值，不難看出，最小值是2個時間單位，它是出現(xiàn)在設(shè)備2上的，所以應(yīng)將對應(yīng)的工件J1排在最后一位，即：

J4-*-*-*-J1

再去掉J1，在剩余的J2、J3、J5中重復(fù)上述步驟，求解過程為：

J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1

當(dāng)同時出現(xiàn)多個最小值時，可從中任選一個。最后得J4-J2-J3-J5-J1解：由約翰遜法可知，表5-8中最小加工時間值是1個時間單位，(a)J1-J2-J3-J4-J526AB(b)J4-J2-J3-J5-J1可以看出，初始作業(yè)順序的總加工周期是30，用約翰遜法排出的作業(yè)順序總加工周期是26，顯然后者的結(jié)果優(yōu)于前者。30AB0(a)J1-J2-J3-J4-J526A

幾種調(diào)度準(zhǔn)則的比較FCFS-First-Come-First-Served

看似“公平”，但是沒有運用已有信息.通常用于服務(wù)業(yè)的排對系統(tǒng)

(銀行,商店)LCFS-Last-Come-First-Served

該準(zhǔn)則通常是缺省情況下發(fā)生的，到達的工件被依次放到最上面.

SPT-ShortestProcessingTime在給定的時間內(nèi)能完成最多的任務(wù)，并且能使平均等待最小.但是使有些任務(wù)大大推遲完成.EDD-EarliestDueDate試圖達到平均延期和最大延期最小.但是需要正確的交貨期.STR-SlackTimeRemaining

使任何任務(wù)（訂單）最大延期最小.動態(tài)計算CR-CriticalRatio

該比值表明訂單是超前

(CR>1),準(zhǔn)時

(CR=1)還是延遲

(CR<1).

STR/OP–SlackTimeperRemainingOperation

與STR類似,但是著眼于將來的作業(yè)活動幾種調(diào)度準(zhǔn)則的比較FCFS-First-Come-Fi

Scheduling

作業(yè)計劃

Scheduling

作業(yè)計劃運營管理--作業(yè)計劃作業(yè)計劃的目的作業(yè)計劃的目的作業(yè)計劃(Scheduling)作業(yè)計劃(Scheduling):作業(yè)計劃是安排零部件（作業(yè)、活動）的出產(chǎn)數(shù)量、設(shè)備及人工使用、投入時間及出產(chǎn)時間。

滿足交貨期要求

使在制品庫存最小

使平均流程時間最小

提供準(zhǔn)確的工件狀態(tài)信息

提高機器/工人的時間利用率

減少調(diào)整準(zhǔn)備時間

使生產(chǎn)和人工成本最低作業(yè)計劃(Scheduling)作業(yè)計劃(Scheduli甘特圖普利茅斯福特龐蒂亞克任務(wù)4/204/224/234/244/254/264/214/174/184/19當(dāng)前日期計劃時間實際進度活動開始活動結(jié)束非工作時間甘特圖普利茅斯福特龐蒂亞克任務(wù)4/204/224/234/2甘特圖醫(yī)院手術(shù)室甘特圖醫(yī)院手術(shù)室制定作業(yè)計劃的主要原則

工件流動(物流)帶來價值

=現(xiàn)金流物流通過車間的速度

=效率將工件流安排成一連續(xù)過程

–流程上一步接一步避免工作中斷動態(tài)安排作業(yè)計劃未完成任務(wù)要能夠及時反饋投入工作地的任務(wù)與能力要匹配發(fā)現(xiàn)瓶頸

–動態(tài)特征找出工程設(shè)計與制造執(zhí)行過程之間的不相容性制定作業(yè)計劃的主要原則 工件流動(物流)帶來價值=現(xiàn)金流大量生產(chǎn)類型的作業(yè)計劃

成批生產(chǎn)類型的作業(yè)計劃

單件小批生產(chǎn)類型作業(yè)計劃另外，還有其他分類：

車間作業(yè)計劃

人力計劃

設(shè)施計劃

車輛調(diào)度計劃

供應(yīng)商計劃

工程項目計劃

動態(tài)計劃和靜態(tài)計劃作業(yè)計劃的種類

大量生產(chǎn)類型的作業(yè)計劃作業(yè)計劃的種類 排序的基本概念

(Sequencing)在編制作業(yè)計劃過程中,有一個問題需要管理人員注意,即投入生產(chǎn)過程的作業(yè)順序的安排.排序:給出零部件在一臺或一組設(shè)備上加工的先后順序的工作。編制作業(yè)計劃的主要工作之一就是要確定出最佳的作業(yè)順序。

排序的基本概念(Sequencing)在編制作業(yè)計劃過程運營管理--作業(yè)計劃運營管理--作業(yè)計劃根據(jù)機器數(shù)的多少

單臺機器的排序問題;多臺機器的排序問題

根據(jù)加工路線的特征單件車間排序(JobShop);流水型排序(FlowShop)

根據(jù)工件到達系統(tǒng)的情況

靜態(tài)排序;動態(tài)排序根據(jù)參數(shù)的性質(zhì)確定型排序;隨機型排序

根據(jù)要實現(xiàn)的目標(biāo)

單目標(biāo)排序;多目標(biāo)排序

排序問題的分類根據(jù)機器數(shù)的多少排序問題的分類運營管理--作業(yè)計劃

Ji----工件i，i=1,2,....ndi----工件i的交貨期

Pi----工件i的加工時間,,pij----工件i在機器j上的加工時間,j=1,…,m

Wi----工件i在系統(tǒng)內(nèi)的等待時間,,wij----工件i在機器j前的等待時間,j=1,…,m

Ci----工件i的完成時間,在工件都已到達的情況下,Ci=Pi+Wi

Fi----工件i的流程時間，在工件都已到達的情況下,Fi=Pi+Wi

Li----工件i的延誤時間,Li=Ci-di,Li<=0按期或完成提前；

Li>0延誤

Ti----工件i的延期量,Ti=max{0,Li}Ei----工件i提前完成的時間排序常用的符號Wi----工件i在系統(tǒng)內(nèi)的等待時間,ShippingDepartment生產(chǎn)流程RawMaterialsLegend:BatchofpartsWorkstationShippingDepartment生產(chǎn)流程RawMat單臺機器的排序問題

單臺機器排序問題

n個工件全部經(jīng)由一臺機器處理

J1J2J3Jn

機器到達系統(tǒng)工件的集合離開系統(tǒng)（機器）單臺機器的排序問題單臺機器排序問題J1機器到達系統(tǒng)工件根據(jù)排序目標(biāo)的不同，可以選擇不同的排序規(guī)則，有時又稱為確定優(yōu)先權(quán)(Priorities)。常見的優(yōu)先權(quán)規(guī)則(Priorityrules)有：最短加工時間SPT---ShortestProcessTime,最早交付時間EDD---EarliestDueDate先到先得FCFS---FirstComeFirstServedCR關(guān)鍵比例---CriticalRate排序規(guī)則根據(jù)排序目標(biāo)的不同，可以選擇不同的排序規(guī)則，有時又稱為確定優(yōu)平均流程時間最短的排序問題

求平均流程時間最短的作業(yè)順序，采用SPT原則。

按工件加工時間的長短，按不減的順序從小到大安排各項作業(yè)。

例：一個車間有一臺加工中心，現(xiàn)有5個工件需要該機器加工。相關(guān)的加工時間和要求完成時間（交貨期）如下表所示，求平均流程時間最短的作業(yè)順序。

J1

J2

J3

J4

J5

加工時間

11

29

31

1

2

交貨期

61

45

31

33

32

平均流程時間最短的排序問題求平均流程時間最短的作業(yè)順序解：根據(jù)SPT原則，得出：J4-J5-J1-J2-J3

有關(guān)項目的計算：

加工時間

完成時間交貨期

延遲

J4

1

1

33

0

J5

2

3

32

0

J1

11

14

61

0

J229

43

45

0

31

74

31

43

J3

解：根據(jù)SPT原則，得出：

加工時間完成時間交貨期延最大延期量最小的排序問題

求最大延期量最小的作業(yè)順序采用EDD原則。

EDD(EarliestDueDate):Jobsaresequencedinincreasingorderoftheirduedates.例：借用上面的例子，求最大延期量最小的作業(yè)順序。解：根據(jù)EDD原則，得出：J3-J5-J4-J2-J1

加工時間

完成時間

交貨期

延遲

J3

31

31

31

0

J5

2

33

32

1

J4

1

34

33

1

J2

29

63

45

18

J1

11

74

61

13

最大延期量最小的排序問題求最大延期量最小的作業(yè)順序采用ED平均延遲=33/5=6.6

=18

進一步考慮：在最大延期量不變的情況下，如何使平均流程時間縮短？如果想同時滿足這兩個目標(biāo)，就是多目標(biāo)排序。平均延遲=33/5=6.6=18進一步考慮：在最大延期量綜合原則例:在一臺設(shè)備上安排6個工件的加工任務(wù)，每項任務(wù)的作業(yè)時間和交貨期如下表所示。J1J2

J3

J4

J5

J6

作業(yè)時間324865交貨期要求6310202830在滿足Tmax最小的情況下，使平均流程時間最小。綜合原則例:在一臺設(shè)備上安排6個工件的加工任務(wù)，每項任務(wù)的1、首先使用EDD規(guī)則排序

J2J1

J3

J4

J5

J6

2、求出所有作業(yè)的總操作時間TT=283、求出交貨期不小于T的任務(wù)項，然后按其加工時間的大小調(diào)整，將加工時間上的任務(wù)調(diào)整到后面。如本例，J5，J6滿足要求，因為t5>t6,所以：J2J1

J3

J4

J6

J5

4、去掉已調(diào)整的任務(wù)，重復(fù)2-4步。

最后得最優(yōu)解：

J2J1

J3

J4

J6

J5

F=13.671、首先使用EDD規(guī)則排序J2J1J3J4Jn項任務(wù)在兩臺機器的排序問題

SchedulingnJobsonTwoMachines兩臺機器排序問題的含義n個工件都必須經(jīng)過機器1和機器2的加工，即工藝路線是一致的。

機器1到達系統(tǒng)工件的集合離開系統(tǒng)（機器）J1J2J3Jn

機器2n項任務(wù)在兩臺機器的排序問題

SchedulingnJo兩臺機器排序問題的目標(biāo)

兩臺機器排序的目標(biāo)是使最大完成時間（總加工周期）Fmax最短。

Fmax的含義見如下的甘特圖(GanttChart)。多臺機器排序的目標(biāo)一般也是使最大完成時間（總加工周期）

Fmax最短。Fmax

時間

機器

A

B在機器A上的作業(yè)時間總加工周期兩臺機器排序問題的目標(biāo)兩臺機器排序的目標(biāo)是使最大完成時間（總加工周期的計算方法工件在兩臺設(shè)備上的加工時間工件編號

J1J2J3J4J5

設(shè)備A

36715

設(shè)備B

28643

例:在設(shè)備A和B上安排5個工件的加工任務(wù)，每項任務(wù)的作業(yè)時間如下表所示。求:該順序的總加工周期Fmax。圖解法：30AB0總加工周期的計算方法工件在兩臺設(shè)備上的加工時間工件編號實現(xiàn)兩臺機器排序的最大完成時間Fmax最短的目標(biāo)，一優(yōu)化算法就是著名的約翰遜法(Johnson’sLaw)。其具體求解過程如下例所示。約翰遜法解決這種問題分為4個步驟：

(1)列出所有工件在兩臺設(shè)備上的作業(yè)時間。

(2)找出作業(yè)時間最小者。

(3)如果該最小值是在設(shè)備1上，將對應(yīng)的工件排在前面，如果該最小值是在設(shè)備2上，則將對應(yīng)的工件排在后面。

(4)排除已安排好的工件，在剩余的工件中重復(fù)步驟(2)和(3)，直到所有工件都安排完畢。

兩臺機器排序問題實現(xiàn)兩臺機器排序的最大完成時間Fmax最短的目標(biāo)，一優(yōu)化算法EliminateM3fromconsideration.ThenextshortesttimeisM2atWorkstation1,soscheduleM2first.EliminateM5fromconsideration.ThenextshortesttimeisM1atworkstation#1,soscheduleM1next.EliminateM1andtheonlyjobremainingtobescheduledisM4.約翰遜法則attheMorrisMachineCo.

時間(hr)工件 工序1 工序2M1 12 22M2 4 5M3 5 3M4 15 16M5 10 8Sequence=M1M2M3M4M5Shortesttimeis3hoursatworkstation2,soschedulejobM3last.EliminateM2fromconsideration.ThenextshortesttimeisM5atworkstation#2,soscheduleM5nexttolast.EliminateM3fromconsideratioWorkstationM2(4)M1(12)M4(15)M5(10)M3(5)Idle—availableforfurtherwork051015202530Day35404550556065Idle2M2(5)M1(22)M4(16)M5(8)M3(3)Idle1GanttChartfortheMorrisMachineCompanyRepairSchedule約翰遜法則atth