現今許多產品生產型態,是採用彈性零工型生產方式,亦即每個工件皆有一至多個製程,並且每個製程可在一至多個機台或廠區完成。同時,從製造業的實際觀點,一個好的生產排程規劃,應該要有多方面的考量,例如降低交貨延遲時間、生產效率提升、減少生產設備磨耗與怠工時間、降低半成品之存貨成本等等,因此本研究就多目標彈性零工型生產排程問題加以探討。 本研究延續Kacem et al. (2002a)所提之彈性零工型生產排程問題,但除了原先的三個最小化目標:總完工時間 (makespan; Cmax)、所有機台總工作量(total machine workload, TMW) 以及關鍵機台的工作量(critical machine workload; CMW)之外,增加第四個目標總延遲時間(total tardiness, TT)。演算法架構使用分層方式求解法 (hierarchical approach):在此分層策略下,上層決定作業-機台指派問題 (operation-machine assignment, OMA),專注於極小化與機台負擔有關兩個目標:TMW與CMW;之後在每個OMA下,下層尋求兩個排程目標最小化:Cmax與TT,此下層過程中TMW與CMW值不變。 本研究使用GRASP (greedy randomized adaptive search procedure) 演算法,使用不同的派工法則計算greedy function,決定OMA與作業排程,再使用區域搜尋法改善作業排程求得區域非被支配解。此演算法稱之為Double-GRASP (D-GRASP)。 本研究將D-GRASP演算結果在兩種三目標問題與先前文獻結果相互比較,本研究採用Kacem et al. (2002a) 之三目標 (Cmax, TMW, CMW) 的5題測試題,另一種三目標(TT, TMW, CMW)測試題則以黃文洲(2010)產生的25題為標竿測試題。在(Cmax, TMW, CMW)問題方面,D-GRASP演算法於大部分的測試題優於FL+EA (Kacem et al. 2002b)、PSO+SA(Xia. and Wu. 2005)、PSO+TS(Zhang et al. 2009);在(TT, TMW, CMW) 問題方面,D-GRASP之表現亦優於黃文洲 (2010)之演化式演算法與蘇海興(2011)之門檻值搜尋法。 在四個目標問題(Cmax, TT, TMW, CMW)上,所提D-GRASP將與ACO+SA、ACO+GRASP、GRASP+SA做比較,並且證實D-GRASP之表先優於其他三種演算法。
Flexible job shop scheduling problems (FJSSPs) arise in many production systems. When scheduling jobs, management generally does not focus solely on one objective. This study focuses on solving the multi-objective flexible job shop scheduling problem (MO-FJSSP) with four minimization objectives: makespan (F1), total tardiness (F2), total machine workload (F3), and critical workload (F4). The study presents a double greedy randomized adaptive search procedure (D-GRASP) to solve the MO-FJSSP. The D-GRASP is a hierarchical approach using two encoding schemes: job-machine assignment (JMA) and job-order list (JOL). At each iteration step, the D-GRASP employs GRASP with greedy function considering F3 and F4 to search for a good quality JMA, and then applies another GRASP with greedy function considering F1 and F2 to find a good schedule for the given JMA. Several experiments were conducted to evaluate the D-GRASP performance using the five instances given by Kacem et al. (2002). The results indicate that the D-GRASP is very competitive or even superior compared to several state-of-the-art published algorithms for problems with three objectives – F1, F3, and F4. The D-GRASP finds a new Pareto optimal solution for the 8x8 and the 10x10 instances. In addition, the D-GRASP outperforms Huang (2010) for problems with different three objectives – F2, F3, and F4, by using 25 instances generated based on Kacem et al.(2002) and Lee and Pinedo (1997). For the four-objective problem, three different hybrid algorithms were developed – ant colony optimization (ACO) for JMA with simulated annealing (SA) for JOL (denoted as ACO+SA), ACO+GRASP, and GRASP+SA. By comparing the four algorithms using the 25 derived instances based on several performance metrics in multi-objective optimization, it is shown that D-GRASP performs best.