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

Abstract

本論文將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 測試問題集進行實驗分析，並與知名演算法比較，本論文提出的演算法在中、大型的問題具有較好的效果。