以MOEA/D結合適應性區域搜尋求解多目標定序流線型工廠排程問題

MOEA/D with adaptive local search for multiobjective permutation flowshop scheduling problems

張祐騰(Chang Yu-Teng)

指導教授 ： 蔣宗哲

國立臺灣師範大學/理學院/資訊工程學系/碩士(2017年)

https://doi.org/10.6345/NTNU202203489

摘要

本論文將MOEA/D應用於求解多目標定序流線型工廠排程問題（multi-objective permutation flowshop scheduling problem），已知多目標定序流線型工廠排程問題是一個 NP-hard 問題，無法確保在多項式時間內將該問題求得最佳解。在這個問題中有多個零件（job）需要依序送入機器（machine）中加工，而每個零件根據製程（operation）不同而有不同的加工時間（processing time）；所有零件皆加工完成的時間為最大完工時間（makespan），而每個零件的完工時間總和為總流程時間（total flow time），我們希望能同時最小化最大完工時間與總流程時間，但縮短最大完工時間可能使得總流程時間增加，反之亦然；然而，我們可以求出非凌越解（non-dominated solution），這些解在目標空間形成一條柏拉圖前緣（Pareto front），我們的目標是求解得到盡量靠近真實解，且分佈越完整的柏拉圖前緣。

過往文獻中，使用 MOEA/D 這種將目標空間（objective space）分解的方法並不多；本論文深入探討 MOEA/D 流程中各個操作對效能之影響；除此之外，我們使用區域搜尋強化解的品質，並探討不同搜尋方式對效能之影響。我們使用Taillard 測試問題集進行實驗分析，並與知名演算法比較，本論文提出的演算法在中、大型的問題具有較好的效果。

關鍵字

多目標 ； 定序流線型工廠排程問題 ； 區域搜尋

並列摘要

none

並列關鍵字

MOEA/D

參考文獻

[1] E. Zitzler, M. Laumanns, and L. Thiele, "SPEA2: Improving the strength Pareto evolutionary algorithm," Eidgenössische Technische Hochschule Zürich (ETH), Institut für Technische Informatik und Kommunikationsnetze (TIK) Zürich, Switzerland, 2001.

[2] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.

[3] E. Zitzler and S. Künzli, "Indicator-based selection in multiobjective search," in Parallel Problem Solving from Nature-PPSN VIII, 2004, pp. 832-842: Springer.

[4] N. Beume, B. Naujoks, and M. Emmerich, "SMS-EMOA: Multiobjective selection based on dominated hypervolume," European Journal of Operational Research, vol. 181, no. 3, pp. 1653-1669, 2007.

[5] Q. Zhang and H. Li, "MOEA/D: A multiobjective evolutionary algorithm based on decomposition," IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, 2007.