GRASP於多目標彈性零工型排程問題解算之研究

Optimizing Multi-Objective Flexible Job Shop Scheduling Problems with Greedy Randomized Adaptive Search Procedure

魏名晨(Ming-Chen Wei)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(2012年)

https://doi.org/10.6838/YZU.2012.00284

摘要

現今許多產品生產型態，是採用彈性零工型生產方式，亦即每個工件皆有一至多個製程，並且每個製程可在一至多個機台或廠區完成。同時，從製造業的實際觀點，一個好的生產排程規劃，應該要有多方面的考量，例如降低交貨延遲時間、生產效率提升、減少生產設備磨耗與怠工時間、降低半成品之存貨成本等等，因此本研究就多目標彈性零工型生產排程問題加以探討。
本研究延續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之表先優於其他三種演算法。

關鍵字

多目標最佳化 ； 彈性零工型生產排程 ； 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.

並列關鍵字

GRASP ； meta-heuristics ； performance metrics ； Multi-objective evolutionary algorithms ； flexible job shop scheduling ； Pareto dominance

參考文獻

36.蘇海興，「門檻值搜尋法求解含完工期限下多目標彈性零工型排程問題」，元智大學工業工程與管理研究所，碩士論文，民國100年。

5.Binato, S., Hery, J., Loewenstern, D.M. and Resende, M.G.C. (2002) A greedy randomized adaptive search procedure for job shop scheduling. In: Ribeiro, C.C., Hansen, P. (Eds.), Essays and Surveys on Metaheuristics, Kluwer, pp. 58-79.

1.Armentano, V.A. and de Araujo, O.C.B. (2006) GRASP with memory-based mechanisms for minimizing total tardiness in single machine scheduling with setup times, Journal of Heuristics, 12:427-446.

2.Armentano, V.A. and de Franca Filho, M.F. (2007) Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach, European Journal of Operational Research, 183:100-114.

3.Baykasoğlu, A. Özbakir, L. and Sönmez, A. (2004) Using multiple objective tabu search and grammars to model and solve multi-objective flexible job shop scheduling problems, Journal of Intelligent Manufacturing, 15: 777-785.