作業(yè)排程前言作業(yè)排程的基本概念作業(yè)排程的特征與限制單機(jī)排程問題平行機(jī)臺(tái)排程問題流線型生產(chǎn)之排程問題零工型生產(chǎn)之排程問題前推與后推排程問題人員排程問題結(jié)語前言半導(dǎo)體制造工廠汽車組裝生產(chǎn)線汽車租賃保留(reservation)系統(tǒng)醫(yī)院中的護(hù)士排班問題系統(tǒng)安裝設(shè)置(installation)專案作業(yè)排程的基本概念排程是一種資源分配的決策活動(dòng)。作業(yè)排程(OperationsScheduling)為廣義排程中的一種，若在制造業(yè)中特別是指制造現(xiàn)場機(jī)臺(tái)與工件間的安排，以下簡稱排程。在一般工廠內(nèi)常見的排程問題中，處理步驟主要可分為兩部份。決定各工作站的工作負(fù)荷(workloading)決定工作之處理順序(sequencing)作業(yè)排程的基本概念1/2將各項(xiàng)工作分配至各工作站，它決定各工作站該負(fù)責(zé)之工作，讓管理者將制令單安排至各工作站，同時(shí)兼顧各工作站間目前的產(chǎn)能負(fù)荷情況以及生產(chǎn)線平衡問題，但并未排定各工作站內(nèi)的工作次序。又稱派工(Dispatching)，透過派工法則來決定在線執(zhí)行順序。排程可定義成一種短期計(jì)劃，此計(jì)劃關(guān)系著制造現(xiàn)場的制令單或擬作業(yè)之工作的作業(yè)順序和時(shí)間配置，此定義說明排程是一序列的排序步驟。負(fù)荷安排工作的處理優(yōu)先級(jí)作業(yè)排程的基本概念2/2因此，所有工作的作業(yè)先后順序、先天的技術(shù)限制、各個(gè)作業(yè)的估計(jì)時(shí)間和各個(gè)作業(yè)所需之資源產(chǎn)能等，都是構(gòu)建細(xì)部排程時(shí)需要考慮的因素。作業(yè)排程的特征與限制制造現(xiàn)場生產(chǎn)結(jié)構(gòu)(ShopStructure)評(píng)估準(zhǔn)則(PerformanceCriteria)產(chǎn)品結(jié)構(gòu)(ProductStructure)工作中心之產(chǎn)能(WorkCenterCapacities)單機(jī)(singlemachine)排程問題?

n個(gè)工作的開始時(shí)間均為零?作業(yè)時(shí)間(tj)包含了準(zhǔn)備時(shí)間(setuptime)，而且不受排程順序的不同而有所影響?作業(yè)時(shí)間(tj)事先已知?一旦機(jī)器有空馬上處理下一等待的工作?上機(jī)的工作未處理完成前，不能中途停止假設(shè)?單機(jī)排程是最基本的排程問題，其定義為n件獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè)，以使某一績效評(píng)估指標(biāo)最佳定義排程之基本評(píng)估指標(biāo)1/2作業(yè)流程時(shí)間(Flowtime)：工作在系統(tǒng)中停留之時(shí)間。延誤時(shí)間(Lateness)：工作i完工時(shí)間與交期之差異?？偼旯r(shí)間(Makespan)：所有工作處理完成之完工時(shí)間。延遲時(shí)間(Tardiness)：工作i完工時(shí)間超出交期的時(shí)間。延遲作業(yè)數(shù)目(Numberoftardyjobs)：排程之基本評(píng)估指標(biāo)2/2平均流程時(shí)間(Averageflowtime)：平均延誤時(shí)間(Averagelateness)：平均延遲時(shí)間(Averagetardiness)：最大延誤時(shí)間(Maximumlateness)：最大延遲時(shí)間(Maximumtardiness)：單機(jī)(singlemachine)排程問題n件獨(dú)立工作以何順序分派至一部機(jī)臺(tái)上作業(yè)，以使某一績效評(píng)估指標(biāo)最佳。最小化平均流程時(shí)間。job作業(yè)時(shí)間越小者排越前面，亦可以使平均延誤(遲)時(shí)間，平均等候時(shí)間最小化。最短作業(yè)時(shí)間法則(SPT)最小化平均加權(quán)流程時(shí)間。將作業(yè)時(shí)間除以權(quán)重，所得之值越小者排越前面。加權(quán)最短作業(yè)時(shí)間法則(WSPT)最大延誤(遲)時(shí)間最小化。交期越早者排越前面，但是此法會(huì)有增加延遲工件數(shù)目和增加平均延遲時(shí)間的傾向。最早交期法則(EDD)

最小化延遲工件數(shù)目。Hodgson法則當(dāng)n個(gè)作業(yè)要排至單一機(jī)臺(tái)上時(shí)，利用SPT(ShortestProcessTime)法則排序可使得平均流程時(shí)間最小化，也就是。最短作業(yè)時(shí)間(SPT)法則—

最小化平均流程時(shí)間(

)范例7.11/3給予一組工作集如表7.6，目標(biāo)為最小化平均流程時(shí)間。表7.6工作作業(yè)時(shí)間表工作i作業(yè)時(shí)間ti142837435106127685范例7.12/3依SPT派工法則排序，順序?yàn)?-1-8-7-3-2-5-6。其流程時(shí)間計(jì)算和表7.7所示。表7.7流程時(shí)間計(jì)算表工作i流程時(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范例7.13/3所以平均流程時(shí)間由上例及圖7.3觀察，工作流程時(shí)間的計(jì)算方式為

除了最小化平均流程時(shí)間以外，在單機(jī)排程問題中SPT法則亦可以最小化平均延誤時(shí)間、最小化平均等候時(shí)間。4187325605101520253035404550加權(quán)最短作業(yè)時(shí)間法則(WSPT)—

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

最小化平均延誤時(shí)間(

)單機(jī)排程問題之目標(biāo)若為最小化平均延誤時(shí)間，SPT法則排序可得最佳解，即最早交期法則(EDDRule)—

最小化最大延誤時(shí)間(Lmax)1955年Jackson提出EDD(EarlyDueDate)派工法則，其應(yīng)用在最小化最大延誤時(shí)間和最大延遲時(shí)間，但是會(huì)有增加延遲工作數(shù)目和增加平均延遲時(shí)間的傾向。EDD法則排序?yàn)榻黄谟缯吲胖劣懊?，即Hodgson法則：求NT最小，

即最小化延遲工件數(shù)目以EDD法則將所有工作排序?yàn)榧希⒂?jì)算E集合中所有工作的完工時(shí)間。假使結(jié)果出現(xiàn)沒有或者只有一個(gè)延遲工作，則停止，此時(shí)已達(dá)為最小最佳解。否則進(jìn)入第二步驟。Step1在集合中從頭至尾找出第一個(gè)延遲作業(yè)，假設(shè)為kStep2檢視前個(gè)工作(包含第個(gè))，將最長作業(yè)時(shí)間之工作移至另一集合中(開始為空集合)，其中。Step3重新計(jì)算集合中所有工作的完工時(shí)間。若集合中沒有延遲作業(yè)，則停止，集合的延遲個(gè)數(shù)即為最小解。否則回到步驟2。Step4平行機(jī)臺(tái)(parallelmachine)

排程問題1/2傳統(tǒng)平行機(jī)臺(tái)排程問題就是將n個(gè)工作如何安排至m部平行機(jī)臺(tái)的問題。平行機(jī)臺(tái)(parallelmachine)

排程問題2/2一般平行機(jī)臺(tái)主要可分為二種：Unrelatedparallelmachine(無關(guān)聯(lián)平行機(jī)臺(tái))：?各機(jī)臺(tái)的加工速度皆不同，且以同一機(jī)臺(tái)來說，

不同的工件也會(huì)有不同的加工速度。Identicalparallelmachine(等效平行機(jī)臺(tái))：?所有的機(jī)臺(tái)對(duì)于某一個(gè)工件的加工速度均相同。最小化平均流程時(shí)間范例7.6Step1:SPT法則:{6,10,3,7,9,1,8,2,5,4}Step2:依序?qū)⒐ぷ髦概芍磷钤玳e置之機(jī)臺(tái)工作i12345678910作業(yè)時(shí)間ti5638723542降低總完工時(shí)間范例7.7Step1:LPT法則:{4,5,2,1,8,9,3,7,6,10}Step2:依序?qū)⒐ぷ髦概芍磷钤玳e置之機(jī)臺(tái)Step3:依SPT法則排序機(jī)臺(tái)上工作工作i12345678910作業(yè)時(shí)間ti5638723542降低最大延遲時(shí)間Step1:EDD法則:{6,10,1,7,2,8,5,4,3,9}Step2:依序?qū)⒐ぷ髦概芍磷钤玳e置之機(jī)臺(tái)作業(yè)時(shí)間交期工作i158269331448125711625738851094151027降低延遲工件數(shù)目在探討單機(jī)排程時(shí)，我們發(fā)現(xiàn)Hodgson方法可使延遲件數(shù)最小，現(xiàn)在依此方法應(yīng)用到平行機(jī)臺(tái)排程上。利用方法7.5.3指派所有工作。步驟1針對(duì)每部機(jī)臺(tái)，找出第一個(gè)延遲工作，假設(shè)發(fā)現(xiàn)在機(jī)臺(tái)j的第i個(gè)順位。步驟2檢查并找出在機(jī)臺(tái)j前i個(gè)順位中作業(yè)時(shí)間最長者，將它移至機(jī)臺(tái)j的最后順位，修正更改后工作的完成時(shí)間并重復(fù)步驟2。步驟3流線型生產(chǎn)之排程問題1/3如何決定n件工作進(jìn)入系統(tǒng)的處理順序：m部序列機(jī)臺(tái)(m-1機(jī)臺(tái)排在m機(jī)臺(tái)前)，每件工作都必須依序通過此m部機(jī)臺(tái)，當(dāng)某工作在一機(jī)臺(tái)之作業(yè)完成后，便依序到下一機(jī)臺(tái)等待處理。流線型生產(chǎn)之排程問題2/3瓊森法則(Johnson’srule)－兩部序列機(jī)臺(tái)最小化總完工時(shí)間。找出所有工作在兩部機(jī)臺(tái)上之作業(yè)時(shí)間ti,1和ti,2兩者中最小者。Step1假使選出的最小時(shí)間在機(jī)臺(tái)1(ti,1)，則將所對(duì)應(yīng)的工作排在順序最早的下一可排空位，繼續(xù)步驟3。假使選出的最小時(shí)間在機(jī)臺(tái)2(ti,2)，則將所對(duì)應(yīng)的工作排在順序最后的下一可排空位，繼續(xù)步驟3。Step2將已指派之工作刪除，回至步驟1，直到所有工作排完為止。Step3流線型生產(chǎn)之排程問題3/3兩部序列機(jī)臺(tái)最小化總完工時(shí)間：Johnson’srule結(jié)果:{,,,,}14253流線型生產(chǎn)之排程問題范例─7.101/3工作i機(jī)臺(tái)1之作業(yè)時(shí)間機(jī)臺(tái)2之作業(yè)時(shí)間13526232847656665975483296810104流線型生產(chǎn)之排程問題范例─7.102/3

工作i機(jī)臺(tái)1之作業(yè)時(shí)間機(jī)臺(tái)2之作業(yè)時(shí)間13526232847656665975483296810104流線型生產(chǎn)之排程問題范例─7.101/3最后之順序?yàn)?-1-6-9-5-4-7-10-8-2零工型生產(chǎn)之排程問題零工型生產(chǎn)排程問題零工型生產(chǎn)系統(tǒng)的派工法則:隨機(jī)法則,FCFS,EDD,SPT,LSF,LWR,………零工型生產(chǎn)排程問題一般而言，有限產(chǎn)能排程問題主要可分成下列幾種：利用訂單排序法則決定訂單或制令的加工優(yōu)先級(jí)，再按順序高低逐一安排各制令的詳細(xì)作業(yè)排程。以「制令」為主的排程方法(Job-basedScheduling或Order-basedScheduling)運(yùn)算邏輯是利用事件導(dǎo)向(Event-Driven)的仿真觀念來描述制造系統(tǒng)的實(shí)際運(yùn)作流程。以「工作中心」為主的排程方法(Event-basedScheduling)派工法則1/2幾種常用的派工法則：以首先來到等候線的工作為優(yōu)先先進(jìn)先出派工法則(FirsteFirstServed,FCFS)以等候線中工作的最早交期者為優(yōu)先最早交期派工法則(EarliestDueDate,EDD)等候在線的每一等待工作的選擇是具相同機(jī)率。一般此法將作為與其他方法之比較基礎(chǔ)。隨機(jī)法則(Random)以等候線中工作的作業(yè)時(shí)間最短者為優(yōu)先。最短作業(yè)時(shí)間派工法則(ShortestProcessingTime,SPT)派工法則2/2以等候線中工作的仍剩余的加工時(shí)間最短者為優(yōu)先。最小剩余時(shí)間派工法則(LeastWorkRemaining,LWR)寬裕時(shí)間是指交期減掉工作還需在機(jī)器上加工完成的時(shí)間。以等候線中工作的寬裕時(shí)間最短者為優(yōu)先。最小寬裕時(shí)間派工法則(LeastSlackFirst,LSF)依照距離到期日剩余時(shí)間對(duì)剩余加工時(shí)間比率，最小者為優(yōu)先。關(guān)鍵性比率(CriticalRatio,CR)范例7-11─以制令為主的排程方法1/3以EDD法則來決定制令的加工優(yōu)先級(jí)順序制令交期111023123213451456156418制令作業(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范例7-11─以制令為主的排程方法2/3順序制令交期111023123213451456156418范例7-11─以制令為主的排程方法3/3范例7.12(EDD)─以「工作中心」

為主的排程方法1/8制令作業(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范例7.12(EDD)─以「工作中心」

為主的排程方法2/8若以T來表示時(shí)間軸。當(dāng)T=0時(shí)，此時(shí)機(jī)臺(tái)A，B，C均空閑。當(dāng)開始著手于A機(jī)臺(tái)的排程時(shí)，我們所面對(duì)的抉擇是制令1或制令2，何者排在最前？假設(shè)依據(jù)EDD派工法則來進(jìn)行模擬過程，如表分別針對(duì)機(jī)臺(tái)A，B，C選定該上機(jī)之制令。機(jī)臺(tái)可排之制令派工法則判斷選定之制令作業(yè)時(shí)間A1,2D1<D213B3,4D3<D434C5,6D5<D655注：Di

表示制令i的交期，其中i=1,2,…,6.范例7.12─派工法則：EDD3/8制令作業(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范例7.12─派工法則：SPT4/8制令作業(yè)順序與時(shí)間交期1A(3)