《生產(chǎn)計(jì)劃與管理--作業(yè)排程(PPT 50頁(yè))(3)》由會(huì)員分享，可在線閱讀，更多相關(guān)《生產(chǎn)計(jì)劃與管理--作業(yè)排程(PPT 50頁(yè))(3)（50頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、前言前言作業(yè)排程的基本概念作業(yè)排程的基本概念作業(yè)排程的特徵與限制作業(yè)排程的特徵與限制單機(jī)排程問題單機(jī)排程問題平行機(jī)臺(tái)排程問題平行機(jī)臺(tái)排程問題流線型生產(chǎn)之排程問題流線型生產(chǎn)之排程問題零工型生產(chǎn)之排程問題零工型生產(chǎn)之排程問題前推與後推排程問題前推與後推排程問題人員排程問題人員排程問題結(jié)語(yǔ)結(jié)語(yǔ) 前言前言半導(dǎo)體製造工廠半導(dǎo)體製造工廠 汽車組裝生產(chǎn)線汽車組裝生產(chǎn)線汽車租賃保留汽車租賃保留(reservation)系統(tǒng)系統(tǒng)醫(yī)院中的護(hù)士排班問題醫(yī)院中的護(hù)士排班問題 系統(tǒng)安裝設(shè)置系統(tǒng)安裝設(shè)置(installation)專案專案生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程3作業(yè)排程的基本概念作業(yè)排程的基本概念排

2、程是一種資源分配的決策活動(dòng)。作業(yè)排程排程是一種資源分配的決策活動(dòng)。作業(yè)排程(Operations Scheduling)為廣義排程中的一種，為廣義排程中的一種，若在製造業(yè)中特別是指製造現(xiàn)場(chǎng)機(jī)臺(tái)與工件間若在製造業(yè)中特別是指製造現(xiàn)場(chǎng)機(jī)臺(tái)與工件間的安排，以下簡(jiǎn)稱排程。的安排，以下簡(jiǎn)稱排程。在一般工廠內(nèi)常見的排程問題中，處理步驟主在一般工廠內(nèi)常見的排程問題中，處理步驟主要可分為兩部份。要可分為兩部份。決定各工作站的工作負(fù)荷決定各工作站的工作負(fù)荷(work loading)決定工作之處理順序決定工作之處理順序(sequencing)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程4作業(yè)排程的基本概念作業(yè)排程

3、的基本概念 1/2將各項(xiàng)工作分配至各工作站，它決定各工作站該負(fù)責(zé)將各項(xiàng)工作分配至各工作站，它決定各工作站該負(fù)責(zé)之工作，讓管理者將製令單安排至各工作站，同時(shí)兼之工作，讓管理者將製令單安排至各工作站，同時(shí)兼顧各工作站間目前的產(chǎn)能負(fù)荷情況以及生產(chǎn)線平衡問顧各工作站間目前的產(chǎn)能負(fù)荷情況以及生產(chǎn)線平衡問題，但並未排定各工作站內(nèi)的工作次序。題，但並未排定各工作站內(nèi)的工作次序。又稱派工又稱派工(Dispatching)，透過派工法則來決定線上執(zhí)，透過派工法則來決定線上執(zhí)行順序。排程可定義成一種短期計(jì)畫，此計(jì)畫關(guān)係行順序。排程可定義成一種短期計(jì)畫，此計(jì)畫關(guān)係著製造現(xiàn)場(chǎng)的製令單或擬作業(yè)之工作的作業(yè)順序和著製造現(xiàn)

4、場(chǎng)的製令單或擬作業(yè)之工作的作業(yè)順序和時(shí)間配置，此定義說明排程是一序列的排序步驟。時(shí)間配置，此定義說明排程是一序列的排序步驟。負(fù)荷安排負(fù)荷安排工作的處理優(yōu)先順序工作的處理優(yōu)先順序生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程5作業(yè)排程的基本概念作業(yè)排程的基本概念 2/2因此，所有工作的作業(yè)先後順序、先天的技術(shù)因此，所有工作的作業(yè)先後順序、先天的技術(shù)限制、各個(gè)作業(yè)的估計(jì)時(shí)間和各個(gè)作業(yè)所需之限制、各個(gè)作業(yè)的估計(jì)時(shí)間和各個(gè)作業(yè)所需之資源產(chǎn)能等，都是構(gòu)建細(xì)部排程時(shí)需要考慮的資源產(chǎn)能等，都是構(gòu)建細(xì)部排程時(shí)需要考慮的因素。因素。生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程6作業(yè)排程的特徵與限制作業(yè)排程的特徵與

5、限制 製造現(xiàn)場(chǎng)生產(chǎn)結(jié)構(gòu)製造現(xiàn)場(chǎng)生產(chǎn)結(jié)構(gòu)(Shop Structure)評(píng)估準(zhǔn)則評(píng)估準(zhǔn)則(Performance Criteria)產(chǎn)品結(jié)構(gòu)產(chǎn)品結(jié)構(gòu)(Product Structure)工作中心之產(chǎn)能工作中心之產(chǎn)能(Work Center Capacities)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程7單機(jī)單機(jī)(single machine)排程問題排程問題 n個(gè)工作的開始時(shí)間均為零個(gè)工作的開始時(shí)間均為零 作業(yè)時(shí)間作業(yè)時(shí)間(tj)包含了準(zhǔn)備時(shí)間包含了準(zhǔn)備時(shí)間(setup time)，而，而 且不受排程順序的不同而有所影響且不受排程順序的不同而有所影響 作業(yè)時(shí)間作業(yè)時(shí)間(tj)事先已知事先已知

6、 一旦機(jī)器有空馬上處理下一等待的工作一旦機(jī)器有空馬上處理下一等待的工作 上機(jī)的工作未處理完成前，不能中途停止上機(jī)的工作未處理完成前，不能中途停止假假設(shè)設(shè) 單機(jī)排程是最基本的排程問題，其定義為單機(jī)排程是最基本的排程問題，其定義為n件件 獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè)，獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè)，以使某一績(jī)效評(píng)估指標(biāo)最佳以使某一績(jī)效評(píng)估指標(biāo)最佳定定義義生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程8排程之基本評(píng)估指標(biāo)排程之基本評(píng)估指標(biāo) 1/2作業(yè)流程時(shí)間作業(yè)流程時(shí)間(Flowtime)：工作在系統(tǒng)中停留之時(shí)間。：工作在系統(tǒng)中停留之時(shí)間。sisisirCF,延誤時(shí)間延誤時(shí)間(Laten

7、ess)：工作：工作i完工時(shí)間與交期之差異。完工時(shí)間與交期之差異。sisisidCL,總完工時(shí)間總完工時(shí)間(Makespan)：所有工作處理完成之完工時(shí)間。：所有工作處理完成之完工時(shí)間。1nsiiMt 延遲時(shí)間延遲時(shí)間(Tardiness)：工作：工作i完工時(shí)間超出交期的時(shí)間。完工時(shí)間超出交期的時(shí)間。,max 0,i si si sTCd 延遲作業(yè)數(shù)目延遲作業(yè)數(shù)目(Number of tardy jobs)：1niiNT 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程9排程之基本評(píng)估指標(biāo)排程之基本評(píng)估指標(biāo) 2/2 n1is,isFn1F n1is,isLn1L n1is,isTn1TL,0max

8、Tmaxmax LmaxLs,ini1max 平均流程時(shí)間平均流程時(shí)間(Average flowtime)：平均延誤時(shí)間平均延誤時(shí)間(Average lateness)：平均延遲時(shí)間平均延遲時(shí)間(Average tardiness)：最大延誤時(shí)間最大延誤時(shí)間(Maximum lateness)：最大延遲時(shí)間最大延遲時(shí)間(Maximum tardiness)：生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程10單機(jī)單機(jī)(single machine)排程問題排程問題n 件獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè)，以使件獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè)，以使某一績(jī)效評(píng)估指標(biāo)最佳。某一績(jī)效評(píng)估指標(biāo)最佳。

9、最小化平均流程時(shí)間。最小化平均流程時(shí)間。job作業(yè)時(shí)間越小者排越前面，亦可作業(yè)時(shí)間越小者排越前面，亦可以使平均延誤以使平均延誤(遲遲)時(shí)間，平均等候時(shí)間最小化。時(shí)間，平均等候時(shí)間最小化。最短作業(yè)時(shí)間法則最短作業(yè)時(shí)間法則(SPT)最小化平均加權(quán)流程時(shí)間。將作業(yè)時(shí)間除以權(quán)重，所得之最小化平均加權(quán)流程時(shí)間。將作業(yè)時(shí)間除以權(quán)重，所得之值越小者排越前面。值越小者排越前面。加權(quán)最短作業(yè)時(shí)間法則加權(quán)最短作業(yè)時(shí)間法則(WSPT)最大延誤最大延誤(遲遲)時(shí)間最小化。交期越早者排越前面，但是此時(shí)間最小化。交期越早者排越前面，但是此法會(huì)有增加延遲工件數(shù)目和增加平均延遲時(shí)間的傾向。法會(huì)有增加延遲工件數(shù)目和增加平均延遲

10、時(shí)間的傾向。最早交期法則最早交期法則(EDD)最小化延遲工件數(shù)目。最小化延遲工件數(shù)目。Hodgson法則法則 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程11當(dāng)當(dāng)n個(gè)作業(yè)要排至單一機(jī)臺(tái)上時(shí)，利用個(gè)作業(yè)要排至單一機(jī)臺(tái)上時(shí)，利用SPT(Shortest Process Time)法則排序可使得平均法則排序可使得平均流程時(shí)間最小化，也就是。流程時(shí)間最小化，也就是。最短作業(yè)時(shí)間最短作業(yè)時(shí)間(SPT)法則法則最小化平均流程時(shí)間最小化平均流程時(shí)間()sF 12nttt生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程12範(fàn)例範(fàn)例 7.1 1/3給予一組工作集如表給予一組工作集如表 7.6，目標(biāo)為最小化平均流程時(shí)

11、間。，目標(biāo)為最小化平均流程時(shí)間。表表 7.6 工作作業(yè)時(shí)間表工作作業(yè)時(shí)間表工作工作 i作業(yè)時(shí)間作業(yè)時(shí)間 ti142837435106127685生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程13範(fàn)例範(fàn)例 7.1 2/3依依SPT派工法則排序，順序?yàn)榕晒し▌t排序，順序?yàn)?-1-8-7-3-2-5-6。其流。其流程時(shí)間計(jì)算和表程時(shí)間計(jì)算和表7.7所示。所示。表表 7.7 流程時(shí)間計(jì)算表流程時(shí)間計(jì)算表工作工作 i流程時(shí)間流程時(shí)間 ti4313+483+4+573+4+5+633+4+5+6+723+4+5+6+7+853+4+5+6+7+8+1063+4+5+6+7+8+10+12生產(chǎn)計(jì)畫與管理 Ch

12、apter 7 作業(yè)排程14範(fàn)例範(fàn)例 7.1 3/3所以平均流程時(shí)間所以平均流程時(shí)間由上例及圖由上例及圖7.3觀察，工作流程時(shí)間的計(jì)算方式為觀察，工作流程時(shí)間的計(jì)算方式為除了最小化平均流程時(shí)間以外，在單機(jī)排程問題中除了最小化平均流程時(shí)間以外，在單機(jī)排程問題中SPT法法則亦可以最小化平均延誤時(shí)間、最小化平均等候時(shí)間。則亦可以最小化平均延誤時(shí)間、最小化平均等候時(shí)間。1(8 3)(7 4)(6 5)(5 6)(4 7)(3 8)(2 10)(1 12)24.58sF 1211(1)2snnFntntttn 4187325605101520253035404550生產(chǎn)計(jì)畫與管理 Chapter 7 作

13、業(yè)排程15加權(quán)最短作業(yè)時(shí)間法則加權(quán)最短作業(yè)時(shí)間法則(WSPT)最小化加權(quán)平均流程時(shí)間最小化加權(quán)平均流程時(shí)間 當(dāng)工作附有重要性之屬性時(shí)，排程人員可給予個(gè)別之當(dāng)工作附有重要性之屬性時(shí)，排程人員可給予個(gè)別之權(quán)重，權(quán)重值愈大表示重要性愈大。權(quán)重，權(quán)重值愈大表示重要性愈大。WSPT法則即是將作業(yè)時(shí)間除以權(quán)重，所得之值愈小法則即是將作業(yè)時(shí)間除以權(quán)重，所得之值愈小者表示為愈重要之工作，而將它排至順序的第一位，者表示為愈重要之工作，而將它排至順序的第一位，依此類推。加權(quán)平均流程時(shí)間的計(jì)算方式為依此類推。加權(quán)平均流程時(shí)間的計(jì)算方式為,1,1nii siw sniiw FFw 1212WSPTnntttwww法則

14、：法則：生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程16最短作業(yè)時(shí)間最短作業(yè)時(shí)間(SPT)法則法則最小化平均延誤時(shí)間最小化平均延誤時(shí)間()單機(jī)排程問題之目標(biāo)若為最小化平均延誤時(shí)間，單機(jī)排程問題之目標(biāo)若為最小化平均延誤時(shí)間，SPT法則排序可得最佳解，即法則排序可得最佳解，即 sL 12nttt生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程17最早交期法則最早交期法則(EDD Rule)最小化最大延誤時(shí)間最小化最大延誤時(shí)間(Lmax)1955年年Jackson提出提出EDD(Early Due Date)派工法派工法則，其應(yīng)用在最小化最大延誤時(shí)間和最大延遲時(shí)則，其應(yīng)用在最小化最大延誤時(shí)間和最大延遲時(shí)

15、間，但是會(huì)有增加延遲工作數(shù)目和增加平均延遲間，但是會(huì)有增加延遲工作數(shù)目和增加平均延遲時(shí)間的傾向。時(shí)間的傾向。EDD法則排序?yàn)榻黄谟缯吲胖劣懊妫捶▌t排序?yàn)榻黄谟缯吲胖劣懊?，?12nddd生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程18Hodgson法則：求法則：求NT最小，最小，即最小化延遲工件數(shù)目即最小化延遲工件數(shù)目以以EDD法則將所有工作排序?yàn)榧?，並計(jì)算法則將所有工作排序?yàn)榧?，並計(jì)算E集合中集合中所有工作的完工時(shí)間。假使結(jié)果出現(xiàn)沒有或者只有一所有工作的完工時(shí)間。假使結(jié)果出現(xiàn)沒有或者只有一個(gè)延遲工作，則停止，此時(shí)已達(dá)個(gè)延遲工作，則停止，此時(shí)已達(dá) 為最小最佳解。否為最小最佳解。否

16、則進(jìn)入第二步驟。則進(jìn)入第二步驟。Step1在集合中從頭至尾找出第一個(gè)延遲作業(yè)，假設(shè)為在集合中從頭至尾找出第一個(gè)延遲作業(yè)，假設(shè)為kStep2檢視前個(gè)工作檢視前個(gè)工作(包含第個(gè)包含第個(gè))，將最長(zhǎng)作業(yè)時(shí)間之工作，將最長(zhǎng)作業(yè)時(shí)間之工作 移至另一集合中移至另一集合中(開始為空集合開始為空集合)，其中。，其中。Step3重新計(jì)算集合中所有工作的完工時(shí)間。若集合中沒重新計(jì)算集合中所有工作的完工時(shí)間。若集合中沒有延遲作業(yè)，則停止，集合的延遲個(gè)數(shù)即為最小解。有延遲作業(yè)，則停止，集合的延遲個(gè)數(shù)即為最小解。否則回到步驟否則回到步驟2。Step4生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程19平行機(jī)臺(tái)平行機(jī)臺(tái)(par

17、allel machine)排程問題排程問題 1/2傳統(tǒng)平行機(jī)臺(tái)排程問題就是將傳統(tǒng)平行機(jī)臺(tái)排程問題就是將n個(gè)工作如何安個(gè)工作如何安排至排至m部平行機(jī)臺(tái)的問題。部平行機(jī)臺(tái)的問題。Machine 1Machine 2Machine 3Machine iMachine mn 件工作m 部平行機(jī)臺(tái).生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程20平行機(jī)臺(tái)平行機(jī)臺(tái)(parallel machine)排程問題排程問題 2/2一般平行機(jī)臺(tái)主要可分為二種：一般平行機(jī)臺(tái)主要可分為二種：Unrelated parallel machine(無關(guān)聯(lián)平行機(jī)臺(tái)無關(guān)聯(lián)平行機(jī)臺(tái))：各機(jī)臺(tái)的加工速度皆不同，且以同一機(jī)臺(tái)來說，

18、各機(jī)臺(tái)的加工速度皆不同，且以同一機(jī)臺(tái)來說，不同的工件也會(huì)有不同的加工速度。不同的工件也會(huì)有不同的加工速度。Identical parallel machine(等效平行機(jī)臺(tái)等效平行機(jī)臺(tái))：所有的機(jī)臺(tái)對(duì)於某一個(gè)工件的加工速度均相同。所有的機(jī)臺(tái)對(duì)於某一個(gè)工件的加工速度均相同。生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程21最小化平均流程時(shí)間最小化平均流程時(shí)間範(fàn)例範(fàn)例 7.6Step1:SPT法則法則:6,10,3,7,9,1,8,2,5,4Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái)依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái)21816141210864機(jī)臺(tái)1機(jī)臺(tái)2機(jī)臺(tái)364871092513工作工作 i1234

19、5678910作業(yè)時(shí)間作業(yè)時(shí)間ti5638723542生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程22降低總完工時(shí)間降低總完工時(shí)間範(fàn)例範(fàn)例 7.7Step1:LPT法則法則:4,5,2,1,8,9,3,7,6,10Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái)依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái)Step3:依依SPT法則排序機(jī)臺(tái)上工作法則排序機(jī)臺(tái)上工作21816141210864機(jī)臺(tái)1機(jī)臺(tái)2機(jī)臺(tái)36487925131021816141210864機(jī)臺(tái) 1機(jī)臺(tái) 2機(jī)臺(tái) 364879251310工作工作 i12345678910作業(yè)時(shí)間作業(yè)時(shí)間ti5638723542生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)

20、排程23降低最大延遲時(shí)間降低最大延遲時(shí)間Step1:EDD法則法則:6,10,1,7,2,8,5,4,3,9Step2:依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái)依序?qū)⒐ぷ髦概芍磷钤玳f置之機(jī)臺(tái)作業(yè)時(shí)間交期工作工作i15826933144812571162573885109415102721816141210864機(jī)臺(tái)1機(jī)臺(tái)2機(jī)臺(tái)364879251310生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程24降低延遲工件數(shù)目降低延遲工件數(shù)目在探討單機(jī)排程時(shí)，我們發(fā)現(xiàn)在探討單機(jī)排程時(shí)，我們發(fā)現(xiàn)Hodgson方法可方法可使延遲件數(shù)最小，現(xiàn)在依此方法應(yīng)用到平行機(jī)使延遲件數(shù)最小，現(xiàn)在依此方法應(yīng)用到平行機(jī)臺(tái)排程上。臺(tái)排程上。

21、利用方法利用方法7.5.3指派所有工作。指派所有工作。步驟步驟1針對(duì)每部機(jī)臺(tái)，找出第一個(gè)延遲工作，假設(shè)針對(duì)每部機(jī)臺(tái)，找出第一個(gè)延遲工作，假設(shè)發(fā)現(xiàn)在機(jī)臺(tái)發(fā)現(xiàn)在機(jī)臺(tái)j的第的第i個(gè)順位。個(gè)順位。步驟步驟2檢查並找出在機(jī)臺(tái)檢查並找出在機(jī)臺(tái)j前前i個(gè)順位中作業(yè)時(shí)間最個(gè)順位中作業(yè)時(shí)間最長(zhǎng)者，將它移至機(jī)臺(tái)長(zhǎng)者，將它移至機(jī)臺(tái)j的最後順位，修正更的最後順位，修正更改後工作的完成時(shí)間並重複步驟改後工作的完成時(shí)間並重複步驟2。步驟步驟3生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程25流線型生產(chǎn)之排程問題流線型生產(chǎn)之排程問題 1/3如何決定如何決定n件工作進(jìn)入系統(tǒng)的處理順序：件工作進(jìn)入系統(tǒng)的處理順序：m部序列機(jī)臺(tái)部序

22、列機(jī)臺(tái)(m-1機(jī)臺(tái)排在機(jī)臺(tái)排在m機(jī)臺(tái)前機(jī)臺(tái)前)，每件，每件工作都必須依序通過此工作都必須依序通過此m部機(jī)臺(tái)，當(dāng)某工作部機(jī)臺(tái)，當(dāng)某工作在一機(jī)臺(tái)之作業(yè)完成後，便依序到下一機(jī)臺(tái)在一機(jī)臺(tái)之作業(yè)完成後，便依序到下一機(jī)臺(tái)等待處理。等待處理。Machine 1Machine 2Machine mn 件工作m部序列機(jī)臺(tái)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程26流線型生產(chǎn)之排程問題流線型生產(chǎn)之排程問題 2/3強(qiáng)生法則強(qiáng)生法則(Johnsons rule)兩部序列機(jī)臺(tái)最兩部序列機(jī)臺(tái)最小化總完工時(shí)間。小化總完工時(shí)間。找出所有工作在兩部機(jī)臺(tái)上之作業(yè)時(shí)間找出所有工作在兩部機(jī)臺(tái)上之作業(yè)時(shí)間ti,1和和ti,2兩兩者

23、中最小者。者中最小者。Step1假使選出的最小時(shí)間在機(jī)臺(tái)假使選出的最小時(shí)間在機(jī)臺(tái)1(ti,1)，則將所對(duì)應(yīng)的，則將所對(duì)應(yīng)的工作排在順序最早的下一可排空位，繼續(xù)步驟工作排在順序最早的下一可排空位，繼續(xù)步驟3。假使選出的最小時(shí)間在機(jī)臺(tái)假使選出的最小時(shí)間在機(jī)臺(tái)2(ti,2)，則將所對(duì)應(yīng)的，則將所對(duì)應(yīng)的工作排在順序最後的下一可排空位，繼續(xù)步驟工作排在順序最後的下一可排空位，繼續(xù)步驟3。Step2將已指派之工作刪除，回至步驟將已指派之工作刪除，回至步驟1，直到所有工作，直到所有工作排完為止。排完為止。Step3生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程27流線型生產(chǎn)之排程問題流線型生產(chǎn)之排程問題 3/

24、3兩部序列機(jī)臺(tái)最小化總完工時(shí)間：兩部序列機(jī)臺(tái)最小化總完工時(shí)間：Johnsons rule結(jié)果結(jié)果:,14253生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程28流線型生產(chǎn)之排程問題範(fàn)例流線型生產(chǎn)之排程問題範(fàn)例7.10 1/3工作工作i i 機(jī)臺(tái)機(jī)臺(tái)1 1之作業(yè)時(shí)間之作業(yè)時(shí)間 機(jī)臺(tái)機(jī)臺(tái)2 2之作業(yè)時(shí)間之作業(yè)時(shí)間 13526232847656665975483296810104生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程29流線型生產(chǎn)之排程問題範(fàn)例流線型生產(chǎn)之排程問題範(fàn)例7.10 2/3 工作工作i i 機(jī)臺(tái)機(jī)臺(tái)1 1之作業(yè)時(shí)間之作業(yè)時(shí)間 機(jī)臺(tái)機(jī)臺(tái)2 2之作業(yè)時(shí)間之作業(yè)時(shí)間 135262328476

25、56665975483296810104生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程30流線型生產(chǎn)之排程問題範(fàn)例流線型生產(chǎn)之排程問題範(fàn)例7.10 1/3最後之順序?yàn)樽钺嶂樞驗(yàn)?-1-6-9-5-4-7-10-8-2機(jī)臺(tái)1機(jī)臺(tái)224363432302826242220181614121086444240384650485654522547108316931695471082時(shí)間生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程31零工型生產(chǎn)之排程問題零工型生產(chǎn)之排程問題生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程32零工型生產(chǎn)排程問題零工型生產(chǎn)排程問題零工型生產(chǎn)系統(tǒng)的派工法則零工型生產(chǎn)系統(tǒng)的派工法則

26、:隨機(jī)法則隨機(jī)法則,FCFS,EDD,SPT,LSF,LWR,FEDCBA完成品(Finished components)原物料(Raw materials)=等候線(Queue)=排序法則(Sequencing rule)=工作中心(Work center)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程33零工型生產(chǎn)排程問題零工型生產(chǎn)排程問題一般而言，有限產(chǎn)能排程問題主要可分成下列一般而言，有限產(chǎn)能排程問題主要可分成下列幾種：幾種：利用訂單排序法則決定訂單或製令的加工優(yōu)先順序，利用訂單排序法則決定訂單或製令的加工優(yōu)先順序，再按順序高低逐一安排各製令的詳細(xì)作業(yè)排程。再按順序高低逐一安排各製令的詳

27、細(xì)作業(yè)排程。以製令為主的排程方法以製令為主的排程方法(Job-based Scheduling或或Order-based Scheduling)運(yùn)算邏輯是利用事件導(dǎo)向運(yùn)算邏輯是利用事件導(dǎo)向(Event-Driven)的模擬觀念的模擬觀念來描述製造系統(tǒng)的實(shí)際運(yùn)作流程。來描述製造系統(tǒng)的實(shí)際運(yùn)作流程。以工作中心為主的排程方法以工作中心為主的排程方法(Event-based Scheduling)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程34派工法則派工法則 1/2幾種常用的派工法則：幾種常用的派工法則：以首先來到等候線的工作為優(yōu)先以首先來到等候線的工作為優(yōu)先先進(jìn)先出派工法則先進(jìn)先出派工法則(Fir

28、st Come First Served,FCFS)以等候線中工作的最早交期者為優(yōu)先以等候線中工作的最早交期者為優(yōu)先最早交期派工法則最早交期派工法則(Earliest Due Date,EDD)等候線上的每一等待工作的選擇是具相同機(jī)率。等候線上的每一等待工作的選擇是具相同機(jī)率。一般此法將作為與其他方法之比較基礎(chǔ)。一般此法將作為與其他方法之比較基礎(chǔ)。隨機(jī)法則隨機(jī)法則(Random)以等候線中工作的作業(yè)時(shí)間最短以等候線中工作的作業(yè)時(shí)間最短者為優(yōu)先。者為優(yōu)先。最短作業(yè)時(shí)間派工法則最短作業(yè)時(shí)間派工法則(Shortest Processing Time,SPT)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排

29、程35派工法則派工法則 2/2以等候線中工作的仍剩餘的加以等候線中工作的仍剩餘的加工時(shí)間最短者為優(yōu)先。工時(shí)間最短者為優(yōu)先。最小剩餘時(shí)間派工法則最小剩餘時(shí)間派工法則(Least Work Remaining,LWR)寬裕時(shí)間是指交期減掉工作還需在機(jī)器上加工完成的時(shí)寬裕時(shí)間是指交期減掉工作還需在機(jī)器上加工完成的時(shí)間。以等候線中工作的寬裕時(shí)間最短者為優(yōu)先。間。以等候線中工作的寬裕時(shí)間最短者為優(yōu)先。最小寬裕時(shí)間派工法則最小寬裕時(shí)間派工法則(Least Slack First,LSF)依照距離到期日剩餘時(shí)間對(duì)剩餘加工時(shí)依照距離到期日剩餘時(shí)間對(duì)剩餘加工時(shí)間比率，最小者為優(yōu)先。間比率，最小者為優(yōu)先。關(guān)鍵性比

30、率關(guān)鍵性比率(Critical Ratio,CR)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程36範(fàn)例範(fàn)例 7-11以以製令製令為主的排程方法為主的排程方法 1/3 以以EDD法則來決定製令的加工優(yōu)先順序法則來決定製令的加工優(yōu)先順序 順序順序製令製令交期交期111023123213451456156418製令製令作業(yè)順序與時(shí)間作業(yè)順序與時(shí)間交期交期1A(3)B(3)C(2)102A(5)C(2)133B(4)A(4)C(2)124B(3)C(5)A(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程37範(fàn)例範(fàn)例 7-11以以製令製令為主的排

31、程方法為主的排程方法 2/3順序順序製令製令交期交期111023123213451456156418生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程38範(fàn)例範(fàn)例 7-11以以製令製令為主的排程方法為主的排程方法 3/3生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程39範(fàn)例範(fàn)例 7.12(EDD)以工作中心以工作中心為主的排程方法為主的排程方法 1/8製令製令作業(yè)順序與時(shí)間作業(yè)順序與時(shí)間交期交期1A(3)B(3)C(2)102A(5)C(2)133B(4)A(4)C(3)124B(3)C(5)A(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程4

32、0範(fàn)例範(fàn)例 7.12(EDD)以工作中心以工作中心為主的排程方法為主的排程方法 2/8若以若以T來表示時(shí)間軸。當(dāng)來表示時(shí)間軸。當(dāng)T=0時(shí)，此時(shí)機(jī)臺(tái)時(shí)，此時(shí)機(jī)臺(tái)A，B，C均空閒。當(dāng)開始著手於均空閒。當(dāng)開始著手於A機(jī)臺(tái)的排程時(shí)，我們所機(jī)臺(tái)的排程時(shí)，我們所面對(duì)的抉擇是製令面對(duì)的抉擇是製令1或製令或製令2，何者排在最前？假，何者排在最前？假設(shè)依據(jù)設(shè)依據(jù)EDD派工法則來進(jìn)行模擬過程，如表分別派工法則來進(jìn)行模擬過程，如表分別針對(duì)機(jī)臺(tái)針對(duì)機(jī)臺(tái)A，B，C選定該上機(jī)之製令。選定該上機(jī)之製令。機(jī)臺(tái)機(jī)臺(tái)可排之製令可排之製令派工法則判斷派工法則判斷選定之製令選定之製令作業(yè)時(shí)間作業(yè)時(shí)間A1,2D1D213B3,4D3D

33、434C5,6D5D655註：註：Di 表示製令表示製令i 的交期，其中的交期，其中 i=1,2,6.生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程41範(fàn)例範(fàn)例 7.12 派工法則：派工法則：EDD 3/8製令製令作業(yè)順序與時(shí)間作業(yè)順序與時(shí)間交期交期1A(3)B(3)C(2)102A(5)C(2)133B(4)A(4)C(3)124B(3)C(5)A(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程42範(fàn)例範(fàn)例 7.12 派工法則：派工法則：SPT 4/8製令製令作業(yè)順序與時(shí)間作業(yè)順序與時(shí)間交期交期1A(3)B(3)C(2)102A(5)C

34、(2)133B(4)A(4)C(3)124B(3)C(5)A(2)185C(5)B(4)146C(2)A(5)B(5)15生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程43範(fàn)例範(fàn)例 7.12 派工法則：派工法則：FCFS 5/8 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程44範(fàn)例範(fàn)例 7.12 派工法則：派工法則：LSF 6/8 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程45範(fàn)例範(fàn)例 7.12 派工法則：派工法則：LWR 7/8 生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程46範(fàn)例範(fàn)例 7.12 不同派工法則的績(jī)效表現(xiàn)不同派工法則的績(jī)效表現(xiàn) 8/8 派工法則派工法則評(píng)估準(zhǔn)則評(píng)估準(zhǔn)則延遲件數(shù)延

35、遲件數(shù)(number of tardy jobs)總延遲時(shí)間總延遲時(shí)間(total tardiness)平均流程時(shí)平均流程時(shí)間間(mean flow time)總完工時(shí)間總完工時(shí)間(makespan)EDD3141522FCFS52217.3322LSF41816.520SPT31315.3320LWR32415.529生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程47前推前推(Forward)與後推與後推(Backward)排程排程由上一小節(jié)範(fàn)例中可發(fā)現(xiàn)，排程的方式均是由目前時(shí)由上一小節(jié)範(fàn)例中可發(fā)現(xiàn)，排程的方式均是由目前時(shí)間點(diǎn)間點(diǎn)Tnow進(jìn)行排程活動(dòng)，即由目前時(shí)間點(diǎn)朝未來時(shí)進(jìn)行排程活動(dòng)，即由目

36、前時(shí)間點(diǎn)朝未來時(shí)間向前看，這樣的排程方式稱之為前推排程。間向前看，這樣的排程方式稱之為前推排程。前推排程前推排程(Forward Scheduling)主要是由未來某特定時(shí)間點(diǎn)，例如某筆訂單的交期，主要是由未來某特定時(shí)間點(diǎn)，例如某筆訂單的交期，在時(shí)間軸上倒推排程。在時(shí)間軸上倒推排程。後推排程後推排程(Backward Scheduling)生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程48結(jié)論結(jié)論排程問題存在於各行各業(yè)及日常生活中。排程問題存在於各行各業(yè)及日常生活中。製造系統(tǒng)種類極多，且在新的製造技術(shù)和製造製造系統(tǒng)種類極多，且在新的製造技術(shù)和製造管理觀念持續(xù)發(fā)展下，隨時(shí)產(chǎn)生新的排程問題管理觀念持續(xù)發(fā)展下，隨時(shí)產(chǎn)生新的排程問題。真實(shí)製造系統(tǒng)的排程問題其複雜度和困難度均真實(shí)製造系統(tǒng)的排程問題其複雜度和困難度均相當(dāng)高。相當(dāng)高。生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程49Q&A生產(chǎn)計(jì)畫與管理 Chapter 7 作業(yè)排程50