應用人工蜂群演算法於多目標彈性零工型排程問題之研究

Discrete Artificial Bee Colony Algorithms for the Scheduling of Multi-Objective Flexible Job Shop Problems

黃茂家(Mao-Jia Huang)

指導教授 ： 徐旭昇

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

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

摘要

現今的經濟環境變遷快速，高科技產業的生產型態日漸複雜，單一產品生產時需要多樣且大量的物料，若在生產線上發生異常狀況時，往往造成更多的人力成本及物料成本甚至影響到成品交貨而造成顧客滿意度下降。彈性零工型生產排程在實務上應用範圍較廣，且多功能之機具可有效減少生產複雜度，故本研究將針對彈性零工型排程問題進行探討。
本研究延續Kacem et al. (2002a, 2002b)所提之測試題，將原先三個目標關鍵機台工作量、所有機台總工作量以及總完工時間增加為四個目標總延遲時間、關鍵機台工作量、所有機台總工作量以及總完工時間，提出三種人工蜂群演算法Artificial Bee Colony(ABC)，第一種人工蜂群演算法(ABC1)使用分層式求解法，先求解作業-機台的指派，再求解所有作業的排程順序，在區域搜尋方面提出兩種不同方法進行相互比較，同時設定外在母體在不同階段執行更新外在母體機制以儲存較佳的解並提供給下一代作為初始解，同時以權重決定方式可細分為固定式(ABC1f, fixed)及隨機式(ABC1r, random)；第二種人工蜂群演算法(ABC2)，以大量的機台-作業組合搭配greedy function以求得初始解，進而使用模擬退火法提升解之品質，同樣可細分為固定式權重(ABC2f)以及隨機式權重(ABC2r)；第三種人工蜂群演算法(ABC3)為ABC1r以及ABC2r之結合，以ABC1r為主體架構，將ABC2r之解作為每個世代之間的參考初始解。
本研究所採用測試題有五題，包含部分彈性8(工件)×8(機台)、完全彈性10×10、完全彈性和有到達時間的4×5、10×7以及15×10五題測試題中關鍵機台工作量、所有機台總工作量以及總完工時間，本研究於大部分的測試題優於FL+EA (Kacem et al. 2002b)、PSO+SA(Xia. and Wu. 2005)、PSO+TS(Zhang et al. 2009)，此外有五種不同的交期參數因子設定，共產生25題並以總延遲時間、關鍵機台工作量以及所有機台總工作量與黃文洲(2010)之演化式演算法相互比較，在25題測試題中皆有不錯之表現。
此外以四個目標五演算法以及兩種三個目標兩演算法(ABC1f, ABC2f)互相比較，對於不同大小的測試題，ABC3在大部分測試題皆優於其他演算法，而在三個目標之下兩演算法提供了不同區域的前緣解但ABC2f之表現優於ABC1f。

關鍵字

多目標最佳化 ； 彈性零工型排程問題 ； 人工蜂群演算法 ； 分層式求解法 ； 模擬退火法

並列摘要

The scheduling of flexible job shop problems are often encountered in practice. The goal that managers want to achieve is often multi-fold. This thesis addresses the problem of finding quality solutions for multi-objective flexible job shop scheduling (MO-FJSS), in which the objectives include makespan (F1), total tardiness (F2), critical machine workload (F3), and total machine workload (F4). Each objective has its own purpose in scheduling jobs. The thesis proposes several discrete artificial bee colony (ABC) algorithms to solve the MO-FJSSP. ABC simulates the intelligent foraging behavior of a honeybee swarm, and is one of the most recently introduced in swarm-based algorithms.
In this research, three versions of ABC are presented. In the first version, ABC1, the initial populations are constructed using the following scheme: Generate operation sequence first, and then assign each operation to a machine with the shortest processing time. The external archive is updated at the end of each generation. In each generation, the best solution of the population in the previous generation is retained as the food source of an employed bee. The food source of any other employed bee is the better solution between an archive solution randomly selected and a solution obtained using information sharing. The onlooker bees use insertion local search to refine solution quality. Each scout bee selects an archive solution as a candidate of food source for the next generation. The ABC1 can be further classified into ABC1f and ABC1r based on whether the weighted vectors on objectives are predetermined or randomly selected.
The second version, ABC2, generates a large set of operation-machine assignment (OMA) lists according to different machine permutations. For each generation, a number of OMAs were selected, and a hybrid heuristic that combines greedy-function with simulated annealing is applied to find a quality solution with respect to each OMA. Similar to ABC1, the ABC2 is also classified into ABC2f and ABC2r based on the same condition. The third version, ABC3, hybridizes ABC1r and ABC2r.
Experiments were conducted to test the performances of the five proposed ABC algorithms, using benchmark instances generated based on Kacem et al. (2002). The results indicate that, in the case of three objectives - (F1, F3, F4), ABC2 outperforms ABC1, and ABC2 has found competitive solutions with several published articles. In the problem of four objectives, ABC2 outperforms ABC1 in both the cases that the weighted vectors are randomly generated and predetermined. Furthermore, ABC3 produces almost all solutions that were either better or equivalent to the best of ABC1 and ABC2.

並列關鍵字

simulated annealing ； Multi-objective combinatorial optimization ； flexible job shop scheduling ； artificial bee colony ； hierarchical approach

參考文獻

黃文洲，「演化式演算法於多目標彈性零工型排程問題之研究」，元智大

Amiri, M., Zandieh, M., Yazdani, M. and Bagheri A. (2010) A variable neighborhood search algorithm for the flexible job-shop scheduling problem. International Journal of Production Research, 48(19):5671-5689.

Brandimarte, P., (1993) Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3):157-183.

Baykasoğlu, A. Ozbakir, L. and Sonmez, 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.

Baykasog˘lu, A. and O‥zbakır, L. (2010) Analyzing the effect of dispatching rules on the scheduling performance through grammar based flexible scheduling system, International Journal of Production Economics, 124:369-381.