生产作业排程的问题与概念分析(ppt 50页).ppt

第七章作業排程,前言作業排程的基本概念作業排程的特徵與限制單機排程問題平行機台排程問題流線型生產之排程問題零工型生產之排程問題前推與後推排程問題人員排程問題結語,生產計畫與管理Chapter7作業排程,7-3,前言,半導體製造工廠,汽車組裝生產線,汽車租賃保留(reservation)系統,醫院中的護士排班問題,系統安裝設置(installation)專案,生產計畫與管理Chapter7作業排程,7-4,作業排程的基本概念,排程是一種資源分配的決策活動。作業排程(OperationsScheduling)為廣義排程中的一種，若在製造業中特別是指製造現場機台與工件間的安排，以下簡稱排程。在一般工廠內常見的排程問題中，處理步驟主要可分為兩部份。,決定各工作站的工作負荷(workloading),決定工作之處理順序(sequencing),生產計畫與管理Chapter7作業排程,7-5,作業排程的基本概念1/2,將各項工作分配至各工作站，它決定各工作站該負責之工作，讓管理者將製令單安排至各工作站，同時兼顧各工作站間目前的產能負荷情況以及生產線平衡問題，但並未排定各工作站內的工作次序。,又稱派工(Dispatching)，透過派工法則來決定線上執行順序。排程可定義成一種短期計畫，此計畫關係著製造現場的製令單或擬作業之工作的作業順序和時間配置，此定義說明排程是一序列的排序步驟。,負荷安排,工作的處理優先順序,生產計畫與管理Chapter7作業排程,7-6,作業排程的基本概念2/2,因此，所有工作的作業先後順序、先天的技術限制、各個作業的估計時間和各個作業所需之資源產能等，都是構建細部排程時需要考慮的因素。,生產計畫與管理Chapter7作業排程,7-7,作業排程的特徵與限制,製造現場生產結構(ShopStructure),評估準則(PerformanceCriteria),產品結構(ProductStructure),工作中心之產能(WorkCenterCapacities),生產計畫與管理Chapter7作業排程,7-8,單機(singlemachine)排程問題,生產計畫與管理Chapter7作業排程,7-9,排程之基本評估指標1/2,作業流程時間(Flowtime)：工作在系統中停留之時間。,延誤時間(Lateness)：工作i完工時間與交期之差異。,總完工時間(Makespan)：所有工作處理完成之完工時間。,延遲時間(Tardiness)：工作i完工時間超出交期的時間。,延遲作業數目(Numberoftardyjobs)：,生產計畫與管理Chapter7作業排程,7-10,排程之基本評估指標2/2,平均流程時間(Averageflowtime)：,平均延誤時間(Averagelateness)：,平均延遲時間(Averagetardiness)：,最大延誤時間(Maximumlateness)：,最大延遲時間(Maximumtardiness)：,生產計畫與管理Chapter7作業排程,7-11,單機(singlemachine)排程問題,n件獨立工作以何順序分派至一部機台上作業，以使某一績效評估指標最佳。,生產計畫與管理Chapter7作業排程,7-12,當n個作業要排至單一機台上時，利用SPT(ShortestProcessTime)法則排序可使得平均流程時間最小化，也就是。,最短作業時間(SPT)法則最小化平均流程時間(),生產計畫與管理Chapter7作業排程,7-13,範例7.11/3,給予一組工作集如表7.6，目標為最小化平均流程時間。,表7.6工作作業時間表,生產計畫與管理Chapter7作業排程,7-14,範例7.12/3,依SPT派工法則排序，順序為4-1-8-7-3-2-5-6。其流程時間計算和表7.7所示。,表7.7流程時間計算表,生產計畫與管理Chapter7作業排程,7-15,範例7.13/3,所以平均流程時間由上例及圖7.3觀察，工作流程時間的計算方式為除了最小化平均流程時間以外，在單機排程問題中SPT法則亦可以最小化平均延誤時間、最小化平均等候時間。,生產計畫與管理Chapter7作業排程,7-16,加權最短作業時間法則(WSPT)最小化加權平均流程時間,當工作附有重要性之屬性時，排程人員可給予個別之權重，權重值愈大表示重要性愈大。WSPT法則即是將作業時間除以權重，所得之值愈小者表示為愈重要之工作，而將它排至順序的第一位，依此類推。加權平均流程時間的計算方式為,生產計畫與管理Chapter7作業排程,7-17,最短作業時間(SPT)法則最小化平均延誤時間(),單機排程問題之目標若為最小化平均延誤時間，SPT法則排序可得最佳解，即,生產計畫與管理Chapter7作業排程,7-18,最早交期法則(EDDRule)最小化最大延誤時間(Lmax),1955年Jackson提出EDD(EarlyDueDate)派工法則，其應用在最小化最大延誤時間和最大延遲時間，但是會有增加延遲工作數目和增加平均延遲時間的傾向。EDD法則排序為交期愈早者排至愈前面，即,生產計畫與管理Chapter7作業排程,7-19,Hodgson法則：求NT最小，即最小化延遲工件數目,生產計畫與管理Chapter7作業排程,7-20,平行機台(parallelmachine)排程問題1/2,傳統平行機台排程問題就是將n個工作如何安排至m部平行機台的問題。,生產計畫與管理Chapter7作業排程,7-21,平行機台(parallelmachine)排程問題2/2,一般平行機台主要可分為二種：,Unrelatedparallelmachine(無關聯平行機台)：各機台的加工速度皆不同，且以同一機台來說，不同的工件也會有不同的加工速度。,Identicalparallelmachine(等效平行機台)：所有的機台對於某一個工件的加工速度均相同。,生產計畫與管理Chapter7作業排程,7-22,最小化平均流程時間,範例7.6Step1:SPT法則:6,10,3,7,9,1,8,2,5,4Step2:依序將工作指派至最早閒置之機台,生產計畫與管理Chapter7作業排程,7-23,降低總完工時間,範例7.7Step1:LPT法則:4,5,2,1,8,9,3,7,6,10Step2:依序將工作指派至最早閒置之機台Step3:依SPT法則排序機台上工作,生產計畫與管理Chapter7作業排程,7-24,降低最大延遲時間,Step1:EDD法則:6,10,1,7,2,8,5,4,3,9Step2:依序將工作指派至最早閒置之機台,作業時間,交期,生產計畫與管理Chapter7作業排程,7-25,降低延遲工件數目,在探討單機排程時，我們發現Hodgson方法可使延遲件數最小，現在依此方法應用到平行機台排程上。,生產計畫與管理Chapter7作業排程,7-26,流線型生產之排程問題1/3,如何決定n件工作進入系統的處理順序：m部序列機台(m-1機台排在m機台前)，每件工作都必須依序通過此m部機台，當某工作在一機台之作業完成後，便依序到下一機台等待處理。,生產計畫與管理Chapter7作業排程,7-27,流線型生產之排程問題2/3,強生法則(Johnsonsrule)兩部序列機台最小化總完工時間。,生產計畫與管理Chapter7作業排程,7-28,流線型生產之排程問題3/3,兩部序列機台最小化總完工時間：Johnsonsrule結果:,1,4,2,5,3,生產計畫與管理Chapter7作業排程,7-29,流線型生產之排程問題範例7.101/3,生產計畫與管理Chapter7作業排程,7-30,流線型生產之排程問題範例7.102/3,生產計畫與管理Chapter7作業排程,7-31,流線型生產之排程問題範例7.101/3,最後之順序為3-1-6-9-5-4-7-10-8-2,生產計畫與管理Chapter7作業排程,7-32,零工型生產之排程問題,生產計畫與管理Chapter7作業排程,7-33,零工型生產排程問題,零工型生產系統的派工法則:隨機法則,FCFS,EDD,SPT,LSF,LWR,生產計畫與管理Chapter7作業排程,7-34,零工型生產排程問題,一般而言，有限產能排程問題主要可分成下列幾種：,生產計畫與管理Chapter7作業排程,7-35,派工法則1/2,幾種常用的派工法則：,生產計畫與管理Chapter7作業排程,7-36,派工法則2/2,生產計畫與管理Chapter7作業排程,7-37,範例7-11以製令為主的排程方法1/3,以EDD法則來決定製令的加工優先順序,生產計畫與管理Chapter7作業排程,7-38,範例7-11以製令為主的排程方法2/3,生產計畫與管理Chapter7作業排程,7-39,範例7-11以製令為主的排程方法3/3,生產計畫與管理Chapter7作業排程,7-40,範例7.12(EDD)以工作中心為主的排程方法1/8,生產計畫與管理Chapter7作業排程,7-41,範例7.12(EDD)以工作中心為主的排程方法2/8,若以T來表示時間軸。當T=0時，此時機台A，B，C均空閒。當開始著手於A機台的排程時，我們所面對的抉擇是製令1或製令2，何者排在最前？假設依據EDD派工法則來進行模擬過程，如表分別針對機台A，B，C選定該上機之製令。,註：Di表示製令i的交期，其中i=1,2,6.,生產計畫與管理Chapter7作業排程,7-42,範例7.12派工法則：EDD3/8,生產計畫與管理Chapter7作業排程,7-43,範例7.12派工法則：SPT4/8,生產計畫與管理Chapter7作業排程,7-44,範例7.12派工法則：FCFS5/8,生產計畫與管理Chapter7作業排程,7-45,範例7.12派工法則：LSF6/8,生產計畫與管理Chapter7作業排程,7-46,範例7.12派工法則：LWR7/8,生產計畫與管理Chapter7作業排程,7