《生產(chǎn)與運(yùn)作管理》第八章：作業(yè)排序

1、Production & Operations ManagementProduction & Operations Management1生產(chǎn)與運(yùn)作管理生產(chǎn)與運(yùn)作管理浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院作業(yè)排序作業(yè)排序8C H A P T E RProduction & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 2生產(chǎn)運(yùn)作管理模型生產(chǎn)運(yùn)作管理模型輸入待轉(zhuǎn)化資源輸入待轉(zhuǎn)化資源物料物料信息信息顧客顧客輸入轉(zhuǎn)化資源輸入轉(zhuǎn)化資源設(shè)施設(shè)施 員工

2、員工顧客顧客輸入資源輸入資源輸出輸出產(chǎn)品與服務(wù)產(chǎn)品與服務(wù)改善改善計(jì)劃與計(jì)劃與控制控制設(shè)計(jì)設(shè)計(jì)運(yùn)作戰(zhàn)略運(yùn)作戰(zhàn)略企業(yè)戰(zhàn)略企業(yè)戰(zhàn)略作業(yè)排序作業(yè)排序Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 3本章主要內(nèi)容本章主要內(nèi)容n作業(yè)排序的基本概念作業(yè)排序的基本概念n作業(yè)排序的表示方式作業(yè)排序的表示方式n流水作業(yè)排序問題流水作業(yè)排序問題n單件作業(yè)排序問題單件作業(yè)排序問題n服務(wù)排隊(duì)系統(tǒng)設(shè)計(jì)中的心理因素服務(wù)排隊(duì)系統(tǒng)設(shè)計(jì)中的心理因素Production &

3、; Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 4n醫(yī)院醫(yī)院l門診病人治療門診病人治療l手術(shù)室手術(shù)室n大學(xué)大學(xué)l排課排課l教室教室n工廠工廠l生產(chǎn)生產(chǎn)l采購采購作業(yè)排序例子作業(yè)排序例子Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 5作業(yè)計(jì)劃與排序作業(yè)計(jì)劃與排序n作業(yè)排序作業(yè)排序(Sequencing)是確定加工對象是確

4、定加工對象的加工順序的加工順序n作業(yè)計(jì)劃作業(yè)計(jì)劃(Scheduling)還要確定開始加還要確定開始加工和完工的時(shí)間工和完工的時(shí)間n作業(yè)排序是作業(yè)計(jì)劃的關(guān)鍵作業(yè)排序是作業(yè)計(jì)劃的關(guān)鍵n在實(shí)際中，這兩個(gè)詞經(jīng)常被等同使用在實(shí)際中，這兩個(gè)詞經(jīng)常被等同使用Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 6作業(yè)排序的戰(zhàn)略目的作業(yè)排序的戰(zhàn)略目的n有效的排序可以提高設(shè)施的利用率，這有效的排序可以提高設(shè)施的利用率，這意味著：意味著：n有效的排序可以提高交貨速度，

5、這意味有效的排序可以提高交貨速度，這意味著：著：n好的排序提供好的排序提供更低的成本更低的成本更好的顧客服務(wù)更好的顧客服務(wù)更可靠的交貨更可靠的交貨Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 7前向排序與后向排序前向排序與后向排序收到收到訂單訂單交貨期交貨期訂購訂購原料原料作業(yè)作業(yè)1作業(yè)作業(yè)2作業(yè)作業(yè)3作業(yè)作業(yè)4訂購訂購原料原料作業(yè)作業(yè)1作業(yè)作業(yè)2作業(yè)作業(yè)3作業(yè)作業(yè)4前向排序前向排序后向排序后向排序請思考下列兩種情況下適用哪種排序方式？請思

6、考下列兩種情況下適用哪種排序方式？按訂單生產(chǎn)的企業(yè)按訂單生產(chǎn)的企業(yè)為節(jié)省庫存的費(fèi)用為節(jié)省庫存的費(fèi)用Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 8甘特圖（甘特圖（ Gantt Chart）n作業(yè)進(jìn)度圖作業(yè)進(jìn)度圖l表示一項(xiàng)工作的計(jì)劃開始日期、計(jì)劃完成日期表示一項(xiàng)工作的計(jì)劃開始日期、計(jì)劃完成日期以及現(xiàn)在的進(jìn)度以及現(xiàn)在的進(jìn)度n 機(jī)器圖（甘特負(fù)荷圖）機(jī)器圖（甘特負(fù)荷圖）l描述不同工作在每一臺機(jī)器上的工作次序，可描述不同工作在每一臺機(jī)器上的工作次序，

7、可被用來管理生產(chǎn)進(jìn)度被用來管理生產(chǎn)進(jìn)度 Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 9作業(yè)進(jìn)度甘特圖作業(yè)進(jìn)度甘特圖工作工作11/10 11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18 11/19ABC開始時(shí)間開始時(shí)間結(jié)束時(shí)間結(jié)束時(shí)間計(jì)劃所用時(shí)間計(jì)劃所用時(shí)間實(shí)際進(jìn)度實(shí)際進(jìn)度表示一項(xiàng)工作的計(jì)劃開始日期、計(jì)劃完成表示一項(xiàng)工作的計(jì)劃開始日期、計(jì)劃完成日期以及現(xiàn)在的進(jìn)度日期以及現(xiàn)在的進(jìn)度Producti

8、on & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 10描述不同工作在每一臺機(jī)器上的工作次序描述不同工作在每一臺機(jī)器上的工作次序機(jī)器甘特圖機(jī)器甘特圖機(jī)器機(jī)器11/11 11/12 11/13 11/14 11/15 11/16 11/17 11/18磨床磨床拋光機(jī)拋光機(jī)開始時(shí)間開始時(shí)間結(jié)束時(shí)間結(jié)束時(shí)間計(jì)劃所用時(shí)間計(jì)劃所用時(shí)間實(shí)際進(jìn)度實(shí)際進(jìn)度非生產(chǎn)性時(shí)間非生產(chǎn)性時(shí)間ABCABCProduction & Operations ManagementProduc

9、tion & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 11排序問題的分類排序問題的分類主要是將不同工件安排到不同設(shè)備上，或主要是將不同工件安排到不同設(shè)備上，或安排不同的人做不同的工作安排不同的人做不同的工作勞動力作業(yè)排序勞動力作業(yè)排序生產(chǎn)作業(yè)排序生產(chǎn)作業(yè)排序主要是確定人員何時(shí)工作主要是確定人員何時(shí)工作n兩種基本形式的作業(yè)排序兩種基本形式的作業(yè)排序Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商

10、管理學(xué)院 12制造業(yè)生產(chǎn)作業(yè)排序分類制造業(yè)生產(chǎn)作業(yè)排序分類按機(jī)器數(shù)按機(jī)器數(shù)量分類量分類單臺機(jī)器的單臺機(jī)器的排序問題排序問題多臺機(jī)器的多臺機(jī)器的排序問題排序問題單件作業(yè)排序問題單件作業(yè)排序問題(Job-Shop)流水作業(yè)排序問題流水作業(yè)排序問題(Flow-Shop)按工件到達(dá)車按工件到達(dá)車間的情況不同間的情況不同靜態(tài)排序問題靜態(tài)排序問題動態(tài)排序問題動態(tài)排序問題工件陸續(xù)到達(dá)，要隨時(shí)安排它們的加工順序工件陸續(xù)到達(dá)，要隨時(shí)安排它們的加工順序排序時(shí)，所有工件都已到達(dá)，可一次性進(jìn)行排序排序時(shí)，所有工件都已到達(dá)，可一次性進(jìn)行排序Production & Operations ManagementPr

11、oduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 13n個(gè)作業(yè)的單臺機(jī)器排序問題個(gè)作業(yè)的單臺機(jī)器排序問題(n/1)n對于某一工作地，在給定的一段時(shí)間內(nèi)，對于某一工作地，在給定的一段時(shí)間內(nèi)，順次決定下一個(gè)被加工的工件順次決定下一個(gè)被加工的工件n可能要考慮交付日期、在制品數(shù)量、全部可能要考慮交付日期、在制品數(shù)量、全部完工時(shí)間等因素完工時(shí)間等因素 對象對象1對象對象2對象對象3對象對象n工作地工作地Production & Operations ManagementProduction & Operations

12、Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 14常用的優(yōu)先順序規(guī)則常用的優(yōu)先順序規(guī)則先到先服務(wù)先到先服務(wù)優(yōu)先選擇完工期限最緊的工件優(yōu)先選擇完工期限最緊的工件優(yōu)先選擇加工時(shí)間最短的工件優(yōu)先選擇加工時(shí)間最短的工件優(yōu)先選擇臨界比最小的工件。臨界比為優(yōu)先選擇臨界比最小的工件。臨界比為工作允許停留時(shí)間和工件余下加工時(shí)間工作允許停留時(shí)間和工件余下加工時(shí)間之比之比優(yōu)先選擇余下加工時(shí)間最長的工件優(yōu)先選擇余下加工時(shí)間最長的工件優(yōu)先選擇余下加工時(shí)間最短的工件優(yōu)先選擇余下加工時(shí)間最短的工件優(yōu)先選擇余下工序數(shù)最多的工件優(yōu)先選擇余下工序數(shù)最多的工件隨機(jī)地挑選下一個(gè)工件隨機(jī)地挑選下一個(gè)工件FCF

13、S (First Come First Served)規(guī)則規(guī)則EDD (Earliest Due Date)規(guī)則規(guī)則SPT (Shortest Processing Time)規(guī)則規(guī)則SCR (Smallest Critical Ratio)規(guī)則規(guī)則MWKR (Most Work Remaining)規(guī)則規(guī)則LWRK (Least work Remaining)規(guī)則規(guī)則MOPNR (Most Operations Remaining)規(guī)則規(guī)則 RANDOM規(guī)則規(guī)則 規(guī)則規(guī)則解釋解釋Production & Operations ManagementProduction & Op

14、erations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 15最先到的工作先處理最先到的工作先處理n大多數(shù)作業(yè)排序標(biāo)準(zhǔn)能達(dá)到平均水平大多數(shù)作業(yè)排序標(biāo)準(zhǔn)能達(dá)到平均水平n對顧客來說是公平的對顧客來說是公平的l對服務(wù)組織更重要對服務(wù)組織更重要如如: : 餐廳餐廳先到先服務(wù)先到先服務(wù)FCFS, (First Come, First Served Rule)Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 16n優(yōu)先處理完工

15、時(shí)間最早的工作優(yōu)先處理完工時(shí)間最早的工作n被一些企業(yè)廣泛的應(yīng)用被一些企業(yè)廣泛的應(yīng)用l如果完工時(shí)間很重要如果完工時(shí)間很重要lMRPMRP系統(tǒng)系統(tǒng)完工時(shí)間完工時(shí)間n使最大延遲最小，提高客戶滿意水平使最大延遲最小，提高客戶滿意水平在許多排程標(biāo)準(zhǔn)上表現(xiàn)并不是太好在許多排程標(biāo)準(zhǔn)上表現(xiàn)并不是太好最早交貨時(shí)間最早交貨時(shí)間EDD（Earliest Due Date Rule）Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 17最短作業(yè)時(shí)間最短作業(yè)時(shí)間SPT（

16、Shortest Processing Time Rule）n優(yōu)先處理完工時(shí)間最短的工作優(yōu)先處理完工時(shí)間最短的工作n可以使工作流最小化，或系統(tǒng)中要完成的工作數(shù)可以使工作流最小化，或系統(tǒng)中要完成的工作數(shù)量最小化量最小化在單臺機(jī)器或單個(gè)工作中心（在單臺機(jī)器或單個(gè)工作中心（n/1）情況下）情況下使用平均延遲、平均等待時(shí)間和平均完成時(shí)間上使用平均延遲、平均等待時(shí)間和平均完成時(shí)間上都能產(chǎn)生最優(yōu)解。都能產(chǎn)生最優(yōu)解。最大的缺陷是工作時(shí)間長的工作將被不斷地最大的缺陷是工作時(shí)間長的工作將被不斷地推遲。推遲。Production & Operations ManagementProduction &

17、; Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 18最小臨界值最小臨界值(關(guān)鍵比率規(guī)劃關(guān)鍵比率規(guī)劃)SCR（Smallest Critical Ratio）n先處理臨界值最小的工作先處理臨界值最小的工作可以縮短平均延遲時(shí)間，有效地跟蹤記可以縮短平均延遲時(shí)間，有效地跟蹤記載工作進(jìn)展和位置載工作進(jìn)展和位置CR剩余時(shí)間剩余時(shí)間剩余工作時(shí)間剩余工作時(shí)間 完工期完工期 - 今日之日期今日之日期剩余工作時(shí)間剩余工作時(shí)間=Production & Operations ManagementProduction & Operations Mana

18、gement浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 19最長余下時(shí)間最長余下時(shí)間MWKR (Most Work Remaining)n優(yōu)先選擇余下加工時(shí)間最長的工作優(yōu)先選擇余下加工時(shí)間最長的工作Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 20最短余下時(shí)間最短余下時(shí)間LWRK (Least work Remaining)n優(yōu)先選擇余下工作時(shí)間最短的工作優(yōu)先選擇余下工作時(shí)間最短的工作Production & Operatio

19、ns ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 21最多余下作業(yè)最多余下作業(yè)MOPNR (Most Operations Remaining)n優(yōu)先選擇余下處理工序最多的工作優(yōu)先選擇余下處理工序最多的工作Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 22隨機(jī)規(guī)則隨機(jī)規(guī)則（RANDOM）n隨機(jī)挑選下一個(gè)工作隨機(jī)挑選下一個(gè)工作Producti

20、on & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 23作業(yè)排序方案的評價(jià)指標(biāo)作業(yè)排序方案的評價(jià)指標(biāo)n工件流程時(shí)間工件流程時(shí)間l從工件可以開始加工從工件可以開始加工(不一定是實(shí)際的開始時(shí)間不一定是實(shí)際的開始時(shí)間)至完工的時(shí)間至完工的時(shí)間n全部完工時(shí)間全部完工時(shí)間l完成一組工作所需的全部時(shí)間完成一組工作所需的全部時(shí)間 n延遲延遲l可以用比預(yù)定完工時(shí)間延遲了的時(shí)間部分來表示，也可以用未按預(yù)定時(shí)間可以用比預(yù)定完工時(shí)間延遲了的時(shí)間部分來表示，也可以用未按預(yù)定時(shí)間完工的工

21、件數(shù)占總工件數(shù)的百分比來表示完工的工件數(shù)占總工件數(shù)的百分比來表示n在制品庫存在制品庫存(WIP)l度量標(biāo)準(zhǔn)可以用工件個(gè)數(shù)、其貨幣價(jià)值或可供應(yīng)的周數(shù)來表示度量標(biāo)準(zhǔn)可以用工件個(gè)數(shù)、其貨幣價(jià)值或可供應(yīng)的周數(shù)來表示n總庫存總庫存l計(jì)劃入庫量和現(xiàn)有庫存量的總和為總庫存量計(jì)劃入庫量和現(xiàn)有庫存量的總和為總庫存量n利用率利用率l用一臺機(jī)器或一個(gè)工人的有效生產(chǎn)時(shí)間占總工作時(shí)間的百分比來表示用一臺機(jī)器或一個(gè)工人的有效生產(chǎn)時(shí)間占總工作時(shí)間的百分比來表示Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工

22、商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 24工作數(shù)量流程時(shí)間平均完工時(shí)間流程時(shí)間處理時(shí)間時(shí)間利用率 處理時(shí)間流程時(shí)間在制品）系統(tǒng)中的平均工作數(shù) (工作數(shù)量延遲時(shí)間平均延遲 作業(yè)排序方案的評價(jià)指標(biāo)（續(xù)）作業(yè)排序方案的評價(jià)指標(biāo)（續(xù)）Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 25作業(yè)排序目標(biāo)作業(yè)排序目標(biāo)n滿足交貨日期滿足交貨日期n提前期最短提前期最短n準(zhǔn)備時(shí)間最短或者成本最小準(zhǔn)備時(shí)間最短或者成本最小n在制品庫存最小在制品庫存最小n機(jī)器或勞動力利用

23、率最大機(jī)器或勞動力利用率最大l這一條有爭議，因?yàn)閮H僅考慮保持機(jī)器或者勞動力處于這一條有爭議，因?yàn)閮H僅考慮保持機(jī)器或者勞動力處于繁忙狀態(tài)可能不是在工序中進(jìn)行管理的最有效的方法繁忙狀態(tài)可能不是在工序中進(jìn)行管理的最有效的方法Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 26n/1排序問題例排序問題例n李生是李生是A復(fù)印公司的主管，復(fù)印公司為其所在市區(qū)的某復(fù)印公司的主管，復(fù)印公司為其所在市區(qū)的某法律公司提供復(fù)印服務(wù)，在這周開始，法律公司提供復(fù)印服務(wù)

24、，在這周開始，5個(gè)客戶提供了個(gè)客戶提供了他們的訂單。詳細(xì)的排序數(shù)據(jù)如下：他們的訂單。詳細(xì)的排序數(shù)據(jù)如下：作業(yè)（按到達(dá)順序）作業(yè)（按到達(dá)順序）加工時(shí)間（天）加工時(shí)間（天）交貨日期（從現(xiàn)在起天數(shù)）交貨日期（從現(xiàn)在起天數(shù)）A35B46C27D69E12所有的訂單都要使用唯一的彩色復(fù)印機(jī)，李生必須決所有的訂單都要使用唯一的彩色復(fù)印機(jī)，李生必須決定定5個(gè)訂單的加工順序，評價(jià)標(biāo)準(zhǔn)是流程時(shí)間最短。個(gè)訂單的加工順序，評價(jià)標(biāo)準(zhǔn)是流程時(shí)間最短。Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理

25、學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 27FCFS作業(yè)順序作業(yè)順序加工時(shí)間加工時(shí)間交貨日期交貨日期流程時(shí)間流程時(shí)間延遲延遲A350+3=30B463+4=7761C277+2=9972D699+6=151596E1215+1=1616214總流程時(shí)間總流程時(shí)間=3+7+9+15+16=50(天）天）平均流程時(shí)間平均流程時(shí)間=50/5=10(天）天）總延遲總延遲=0+1+2+6+14=23，平均延遲，平均延遲=23/5=4.6(天）天）Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管

26、理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 28SPT作業(yè)順序作業(yè)順序加工時(shí)間加工時(shí)間交貨日期交貨日期流程時(shí)間流程時(shí)間延遲延遲總流程時(shí)間總流程時(shí)間=平均流程時(shí)間平均流程時(shí)間=總延遲總延遲=，平均延遲，平均延遲=作業(yè)（按到達(dá)順序）作業(yè)（按到達(dá)順序）加工時(shí)間（天）加工時(shí)間（天）交貨日期（從現(xiàn)在起天數(shù)）交貨日期（從現(xiàn)在起天數(shù)）A35B46C27D69E12E120+1=10C271+2=30A353+3=66-5=1B466+4=1010-6=4D6910+6=1616-9=71+3+6+10+16=36(天天)36/5=7.2(天天)1+4+7=12 (天天)12/5=2.4(天天)Production &a

27、mp; Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 29EDD作業(yè)順序作業(yè)順序加工時(shí)間加工時(shí)間交貨日期交貨日期流程時(shí)間流程時(shí)間延遲延遲總流程時(shí)間總流程時(shí)間=平均流程時(shí)間平均流程時(shí)間=總延遲總延遲=，平均延遲，平均延遲=作業(yè)（按到達(dá)順序）作業(yè)（按到達(dá)順序）加工時(shí)間（天）加工時(shí)間（天）交貨日期（從現(xiàn)在起天數(shù)）交貨日期（從現(xiàn)在起天數(shù)）A35B46C27D69E12E120+1=10A351+3=40B464+4=88-6=2C278+2=1010-7=3D6910+6=1616

28、-9=71+4+8+10+16=39(天天)39/5=7.8(天天)2+3+7=12 (天天)12/5=2.4(天天)Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 30優(yōu)先調(diào)度規(guī)則對比優(yōu)先調(diào)度規(guī)則對比規(guī)劃規(guī)劃總完成時(shí)間總完成時(shí)間(天天)平均完成時(shí)間平均完成時(shí)間(天天)平均延遲平均延遲(天天)FCFS50104.6SPT367.22.4EDD397.82.4n從上面可看出，從上面可看出，SPT規(guī)則比其他規(guī)則較好，規(guī)則比其他規(guī)則較好，n事實(shí)上也

29、是這樣，用數(shù)學(xué)方法可以證明在事實(shí)上也是這樣，用數(shù)學(xué)方法可以證明在n/1情況下情況下使用其他衡量標(biāo)準(zhǔn)，如平均等待時(shí)間和平均完成時(shí)間使用其他衡量標(biāo)準(zhǔn)，如平均等待時(shí)間和平均完成時(shí)間，SPT都能產(chǎn)生最優(yōu)解。都能產(chǎn)生最優(yōu)解。n這種簡單的規(guī)則如此有用，以至于被稱為這種簡單的規(guī)則如此有用，以至于被稱為“整個(gè)排序整個(gè)排序科學(xué)中最重要的概念科學(xué)中最重要的概念”Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 31對在制品庫存的理解對在制品庫存的理解nn/1排序排

30、序n第一件工件開始生產(chǎn)前所有工件已經(jīng)達(dá)到，處于等待狀態(tài)第一件工件開始生產(chǎn)前所有工件已經(jīng)達(dá)到，處于等待狀態(tài)機(jī)殼加機(jī)殼加工次序工次序開始工作開始工作 加工時(shí)間加工時(shí)間 結(jié)束工作結(jié)束工作 流程時(shí)間流程時(shí)間在制品庫存貢獻(xiàn)在制品庫存貢獻(xiàn)E01111/16 0.0625A13444/160.25B44888/160.5C82101010/160.625D106161616/161總數(shù)總數(shù)392.4375平均在制品庫存平均在制品庫存39/162.4375Production & Operations ManagementProduction & Operations Management浙江

31、財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 32對總庫存的理解對總庫存的理解nn/1排序排序n第一件工件開始生產(chǎn)前所有工件已經(jīng)達(dá)到，處于等待狀態(tài)第一件工件開始生產(chǎn)前所有工件已經(jīng)達(dá)到，處于等待狀態(tài)機(jī)殼加機(jī)殼加工次序工次序加工時(shí)間加工時(shí)間 結(jié)束時(shí)間結(jié)束時(shí)間預(yù)計(jì)顧客預(yù)計(jì)顧客取貨時(shí)間取貨時(shí)間顧客實(shí)際顧客實(shí)際取貨時(shí)間取貨時(shí)間提前延遲提前延遲E11221A34551B48682C2107103D6169167總數(shù)總數(shù)3941212平均總庫存平均總庫存41/162.5625Production & Operations ManagementProduction & Operations M

32、anagement浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 33優(yōu)先規(guī)則及其事例（學(xué)生練習(xí)）優(yōu)先規(guī)則及其事例（學(xué)生練習(xí)）n例：一個(gè)加工車間負(fù)責(zé)加工發(fā)動機(jī)機(jī)殼，現(xiàn)在共例：一個(gè)加工車間負(fù)責(zé)加工發(fā)動機(jī)機(jī)殼，現(xiàn)在共有有5個(gè)機(jī)殼等待加工。只有一名技工在崗做此項(xiàng)個(gè)機(jī)殼等待加工。只有一名技工在崗做此項(xiàng)工作。現(xiàn)各個(gè)機(jī)殼的標(biāo)準(zhǔn)加工時(shí)間已經(jīng)被估算出工作?，F(xiàn)各個(gè)機(jī)殼的標(biāo)準(zhǔn)加工時(shí)間已經(jīng)被估算出來，顧客也已經(jīng)明確提出了他們所希望的完工時(shí)來，顧客也已經(jīng)明確提出了他們所希望的完工時(shí)間間n分別使用分別使用SPT和和EDD規(guī)則進(jìn)行排序，并計(jì)算這規(guī)則進(jìn)行排序，并計(jì)算這兩個(gè)方案的平均提前時(shí)間、延遲時(shí)間、在制品庫兩個(gè)方案的平

33、均提前時(shí)間、延遲時(shí)間、在制品庫存和總庫存存和總庫存Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 34發(fā)動機(jī)機(jī)殼的加工與取貨信息發(fā)動機(jī)機(jī)殼的加工與取貨信息發(fā)動機(jī)機(jī)殼發(fā)動機(jī)機(jī)殼所需標(biāo)準(zhǔn)加工時(shí)間所需標(biāo)準(zhǔn)加工時(shí)間(h)(包括機(jī)器調(diào)整包括機(jī)器調(diào)整)預(yù)計(jì)顧客取貨時(shí)間預(yù)計(jì)顧客取貨時(shí)間(h)(從現(xiàn)在開始算起的所需從現(xiàn)在開始算起的所需時(shí)間時(shí)間)機(jī)殼機(jī)殼1機(jī)殼機(jī)殼2機(jī)殼機(jī)殼3機(jī)殼機(jī)殼4機(jī)殼機(jī)殼586153121012201822一個(gè)加工車間負(fù)責(zé)加工發(fā)動機(jī)機(jī)殼，

34、現(xiàn)在共有一個(gè)加工車間負(fù)責(zé)加工發(fā)動機(jī)機(jī)殼，現(xiàn)在共有5個(gè)機(jī)殼等待加工。只個(gè)機(jī)殼等待加工。只有一名技工在崗做此項(xiàng)工作。現(xiàn)各個(gè)機(jī)殼的標(biāo)準(zhǔn)加工時(shí)間已經(jīng)被估算有一名技工在崗做此項(xiàng)工作?，F(xiàn)各個(gè)機(jī)殼的標(biāo)準(zhǔn)加工時(shí)間已經(jīng)被估算出來，顧客也已經(jīng)明確提出了他們所希望的完工時(shí)間。出來，顧客也已經(jīng)明確提出了他們所希望的完工時(shí)間。請給出分別使用請給出分別使用SPT和和EDD規(guī)則進(jìn)行排序，并計(jì)算這兩個(gè)方案規(guī)則進(jìn)行排序，并計(jì)算這兩個(gè)方案的平均提前時(shí)間、延遲時(shí)間、在制品庫存和總庫存的平均提前時(shí)間、延遲時(shí)間、在制品庫存和總庫存Production & Operations ManagementProduction &

35、; Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 35SPT規(guī)則排序結(jié)果規(guī)則排序結(jié)果機(jī)殼加機(jī)殼加工次序工次序開始工作開始工作 加工時(shí)間加工時(shí)間 結(jié)束工作結(jié)束工作 流程時(shí)間流程時(shí)間預(yù)計(jì)顧客預(yù)計(jì)顧客取貨時(shí)間取貨時(shí)間顧客實(shí)際顧客實(shí)際取貨時(shí)間取貨時(shí)間提前提前小時(shí)數(shù)小時(shí)數(shù)拖延拖延小時(shí)數(shù)小時(shí)數(shù)總數(shù)總數(shù)平均數(shù)平均數(shù)平均在制品庫存平均在制品庫存 平均總庫存平均總庫存機(jī)殼機(jī)殼4機(jī)殼機(jī)殼2機(jī)殼機(jī)殼1機(jī)殼機(jī)殼5機(jī)殼機(jī)殼3Production & Operations ManagementProduction & Operations Management

36、浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 36SPT規(guī)則排序結(jié)果規(guī)則排序結(jié)果機(jī)殼加機(jī)殼加工次序工次序開始工作開始工作 加工時(shí)間加工時(shí)間 結(jié)束工作結(jié)束工作 流程時(shí)間流程時(shí)間預(yù)計(jì)顧客預(yù)計(jì)顧客取貨時(shí)間取貨時(shí)間顧客實(shí)際顧客實(shí)際取貨時(shí)間取貨時(shí)間提前提前小時(shí)數(shù)小時(shí)數(shù)拖延拖延小時(shí)數(shù)小時(shí)數(shù)機(jī)殼機(jī)殼40333181815機(jī)殼機(jī)殼2369912123機(jī)殼機(jī)殼198171710177機(jī)殼機(jī)殼51712292922297機(jī)殼機(jī)殼329154444204424總數(shù)總數(shù)1021201838平均數(shù)平均數(shù)20.43.67.6平均在制品庫存平均在制品庫存102/442.32個(gè)個(gè) 平均總庫存平均總庫存120/44=2.7

37、3個(gè)個(gè)Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 37EDD規(guī)則排序結(jié)果規(guī)則排序結(jié)果機(jī)殼加機(jī)殼加工次序工次序開始工作開始工作 加工時(shí)間加工時(shí)間 結(jié)束工作結(jié)束工作 流程時(shí)間流程時(shí)間預(yù)計(jì)顧客預(yù)計(jì)顧客取貨時(shí)間取貨時(shí)間顧客實(shí)際顧客實(shí)際取貨時(shí)間取貨時(shí)間提前提前小時(shí)數(shù)小時(shí)數(shù)拖延拖延小時(shí)數(shù)小時(shí)數(shù)總數(shù)總數(shù)平均數(shù)平均數(shù)平均在制品庫存平均在制品庫存 平均總庫存平均總庫存機(jī)殼機(jī)殼1機(jī)殼機(jī)殼2機(jī)殼機(jī)殼4機(jī)殼機(jī)殼3機(jī)殼機(jī)殼5Production & Ope

38、rations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 38EDD規(guī)則排序結(jié)果規(guī)則排序結(jié)果機(jī)殼加機(jī)殼加工次序工次序開始工作開始工作 加工時(shí)間加工時(shí)間 結(jié)束工作結(jié)束工作 流程時(shí)間流程時(shí)間預(yù)計(jì)顧客預(yù)計(jì)顧客取貨時(shí)間取貨時(shí)間顧客實(shí)際顧客實(shí)際取貨時(shí)間取貨時(shí)間提前提前小時(shí)數(shù)小時(shí)數(shù)拖延拖延小時(shí)數(shù)小時(shí)數(shù)機(jī)殼機(jī)殼1088810102機(jī)殼機(jī)殼286141412142機(jī)殼機(jī)殼4143171718181機(jī)殼機(jī)殼317153232203212機(jī)殼機(jī)殼532124444224422總數(shù)總數(shù)115118336平均數(shù)平均

39、數(shù)230.67.2平均在制品庫存平均在制品庫存115/44=2.61 平均總庫存平均總庫存118/44=2.68Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 39流水作業(yè)排序問題流水作業(yè)排序問題n流水作業(yè)排序問題的基本特征是每個(gè)工流水作業(yè)排序問題的基本特征是每個(gè)工件的加工路線都一致件的加工路線都一致n討論討論所有工件在各臺機(jī)器上的加工順序所有工件在各臺機(jī)器上的加工順序都相同的情況都相同的情況Production & Operatio

40、ns ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 40最長流程時(shí)間最長流程時(shí)間n最長流程時(shí)間又稱加工周期最長流程時(shí)間又稱加工周期n是第一個(gè)工件在一臺機(jī)器開始加工時(shí)算起，到是第一個(gè)工件在一臺機(jī)器開始加工時(shí)算起，到最后一個(gè)工件在最后一臺機(jī)器上完工時(shí)為至所最后一個(gè)工件在最后一臺機(jī)器上完工時(shí)為至所經(jīng)過的時(shí)間經(jīng)過的時(shí)間n假定所有工件到達(dá)時(shí)間為零，則假定所有工件到達(dá)時(shí)間為零，則最長流程時(shí)間最長流程時(shí)間=排在末位加工工件在車間的停排在末位加工工件在車間的停留時(shí)間留時(shí)間n流水作業(yè)排序一個(gè)目標(biāo)函數(shù)：最長流程時(shí)間

41、最流水作業(yè)排序一個(gè)目標(biāo)函數(shù)：最長流程時(shí)間最短短Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 41最長流程時(shí)間最長流程時(shí)間n設(shè)設(shè)n個(gè)工件的加工順序?yàn)閭€(gè)工件的加工順序?yàn)镾=(S1,S2,Sn)iksC1111iiissspCCksskskksiiiipCCC)()1(1,max表示工件表示工件Si在機(jī)器在機(jī)器Mk上的完工時(shí)間上的完工時(shí)間ksip表示工件表示工件Si在機(jī)器在機(jī)器Mk上的加工時(shí)間上的加工時(shí)間Production & Oper

42、ations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 42加工順序矩陣加工順序矩陣i615243Pi1244213Pi2544576Pi3555857Pi4143234Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 43加工順序矩陣加工順序矩陣圖示解釋圖示解釋1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1

43、7 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46機(jī)器機(jī)器1機(jī)器機(jī)器2機(jī)器機(jī)器3機(jī)器機(jī)器4時(shí)間時(shí)間Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 44n個(gè)作業(yè)兩臺機(jī)器排序問題個(gè)作業(yè)兩臺機(jī)器排序問題(n/2)n兩個(gè)或者更多以上的作業(yè)必須在兩臺機(jī)器兩個(gè)或者更多以上的作業(yè)必須在兩臺機(jī)器上以共同的工序進(jìn)行加工上以共同的工序進(jìn)行

44、加工n評價(jià)標(biāo)準(zhǔn)：從第一個(gè)作業(yè)開始到最后一個(gè)評價(jià)標(biāo)準(zhǔn)：從第一個(gè)作業(yè)開始到最后一個(gè)作業(yè)結(jié)束的總流程時(shí)間最短，即全部完工作業(yè)結(jié)束的總流程時(shí)間最短，即全部完工時(shí)間最短時(shí)間最短Johnson方法（約翰遜方方法（約翰遜方法）法）Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 45nN項(xiàng)作業(yè)按相同順序經(jīng)過項(xiàng)作業(yè)按相同順序經(jīng)過2臺機(jī)器加工，使全臺機(jī)器加工，使全部完工時(shí)間最小部完工時(shí)間最小nN項(xiàng)作業(yè)的雙機(jī)排序（項(xiàng)作業(yè)的雙機(jī)排序（N/2）鋸鋸鉆鉆工作工作 A工作

45、工作 B工作工作 C工作工作 (N = 3)Johnson方法（約翰遜方法）方法（約翰遜方法）Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 46Johnson方法方法 - N項(xiàng)作業(yè)的雙機(jī)排序項(xiàng)作業(yè)的雙機(jī)排序(1)列出每個(gè)作業(yè)在兩臺機(jī)器上的加工時(shí)間列出每個(gè)作業(yè)在兩臺機(jī)器上的加工時(shí)間(2)選擇最短的加工時(shí)間。如果最短的加工時(shí)間選擇最短的加工時(shí)間。如果最短的加工時(shí)間來自第一臺機(jī)器，那么先完成這個(gè)作業(yè)；如果來來自第一臺機(jī)器，那么先完成這個(gè)作業(yè)；如果

46、來自第二臺機(jī)器，那么這個(gè)作業(yè)就放在最后完成自第二臺機(jī)器，那么這個(gè)作業(yè)就放在最后完成(3)刪除已排序作業(yè)刪除已排序作業(yè)(4)對剩余作業(yè)重復(fù)步驟對剩余作業(yè)重復(fù)步驟(2)和和(3)，直到所有，直到所有作業(yè)排序完畢作業(yè)排序完畢Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 47列出作業(yè)及加工時(shí)間列出作業(yè)及加工時(shí)間全部安排全部安排完畢完畢?Yes12YesNoNoJohnson法的步驟法的步驟選擇加工時(shí)間選擇加工時(shí)間最短的作業(yè)最短的作業(yè)哪臺機(jī)器？哪臺機(jī)

47、器？先完成這一作業(yè)先完成這一作業(yè)最后完成這一作業(yè)最后完成這一作業(yè)刪除這一作業(yè)刪除這一作業(yè)還有剩余還有剩余作業(yè)嗎？作業(yè)嗎？結(jié)束結(jié)束強(qiáng)制結(jié)束強(qiáng)制結(jié)束Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 48Johnson法法 例子例子作業(yè)作業(yè)工作工作1工作工作2Y11222Y245Y353Y41516Y5108(1)列出每個(gè)作業(yè)在兩臺機(jī)器上的加工時(shí)間列出每個(gè)作業(yè)在兩臺機(jī)器上的加工時(shí)間(2)選擇最短的加工時(shí)間。如果最短的加工時(shí)間來自第一臺機(jī)器，那么先完成

48、這個(gè)作選擇最短的加工時(shí)間。如果最短的加工時(shí)間來自第一臺機(jī)器，那么先完成這個(gè)作業(yè)；如果來自第二臺機(jī)器，那么這個(gè)作業(yè)就放在最后完成業(yè)；如果來自第二臺機(jī)器，那么這個(gè)作業(yè)就放在最后完成(3)刪除已排序作業(yè)刪除已排序作業(yè)(4)對剩余作業(yè)重復(fù)步驟對剩余作業(yè)重復(fù)步驟(2)和和(3)，直到所有作業(yè)排序完畢，直到所有作業(yè)排序完畢Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 49Johnson法法 例子例子步驟步驟 1步驟步驟 2步驟步驟 3步驟步驟 4步驟步

49、驟 5(1)列出每個(gè)作業(yè)在兩臺機(jī)器上的加工時(shí)間列出每個(gè)作業(yè)在兩臺機(jī)器上的加工時(shí)間(2)選擇最短的加工時(shí)間。如果最短的加工時(shí)間來自第一臺機(jī)器，那選擇最短的加工時(shí)間。如果最短的加工時(shí)間來自第一臺機(jī)器，那么先完成這個(gè)作業(yè)；如果來自第二臺機(jī)器，那么這個(gè)作業(yè)就放在最后么先完成這個(gè)作業(yè)；如果來自第二臺機(jī)器，那么這個(gè)作業(yè)就放在最后完成完成(3)刪除已排序作業(yè)刪除已排序作業(yè)(4)對剩余作業(yè)重復(fù)步驟對剩余作業(yè)重復(fù)步驟(2)和和(3)，直到所有作業(yè)排序完畢，直到所有作業(yè)排序完畢作業(yè)作業(yè)工作工作1工作工作2Y11222Y245Y353Y41516Y5108Y3Y1Y2Y4Y5Y3Y3Y3Y3Y2Y2Y2Y5Y5Y1

50、Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 50Johnson法例子的甘特圖法例子的甘特圖工序1工序1工序2工序245450 05 510101515202025253030353540405050555560606565Y2(4)Y1(12)Y4(15)Y5(10)Y3(5)空閑，等待新任務(wù)空閑，等待新任務(wù)Y2(5)Y1(22)Y4(16)Y5(8)Y3(3)空閑空閑空閑空閑Y4Y3Y2Y5Y1Production & Oper

51、ations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 51提問提問n如果第一臺機(jī)器的某作業(yè)的所用時(shí)間同第如果第一臺機(jī)器的某作業(yè)的所用時(shí)間同第二臺機(jī)器的另一作業(yè)的時(shí)間相同，應(yīng)該如二臺機(jī)器的另一作業(yè)的時(shí)間相同，應(yīng)該如何排序？何排序？n如果一項(xiàng)作業(yè)在兩臺機(jī)器上的作業(yè)時(shí)間相如果一項(xiàng)作業(yè)在兩臺機(jī)器上的作業(yè)時(shí)間相同，應(yīng)該如何排序？同，應(yīng)該如何排序？Production & Operations ManagementProduction & Operations Management浙江

52、財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 52Johnson法的補(bǔ)充說明法的補(bǔ)充說明n如果第一臺機(jī)器的某作業(yè)的所用時(shí)間同第二臺機(jī)如果第一臺機(jī)器的某作業(yè)的所用時(shí)間同第二臺機(jī)器的另一作業(yè)的時(shí)間相同，則第一臺機(jī)器的這一器的另一作業(yè)的時(shí)間相同，則第一臺機(jī)器的這一作業(yè)安排在前面完成，而第二臺機(jī)器的這項(xiàng)作業(yè)作業(yè)安排在前面完成，而第二臺機(jī)器的這項(xiàng)作業(yè)安排在后面完成安排在后面完成n如果一項(xiàng)作業(yè)在兩臺機(jī)器上的作業(yè)時(shí)間相同，這如果一項(xiàng)作業(yè)在兩臺機(jī)器上的作業(yè)時(shí)間相同，這個(gè)項(xiàng)目可以被安排在兩個(gè)作業(yè)時(shí)間的任一一個(gè)個(gè)項(xiàng)目可以被安排在兩個(gè)作業(yè)時(shí)間的任一一個(gè)Production & Operations Mana

53、gementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 53Johnson法的優(yōu)化（法的優(yōu)化（P303）n第一臺機(jī)器上的加工時(shí)間記為第一臺機(jī)器上的加工時(shí)間記為ai，第二臺機(jī)器上，第二臺機(jī)器上的加工時(shí)間的加工時(shí)間bin將所有工件將所有工件ai bi按按ai值不減的順序排成一個(gè)值不減的順序排成一個(gè)序列序列An將所有工件將所有工件ai bi按按bi值不增的順序排成一個(gè)值不增的順序排成一個(gè)序列序列Bn將將A放在放在B之前，就構(gòu)成了最優(yōu)加工順序之前，就構(gòu)成了最優(yōu)加工順序Production & Operations

54、 ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 54Johnson法的優(yōu)化法的優(yōu)化n ai bi按按ai值不減的序列值不減的序列A：(4,12,15) ,(Y2,Y1,Y4)作業(yè)作業(yè)工作工作1工作工作2Y11222Y245Y353Y41516Y51084121538Y4Y3Y2Y5Y1nai bi按按bi值不增的序列值不增的序列B：(8,3),(Y5,Y3)Production & Operations ManagementProduction & Operations Mana

55、gement浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 55n個(gè)作業(yè)個(gè)作業(yè)n臺機(jī)器排序問題臺機(jī)器排序問題(n/n)n當(dāng)作業(yè)數(shù)和機(jī)器數(shù)相同時(shí)，能夠同時(shí)開始當(dāng)作業(yè)數(shù)和機(jī)器數(shù)相同時(shí)，能夠同時(shí)開始所有作業(yè)所有作業(yè)n作業(yè)排序問題不是哪個(gè)作業(yè)先開始，而是作業(yè)排序問題不是哪個(gè)作業(yè)先開始，而是哪個(gè)作業(yè)指派到哪臺機(jī)器上的安排使得總哪個(gè)作業(yè)指派到哪臺機(jī)器上的安排使得總排序最佳排序最佳Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 56n/n作業(yè)問題的分配方

56、法作業(yè)問題的分配方法Assignment Method分配方法是一種特殊的可將任務(wù)或工作分分配方法是一種特殊的可將任務(wù)或工作分配給相應(yīng)的資源的線性規(guī)劃模型，是線性規(guī)劃配給相應(yīng)的資源的線性規(guī)劃模型，是線性規(guī)劃運(yùn)輸問題的一個(gè)特例。運(yùn)輸問題的一個(gè)特例。適用于有適用于有n個(gè)需求和個(gè)需求和n個(gè)供給的情況個(gè)供給的情況成本成本或或時(shí)間時(shí)間達(dá)到最少達(dá)到最少目標(biāo)目標(biāo)特征特征一件工作一件工作(或一個(gè)人或一個(gè)人)僅分配給一臺機(jī)器僅分配給一臺機(jī)器(或或一個(gè)項(xiàng)目一個(gè)項(xiàng)目)Production & Operations ManagementProduction & Operations Managemen

57、t浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 57n/n作業(yè)問題的分配方法作業(yè)問題的分配方法每個(gè)分配問題用一張表，表中數(shù)字是與每個(gè)分配問題用一張表，表中數(shù)字是與特定的分配相關(guān)的成本或時(shí)間。特定的分配相關(guān)的成本或時(shí)間。通過在增加或減少一適當(dāng)?shù)臄?shù)字以找到通過在增加或減少一適當(dāng)?shù)臄?shù)字以找到各種分配的最小機(jī)會成本。各種分配的最小機(jī)會成本。Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 58分配方法的步驟分配方法的步驟1.1.將每行數(shù)字減去該行中

58、最小數(shù)字，將每列減去該將每行數(shù)字減去該行中最小數(shù)字，將每列減去該列中最小數(shù)字。列中最小數(shù)字。2.2.畫數(shù)量最小的水平線和垂直線以蓋住表中的所有畫數(shù)量最小的水平線和垂直線以蓋住表中的所有的零。若的零。若直線數(shù)等于表的行或列數(shù)直線數(shù)等于表的行或列數(shù)，那么我們就，那么我們就找到了最優(yōu)分配找到了最優(yōu)分配( (見步驟見步驟4)4)；否則進(jìn)入步驟；否則進(jìn)入步驟3 3。3.3.從未被直線蓋住的所有數(shù)中減去最小的數(shù)，并將從未被直線蓋住的所有數(shù)中減去最小的數(shù)，并將此最小數(shù)加到所有兩兩相交之處的數(shù)上。再回到此最小數(shù)加到所有兩兩相交之處的數(shù)上。再回到步驟步驟2 2往下操作直到出現(xiàn)可能的最佳分配。往下操作直到出現(xiàn)可能

59、的最佳分配。4.4.最佳分配總在表中零位置出現(xiàn)。最佳分配總在表中零位置出現(xiàn)。Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 59分配方法示例分配方法示例 機(jī)器機(jī)器工作工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元將工作分配到機(jī)器上去將工作分配到機(jī)器上去Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)

60、學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 60分配方法示例分配方法示例機(jī)器機(jī)器工作工作ABCR-3411元14元6元S-668元10元11元T-509元12元7元步驟步驟1a1a：從各行數(shù)字中減去其中數(shù)字最小的數(shù)字：從各行數(shù)字中減去其中數(shù)字最小的數(shù)字機(jī)器機(jī)器工作工作ABCR-34S-66T-50658002325087Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 61分配方法示例分配方法示例機(jī)器機(jī)器工作工作ABCR-34580S-66023

61、T-50250步驟步驟1b1b：從各列數(shù)字中減去其中數(shù)字最小的數(shù)字：從各列數(shù)字中減去其中數(shù)字最小的數(shù)字機(jī)器機(jī)器工作工作ABCR-34S-66T-50050226030300Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 62分配方法示例分配方法示例機(jī)器機(jī)器工作工作ABCR-34560S-66003T-50230步驟步驟2 2：畫最小數(shù)目的直線蓋住所有的：畫最小數(shù)目的直線蓋住所有的0 0直線數(shù)直線數(shù)=2=2行行( (列列) )數(shù)數(shù)3 3，故非最優(yōu)答案，故非最優(yōu)答案Production & Operations ManagementProduction & Operations Management浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院浙江財(cái)經(jīng)學(xué)院工商管理學(xué)院 63分配方法示例分配方法示例機(jī)器機(jī)器工作工作ABCR-34560S-66003T-50230步驟步驟3：從未被直線蓋住的所有數(shù)中減去最小的數(shù)，并將：從未被直線蓋住的所有數(shù)中減去最小的數(shù)，并將此最小數(shù)加到所有兩兩相交之處的數(shù)上此最小數(shù)加到所有兩兩