生产计划与管理作业排程

第一页，编辑于星期日：二十点四十九分。第七章　作業排程前言作業排程的基本概念作業排程的特徵與限制單機排程問題平行機台排程問題流線型生產之排程問題零工型生產之排程問題前推與後推排程問題人員排程問題結語第二页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*前言半導體製造工廠汽車組裝生產線汽車租賃保留(reservation)系統醫院中的護士排班問題系統安裝設置(installation)專案第三页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*作業排程的基本概念排程是一種資源分配的決策活動。作業排程(OperationsScheduling)為廣義排程中的一種，若在製造業中特別是指製造現場機台與工件間的安排，以下簡稱排程。在一般工廠內常見的排程問題中，處理步驟主要可分為兩部份。決定各工作站的工作負荷(workloading)決定工作之處理順序(sequencing)第四页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*作業排程的基本概念1/2將各項工作分配至各工作站，它決定各工作站該負責之工作，讓管理者將製令單安排至各工作站，同時兼顧各工作站間目前的產能負荷情況以及生產線平衡問題，但並未排定各工作站內的工作次序。又稱派工(Dispatching)，透過派工法則來決定線上執行順序。排程可定義成一種短期計畫，此計畫關係著製造現場的製令單或擬作業之工作的作業順序和時間配置，此定義說明排程是一序列的排序步驟。負荷安排工作的處理優先順序第五页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*作業排程的基本概念2/2因此，所有工作的作業先後順序、先天的技術限制、各個作業的估計時間和各個作業所需之資源產能等，都是構建細部排程時需要考慮的因素。第六页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*作業排程的特徵與限制製造現場生產結構(ShopStructure)評估準則(PerformanceCriteria)產品結構(ProductStructure)工作中心之產能(WorkCenterCapacities)第七页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*單機(singlemachine)排程問題․n個工作的開始時間均為零․作業時間(tj)包含了準備時間(setuptime)，而且不受排程順序的不同而有所影響․作業時間(tj)事先已知․一旦機器有空馬上處理下一等待的工作․上機的工作未處理完成前，不能中途停止假設․單機排程是最基本的排程問題，其定義為n件獨立工作以何順序分派至一部機台上作業，以使某一績效評估指標最佳定義第八页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*排程之基本評估指標1/2作業流程時間(Flowtime)：工作在系統中停留之時間。延誤時間(Lateness)：工作i完工時間與交期之差異。總完工時間(Makespan)：所有工作處理完成之完工時間。延遲時間(Tardiness)：工作i完工時間超出交期的時間。延遲作業數目(Numberoftardyjobs)：第九页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*排程之基本評估指標2/2平均流程時間(Averageflowtime)：平均延誤時間(Averagelateness)：平均延遲時間(Averagetardiness)：最大延誤時間(Maximumlateness)：最大延遲時間(Maximumtardiness)：第十页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*單機(singlemachine)排程問題n件獨立工作以何順序分派至一部機台上作業，以使某一績效評估指標最佳。最小化平均流程時間。job作業時間越小者排越前面，亦可以使平均延誤(遲)時間，平均等候時間最小化。最短作業時間法則(SPT)最小化平均加權流程時間。將作業時間除以權重，所得之值越小者排越前面。加權最短作業時間法則(WSPT)最大延誤(遲)時間最小化。交期越早者排越前面，但是此法會有增加延遲工件數目和增加平均延遲時間的傾向。最早交期法則(EDD)最小化延遲工件數目。Hodgson法則第十一页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*當n個作業要排至單一機台上時，利用SPT(ShortestProcessTime)法則排序可使得平均流程時間最小化，也就是　　　　　　　　。最短作業時間(SPT)法則—最小化平均流程時間(　)第十二页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7.11/3給予一組工作集如表7.6，目標為最小化平均流程時間。表7.6工作作業時間表工作i作業時間ti142837435106127685第十三页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7.12/3依SPT派工法則排序，順序為4-1-8-7-3-2-5-6。其流程時間計算和表7.7所示。表7.7流程時間計算表工作i流程時間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第十四页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7.13/3所以平均流程時間由上例及圖7.3觀察，工作流程時間的計算方式為除了最小化平均流程時間以外，在單機排程問題中SPT法則亦可以最小化平均延誤時間、最小化平均等候時間。4187325605101520253035404550第十五页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*加權最短作業時間法則(WSPT)—最小化加權平均流程時間當工作附有重要性之屬性時，排程人員可給予個別之權重，權重值愈大表示重要性愈大。WSPT法則即是將作業時間除以權重，所得之值愈小者表示為愈重要之工作，而將它排至順序的第一位，依此類推。加權平均流程時間的計算方式為第十六页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*最短作業時間(SPT)法則—最小化平均延誤時間(　)單機排程問題之目標若為最小化平均延誤時間，SPT法則排序可得最佳解，即第十七页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*最早交期法則(EDDRule)—最小化最大延誤時間(Lmax)1955年Jackson提出EDD(EarlyDueDate)派工法則，其應用在最小化最大延誤時間和最大延遲時間，但是會有增加延遲工作數目和增加平均延遲時間的傾向。EDD法則排序為交期愈早者排至愈前面，即第十八页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*Hodgson法則：求NT最小，即最小化延遲工件數目以EDD法則將所有工作排序為集合，並計算E集合中所有工作的完工時間。假使結果出現沒有或者只有一個延遲工作，則停止，此時已達為最小最佳解。否則進入第二步驟。Step1在集合中從頭至尾找出第一個延遲作業，假設為kStep2檢視前個工作(包含第個)，將最長作業時間之工作移至另一集合中(開始為空集合)，其中。Step3重新計算集合中所有工作的完工時間。若集合中沒有延遲作業，則停止，集合的延遲個數即為最小解。否則回到步驟2。Step4第十九页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*平行機台(parallelmachine)排程問題1/2傳統平行機台排程問題就是將n個工作如何安排至m部平行機台的問題。第二十页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*平行機台(parallelmachine)排程問題2/2一般平行機台主要可分為二種：Unrelatedparallelmachine(無關聯平行機台)：․各機台的加工速度皆不同，且以同一機台來說，不同的工件也會有不同的加工速度。Identicalparallelmachine(等效平行機台)：․所有的機台對於某一個工件的加工速度均相同。第二十一页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*最小化平均流程時間範例7.6Step1:SPT法則:{6,10,3,7,9,1,8,2,5,4}Step2:依序將工作指派至最早閒置之機台工作i12345678910作業時間ti5638723542第二十二页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*降低總完工時間範例7.7Step1:LPT法則:{4,5,2,1,8,9,3,7,6,10}Step2:依序將工作指派至最早閒置之機台Step3:依SPT法則排序機台上工作工作i12345678910作業時間ti5638723542第二十三页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*降低最大延遲時間Step1:EDD法則:{6,10,1,7,2,8,5,4,3,9}Step2:依序將工作指派至最早閒置之機台作業時間交期工作i158269331448125711625738851094151027第二十四页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*降低延遲工件數目在探討單機排程時，我們發現Hodgson 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 可使延遲件數最小，現在依此方法應用到平行機台排程上。利用方法7.5.3指派所有工作。步驟1針對每部機台，找出第一個延遲工作，假設發現在機台j的第i個順位。步驟2檢查並找出在機台j前i個順位中作業時間最長者，將它移至機台j的最後順位，修正更改後工作的完成時間並重複步驟2。步驟3第二十五页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*流線型生產之排程問題1/3如何決定n件工作進入系統的處理順序：m部序列機台(m-1機台排在m機台前)，每件工作都必須依序通過此m部機台，當某工作在一機台之作業完成後，便依序到下一機台等待處理。第二十六页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*流線型生產之排程問題2/3強生法則(Johnson’srule)－兩部序列機台最小化總完工時間。找出所有工作在兩部機台上之作業時間ti,1和ti,2兩者中最小者。Step1假使選出的最小時間在機台1(ti,1)，則將所對應的工作排在順序最早的下一可排空位，繼續步驟3。假使選出的最小時間在機台2(ti,2)，則將所對應的工作排在順序最後的下一可排空位，繼續步驟3。Step2將已指派之工作刪除，回至步驟1，直到所有工作排完為止。Step3第二十七页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*流線型生產之排程問題3/3兩部序列機台最小化總完工時間：Johnson’srule結果:{,,,,}14253第二十八页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*流線型生產之排程問題範例─7.101/3工作i機台1之作業時間機台2之作業時間13526232847656665975483296810104第二十九页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*流線型生產之排程問題範例─7.102/3工作i機台1之作業時間機台2之作業時間13526232847656665975483296810104第三十页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*流線型生產之排程問題範例─7.101/3最後之順序為3-1-6-9-5-4-7-10-8-2第三十一页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*零工型生產之排程問題第三十二页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*零工型生產排程問題零工型生產系統的派工法則:隨機法則,FCFS,EDD,SPT,LSF,LWR,………第三十三页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*零工型生產排程問題一般而言，有限產能排程問題主要可分成下列幾種：利用訂單排序法則決定訂單或製令的加工優先順序，再按順序高低逐一安排各製令的詳細作業排程。以「製令」為主的排程方法(Job-basedScheduling或Order-basedScheduling)運算邏輯是利用事件導向(Event-Driven)的模擬觀念來描述製造系統的實際運作流程。以「工作中心」為主的排程方法(Event-basedScheduling)第三十四页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*派工法則1/2幾種常用的派工法則：以首先來到等候線的工作為優先先進先出派工法則(FirstComeFirstServed,FCFS)以等候線中工作的最早交期者為優先最早交期派工法則(EarliestDueDate,EDD)等候線上的每一等待工作的選擇是具相同機率。一般此法將作為與其他方法之比較基礎。隨機法則(Random)以等候線中工作的作業時間最短者為優先。最短作業時間派工法則(ShortestProcessingTime,SPT)第三十五页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*派工法則2/2以等候線中工作的仍剩餘的加工時間最短者為優先。最小剩餘時間派工法則(LeastWorkRemaining,LWR)寬裕時間是指交期減掉工作還需在機器上加工完成的時間。以等候線中工作的寬裕時間最短者為優先。最小寬裕時間派工法則(LeastSlackFirst,LSF)依照距離到期日剩餘時間對剩餘加工時間比率，最小者為優先。關鍵性比率(CriticalRatio,CR)第三十六页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7-11─以製令為主的排程方法1/3以EDD法則來決定製令的加工優先順序順序製令交期111023123213451456156418製令作業順序與時間交期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第三十七页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7-11─以製令為主的排程方法2/3順序製令交期111023123213451456156418第三十八页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7-11─以製令為主的排程方法3/3第三十九页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7.12(EDD)─以「工作中心」為主的排程方法1/8製令作業順序與時間交期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第四十页，编辑于星期日：二十点四十九分。生產計畫與管理Chapter7作業排程7-*範例7.12(EDD)─以「工作中心」為主的排程方法2/8若以T來表示時間軸。當T=0時，此時機台A，B，C均空閒。當開始著手於A機台的排程時，我們所面對的抉擇是製令1或製令2，何者排在最前？假設依據EDD派工法則來進行模擬過程，如表分別針對機台A，B，C選定該上機之製令。機台可排之製令派工法則判斷選定之製令作業時間A1,2D1