资源描述
第七章作業排程第七章作業排程前言前言作業排程的基本概念作業排程的基本概念作業排程的特徵與限制作業排程的特徵與限制單機排程問題單機排程問題平行機台排程問題平行機台排程問題流線型生產之排程問題流線型生產之排程問題零工型生產之排程問題零工型生產之排程問題前推與後推排程問題前推與後推排程問題人員排程問題人員排程問題結語結語 前言前言半導體製造工廠半導體製造工廠 汽車組裝生產線汽車組裝生產線汽車租賃保留汽車租賃保留(reservation)系統系統醫院中的護士排班問題醫院中的護士排班問題 系統安裝設置系統安裝設置(installation)專案專案生產計畫與管理 Chapter 7 作業排程3作業排程的基本作業排程的基本概念念排排程程是是一一種種資資源源分分配配的的決決策策活活動動。作作業業排排程程(Operations Scheduling)為為廣廣義義排排程程中中的的一一種種，若若在在製製造造業業中中特特別別是是指指製製造造現現場場機機台台與與工工件件間間的安排，以下簡稱排程。的安排，以下簡稱排程。在在一一般般工工廠廠內內常常見見的的排排程程問問題題中中，處處理理步步驟驟主主要可分為兩部份。要可分為兩部份。決定各工作站的工作負荷決定各工作站的工作負荷(work loading)決定工作之處理順序決定工作之處理順序(sequencing)生產計畫與管理 Chapter 7 作業排程4作業排程的基本作業排程的基本概念念 1/2將各項工作分配至各工作站，它決定各工作站該負責將各項工作分配至各工作站，它決定各工作站該負責之工作，讓管理者將製令單安排至各工作站，同時兼之工作，讓管理者將製令單安排至各工作站，同時兼顧各工作站間目前的產能負荷情況以及生產線平衡問顧各工作站間目前的產能負荷情況以及生產線平衡問題，但並未排定各工作站內的工作次序。題，但並未排定各工作站內的工作次序。又稱派工又稱派工(Dispatching)，透過派工法則來決定線上執，透過派工法則來決定線上執行順序。排程可定義成一種短期計畫，此計畫關係著行順序。排程可定義成一種短期計畫，此計畫關係著製造現場的製令單或擬作業之工作的作業順序和時間製造現場的製令單或擬作業之工作的作業順序和時間配置，此定義說明排程是一序列的排序步驟。配置，此定義說明排程是一序列的排序步驟。負荷安排負荷安排工作的處理優先順序工作的處理優先順序生產計畫與管理 Chapter 7 作業排程5作業排程的基本作業排程的基本概念念 2/2因因此此，所所有有工工作作的的作作業業先先後後順順序序、先先天天的的技技術術限限制制、各各個個作作業業的的估估計計時時間間和和各各個個作作業業所所需需之之資資源源產產能能等等，都都是是構構建建細細部部排排程程時時需需要要考考慮慮的的因素。因素。生產計畫與管理 Chapter 7 作業排程6作業排程的特徵與限制作業排程的特徵與限制 製造現場生產結構製造現場生產結構(Shop Structure)評估準則評估準則(Performance Criteria)產品結構產品結構(Product Structure)工作中心之產能工作中心之產能(Work Center Capacities)生產計畫與管理 Chapter 7 作業排程7單機單機(single machine)排程問題排程問題 n個工作的開始時間均為零個工作的開始時間均為零作業時間作業時間(tj)包含了準備時間包含了準備時間(setup time)，而，而 且不受排程順序的不同而有所影響且不受排程順序的不同而有所影響作業時間作業時間(tj)事先已知事先已知一旦機器有空馬上處理下一等待的工作一旦機器有空馬上處理下一等待的工作上機的工作未處理完成前，不能中途停止上機的工作未處理完成前，不能中途停止假假設設單機排程是最基本的排程問題，其定義為單機排程是最基本的排程問題，其定義為n件件 獨立工作以何順序分派至一部機台上作業，獨立工作以何順序分派至一部機台上作業，以使某一績效評估指標最佳以使某一績效評估指標最佳定定義義生產計畫與管理 Chapter 7 作業排程8排程之基本評估指標排程之基本評估指標 1/2作業流程時間作業流程時間(Flowtime)：工作在系統中停留之時間。：工作在系統中停留之時間。延誤時間延誤時間(Lateness)：工作：工作i完工時間與交期之差異。完工時間與交期之差異。總完工時間總完工時間(Makespan)：所有工作處理完成之完工時間。：所有工作處理完成之完工時間。延遲時間延遲時間(Tardiness)：工作：工作i完工時間超出交期的時間。完工時間超出交期的時間。延遲作業數目延遲作業數目(Number of tardy jobs)：生產計畫與管理 Chapter 7 作業排程9排程之基本評估指標排程之基本評估指標 2/2平均流程時間平均流程時間(Average flowtime)：平均延誤時間平均延誤時間(Average lateness)：平均延遲時間平均延遲時間(Average tardiness)：最大延誤時間最大延誤時間(Maximum lateness)：最大延遲時間最大延遲時間(Maximum tardiness)：生產計畫與管理 Chapter 7 作業排程10單機單機(single machine)排程問題排程問題n 件件獨獨立立工工作作以以何何順順序序分分派派至至一一部部機機台台上上作作業業，以以使使某一績效評估指標最佳。某一績效評估指標最佳。最小化平均流程時間。最小化平均流程時間。job作業時間越小者排越前面，亦可作業時間越小者排越前面，亦可以使平均延誤以使平均延誤(遲遲)時間，平均等候時間最小化。時間，平均等候時間最小化。最短作業時間法則最短作業時間法則(SPT)最小化平均加權流程時間。將作業時間除以權重，所得之最小化平均加權流程時間。將作業時間除以權重，所得之值越小者排越前面。值越小者排越前面。加權最短作業時間法則加權最短作業時間法則(WSPT)最大延誤最大延誤(遲遲)時間最小化。交期越早者排越前面，但是此時間最小化。交期越早者排越前面，但是此法會有增加延遲工件數目和增加平均延遲時間的傾向。法會有增加延遲工件數目和增加平均延遲時間的傾向。最早交期法則最早交期法則(EDD)最小化延遲工件數目。最小化延遲工件數目。Hodgson法則法則 生產計畫與管理 Chapter 7 作業排程11當當n個個作作業業要要排排至至單單一一機機台台上上時時，利利用用SPT(Shortest Process Time)法法則則排排序序可可使使得得平平均均流流程時間最小化，也就是。程時間最小化，也就是。最短作業時間最短作業時間(SPT)法則法則最小化平均流程時間最小化平均流程時間()生產計畫與管理 Chapter 7 作業排程12範例範例 7.1 1/3給予一組工作集如表給予一組工作集如表 7.6，目標為最小化平均流程時間。，目標為最小化平均流程時間。表表 7.6 工作作業時間表工作作業時間表工作工作 i作業時間作業時間 ti142837435106127685生產計畫與管理 Chapter 7 作業排程13範例範例 7.1 2/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生產計畫與管理 Chapter 7 作業排程14範例範例 7.1 3/3所以平均流程時間所以平均流程時間由上例及圖由上例及圖7.3觀察，工作流程時間的計算方式為觀察，工作流程時間的計算方式為 除除了了最最小小化化平平均均流流程程時時間間以以外外，在在單單機機排排程程問問題題中中SPT法法則亦可以最小化平均延誤時間、最小化平均等候時間。則亦可以最小化平均延誤時間、最小化平均等候時間。4187325605101520253035404550生產計畫與管理 Chapter 7 作業排程15加權最短作業時間法則加權最短作業時間法則(WSPT)最小化加權平均流程時間最小化加權平均流程時間 當當工工作作附附有有重重要要性性之之屬屬性性時時，排排程程人人員員可可給給予予個個別別之之權重，權重值愈大表示重要性愈大。權重，權重值愈大表示重要性愈大。WSPT法法則則即即是是將將作作業業時時間間除除以以權權重重，所所得得之之值值愈愈小小者者表表示示為為愈愈重重要要之之工工作作，而而將將它它排排至至順順序序的的第第一一位位，依依此類推。加權平均流程時間的計算方式為此類推。加權平均流程時間的計算方式為生產計畫與管理 Chapter 7 作業排程16最短作業時間最短作業時間(SPT)法則法則最小化平均延誤時間最小化平均延誤時間()單單機機排排程程問問題題之之目目標標若若為為最最小小化化平平均均延延誤誤時時間間，SPT法則排序可得最佳解，即法則排序可得最佳解，即 生產計畫與管理 Chapter 7 作業排程17最早交期法則最早交期法則(EDD Rule)最小化最大延誤時間最小化最大延誤時間(Lmax)1955年年Jackson提提出出EDD(Early Due Date)派派工工法法則則，其其應應用用在在最最小小化化最最大大延延誤誤時時間間和和最最大大延延遲遲時時間間，但但是是會會有有增增加加延延遲遲工工作作數數目目和和增增加加平平均均延延遲遲時間的傾向。時間的傾向。EDD法則排序為交期愈早者排至愈前面，即法則排序為交期愈早者排至愈前面，即生產計畫與管理 Chapter 7 作業排程18Hodgson法則：求法則：求NT最小，最小，即最小化延遲工件數目即最小化延遲工件數目以以EDD法法則則將將所所有有工工作作排排序序為為集集合合，並並計計算算E集集合合中中所所有有工工作作的的完完工工時時間間。假假使使結結果果出出現現沒沒有有或或者者只只有有一一個個延延遲遲工工作作，則則停停止止，此此時時已已達達 為為最最小小最最佳佳解解。否否則進入第二步驟。則進入第二步驟。Step1在集合中從頭至尾找出第一個延遲作業，假設為在集合中從頭至尾找出第一個延遲作業，假設為kStep2檢檢視視前前個個工工作作(包包含含第第個個)，將將最最長長作作業業時時間間之之工工作作 移至另一集合中移至另一集合中(開始為空集合開始為空集合)，其中。，其中。Step3重重新新計計算算集集合合中中所所有有工工作作的的完完工工時時間間。若若集集合合中中沒沒有有延延遲遲作作業業，則則停停止止，集集合合的的延延遲遲個個數數即即為為最最小小解解。否則回到步驟否則回到步驟2。Step4生產計畫與管理 Chapter 7 作業排程19平行機台平行機台(parallel machine)排程問題排程問題 1/2傳傳統統平平行行機機台台排排程程問問題題就就是是將將n個個工工作作如如何何安安排至排至m部平行機台的問題。部平行機台的問題。生產計畫與管理 Chapter 7 作業排程20平行機台平行機台(parallel machine)排程問題排程問題 2/2一般平行機台主要可分為二種：一般平行機台主要可分為二種：Unrelated parallel machine(無關聯平行機台無關聯平行機台)：各各機機台台的的加加工工速速度度皆皆不不同同，且且以以同同一一機機台台來來說說，不同的工件也會有不同的加工速度。不同的工件也會有不同的加工速度。Identical parallel machine(等效平行機台等效平行機台)：所有的機台對於某一個工件的加工速度均相同。所有的機台對於某一個工件的加工速度均相同。生產計畫與管理 Chapter 7 作業排程21最小化平均流程時間最小化平均流程時間範例範例 7.6Step1:SPT法則法則:6,10,3,7,9,1,8,2,5,4Step2:依序將工作指派至最早閒置之機台依序將工作指派至最早閒置之機台工作工作 i12345678910作業時間作業時間ti5638723542生產計畫與管理 Chapter 7 作業排程22降低總完工時間降低總完工時間範例範例 7.7Step1:LPT法則法則:4,5,2,1,8,9,3,7,6,10Step2:依序將工作指派至最早閒置之機台依序將工作指派至最早閒置之機台Step3:依依SPT法則排序機台上工作法則排序機台上工作工作工作 i12345678910作業時間作業時間ti5638723542生產計畫與管理 Chapter 7 作業排程23降低最大延遲時間降低最大延遲時間Step1:EDD法則法則:6,10,1,7,2,8,5,4,3,9Step2:依序將工作指派至最早閒置之機台依序將工作指派至最早閒置之機台作業時間交期工作工作i158269331448125711625738851094151027生產計畫與管理 Chapter 7 作業排程24降低延遲工件數目降低延遲工件數目在在探探討討單單機機排排程程時時，我我們們發發現現Hodgson方方法法可可使使延延遲遲件件數數最最小小，現現在在依依此此方方法法應應用用到到平平行行機機台排程上。台排程上。利用方法利用方法7.5.3指派所有工作。指派所有工作。步驟步驟1針對每部機台，找出第一個延遲工作，假設針對每部機台，找出第一個延遲工作，假設發現在機台發現在機台j的第的第i個順位。個順位。步驟步驟2檢查並找出在機台檢查並找出在機台j前前i個順位中作業時間最個順位中作業時間最長者，將它移至機台長者，將它移至機台j的最後順位，修正更的最後順位，修正更改後工作的完成時間並重複步驟改後工作的完成時間並重複步驟2。步驟步驟3生產計畫與管理 Chapter 7 作業排程25流線型生流線型生產之排程問題之排程問題 1/3如何決定如何決定n件工作進入系統的處理順序：件工作進入系統的處理順序：m部部序序列列機機台台(m-1機機台台排排在在m機機台台前前)，每每件件工工作作都都必必須須依依序序通通過過此此m部部機機台台，當當某某工工作作在在一一機機台台之之作作業業完完成成後後，便便依依序序到到下下一一機機台台等待處理。等待處理。生產計畫與管理 Chapter 7 作業排程26流線型生流線型生產之排程問題之排程問題 2/3強強生生法法則則(Johnsons rule)兩兩部部序序列列機機台台最最小小化總完工時間。化總完工時間。找找出出所所有有工工作作在在兩兩部部機機台台上上之之作作業業時時間間ti,1和和ti,2兩兩者中最小者。者中最小者。Step1假假使使選選出出的的最最小小時時間間在在機機台台1(ti,1)，則則將將所所對對應應的的工工作作排排在在順順序序最最早早的的下下一一可可排排空空位位，繼繼續續步步驟驟3。假假使使選選出出的的最最小小時時間間在在機機台台2(ti,2)，則則將將所所對對應應的的工作排在順序最後的下一可排空位，繼續步驟工作排在順序最後的下一可排空位，繼續步驟3。Step2將將已已指指派派之之工工作作刪刪除除，回回至至步步驟驟1，直直到到所所有有工工作作排完為止。排完為止。Step3生產計畫與管理 Chapter 7 作業排程27流線型生流線型生產之排程問題之排程問題 3/3兩兩部部序序列列機機台台最最小小化化總總完完工工時時間間：Johnsons rule結果結果:,14253生產計畫與管理 Chapter 7 作業排程28流線型生流線型生產之排程問題範例之排程問題範例7.10 1/3工作工作i 機台機台1之作業時間之作業時間 機台機台2之作業時間之作業時間 13526232847656665975483296810104生產計畫與管理 Chapter 7 作業排程29流線型生流線型生產之排程問題範例之排程問題範例7.10 2/3 工作工作i 機台機台1之作業時間之作業時間 機台機台2之作業時間之作業時間 13526232847656665975483296810104生產計畫與管理 Chapter 7 作業排程30流線型生流線型生產之排程問題範例之排程問題範例7.10 1/3最後之順序為最後之順序為3-1-6-9-5-4-7-10-8-2生產計畫與管理 Chapter 7 作業排程31零工型生零工型生產之排程問題之排程問題生產計畫與管理 Chapter 7 作業排程32零工型生零工型生產排程問題排程問題零工型生產系統的派工法則零工型生產系統的派工法則:隨機法則隨機法則,FCFS,EDD,SPT,LSF,LWR,生產計畫與管理 Chapter 7 作業排程33零工型生零工型生產排程問題排程問題一一般般而而言言，有有限限產產能能排排程程問問題題主主要要可可分分成成下下列列幾種：幾種：利利用用訂訂單單排排序序法法則則決決定定訂訂單單或或製製令令的的加加工工優優先先順順序序，再按順序高低逐一安排各製令的詳細作業排程。再按順序高低逐一安排各製令的詳細作業排程。以製令為主的排程方法以製令為主的排程方法(Job-based Scheduling或或Order-based Scheduling)運算邏輯是利用事件導向運算邏輯是利用事件導向(Event-Driven)的模擬觀念的模擬觀念來描述製造系統的實際運作流程。來描述製造系統的實際運作流程。以工作中心為主的排程方法以工作中心為主的排程方法(Event-based Scheduling)生產計畫與管理 Chapter 7 作業排程34派工法則派工法則 1/2幾種常用的派工法則：幾種常用的派工法則：以首先來到等候線的工作為優先以首先來到等候線的工作為優先先進先出派工法則先進先出派工法則(First Come First Served,FCFS)以等候線中工作的最早交期者為優先以等候線中工作的最早交期者為優先最早交期派工法則最早交期派工法則(Earliest Due Date,EDD)等候線上的每一等待工作的選擇是具相同機率。等候線上的每一等待工作的選擇是具相同機率。一般此法將作為與其他方法之比較基礎。一般此法將作為與其他方法之比較基礎。隨機法則隨機法則(Random)以等候線中工作的作業時間最短以等候線中工作的作業時間最短者為優先。者為優先。最短作業時間派工法則最短作業時間派工法則(Shortest Processing Time,SPT)生產計畫與管理 Chapter 7 作業排程35派工法則派工法則 2/2以等候線中工作的仍剩餘的加以等候線中工作的仍剩餘的加工時間最短者為優先。工時間最短者為優先。最小剩餘時間派工法則最小剩餘時間派工法則(Least Work Remaining,LWR)寬裕時間是指交期減掉工作還需在機器上加工完成的時寬裕時間是指交期減掉工作還需在機器上加工完成的時間。以等候線中工作的寬裕時間最短者為優先。間。以等候線中工作的寬裕時間最短者為優先。最小寬裕時間派工法則最小寬裕時間派工法則(Least Slack First,LSF)依照距離到期日剩餘時間對剩餘加工時依照距離到期日剩餘時間對剩餘加工時間比率，最小者為優先。間比率，最小者為優先。關鍵性比率關鍵性比率(Critical Ratio,CR)生產計畫與管理 Chapter 7 作業排程36範例範例 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生產計畫與管理 Chapter 7 作業排程37範例範例 7-11以以製令製令為主的排程方法主的排程方法 2/3順序順序製令製令交期交期111023123213451456156418生產計畫與管理 Chapter 7 作業排程38範例範例 7-11以以製令製令為主的排程方法主的排程方法 3/3生產計畫與管理 Chapter 7 作業排程39範例範例 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生產計畫與管理 Chapter 7 作業排程40範例範例 7.12(EDD)以工作中心以工作中心為主的排程方法主的排程方法 2/8若若以以T來來表表示示時時間間軸軸。當當T=0時時，此此時時機機台台A，B，C均均空空閒閒。當當開開始始著著手手於於A機機台台的的排排程程時時，我我們們所所面面對對的的抉抉擇擇是是製製令令1或或製製令令2，何何者者排排在在最最前前？假假設設依依據據EDD派派工工法法則則來來進進行行模模擬擬過過程程，如如表表分分別針對機台別針對機台A，B，C選定該上機之製令。選定該上機之製令。機台機台可排之製令可排之製令派工法則判斷派工法則判斷選定之製令選定之製令作業時間作業時間A1,2D1D213B3,4D3D434C5,6D5D655註：註：Di 表示製令表示製令i 的交期，其中的交期，其中 i=1,2,6.生產計畫與管理 Chapter 7 作業排程41範例範例 7.12 派工法則：派工法則：EDD 3/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生產計畫與管理 Chapter 7 作業排程42範例範例 7.12 派工法則：派工法則：SPT 4/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生產計畫與管理 Chapter 7 作業排程43範例範例 7.12 派工法則：派工法則：FCFS 5/8 生產計畫與管理 Chapter 7 作業排程44範例範例 7.12 派工法則：派工法則：LSF 6/8 生產計畫與管理 Chapter 7 作業排程45範例範例 7.12 派工法則：派工法則：LWR 7/8 生產計畫與管理 Chapter 7 作業排程46範例範例 7.12 不同派工法則的績效表現不同派工法則的績效表現 8/8 派工法則派工法則評估準則評估準則延遲件數延遲件數(number of tardy jobs)總延遲時間總延遲時間(total tardiness)平均流程時平均流程時間間(mean flow time)總完工時間總完工時間(makespan)EDD3141522FCFS52217.3322LSF41816.520SPT31315.3320LWR32415.529生產計畫與管理 Chapter 7 作業排程47前推前推(Forward)與後推與後推(Backward)排程排程由由上上一一小小節節範範例例中中可可發發現現，排排程程的的方方式式均均是是由由目目前前時時間間點點Tnow進進行行排排程程活活動動，即即由由目目前前時時間間點點朝朝未未來來時時間向前看，這樣的排程方式稱之為前推排程。間向前看，這樣的排程方式稱之為前推排程。前推排程前推排程(Forward Scheduling)主主要要是是由由未未來來某某特特定定時時間間點點，例例如如某某筆筆訂訂單單的的交交期期，在時間軸上倒推排程。在時間軸上倒推排程。後推排程後推排程(Backward Scheduling)生產計畫與管理 Chapter 7 作業排程48結論結論排程問題存在於各行各業及日常生活中。排程問題存在於各行各業及日常生活中。製製造造系系統統種種類類極極多多，且且在在新新的的製製造造技技術術和和製製造造管管理觀念持續發展下，隨時產生新的排程問題理觀念持續發展下，隨時產生新的排程問題。真真實實製製造造系系統統的的排排程程問問題題其其複複雜雜度度和和困困難難度度均均相相當高。當高。生產計畫與管理 Chapter 7 作業排程49Q&A生產計畫與管理 Chapter 7 作業排程50
展开阅读全文