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

[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.
[6] G. Minella, R. Ruiz, and M. Ciavotta, "A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem," INFORMS Journal on Computing, vol. 20, no. 3, pp. 451-471, 2008.
[7] M. M. Yenisey and B. Yagmahan, "Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends," Omega, vol. 45, pp. 119-135, 2014.
[8] S.-W. Lin and K.-C. Ying, "Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm," Computers & Operations Research, vol. 40, no. 6, pp. 1625-1647, 2013.
[9] T.-C. Chiang, H.-C. Cheng, and L.-C. Fu, "NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems," Expert Systems with Applications, vol. 38, no. 5, pp. 5986-5999, 2011.
[10] T. K. Varadharajan and C. Rajendran, "A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs," European Journal of Operational Research, vol. 167, no. 3, pp. 772-795, 2005.
[11] M. Nawaz, E. E. Enscore, and I. Ham, "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, vol. 11, no. 1, pp. 91-95, 1983.
[12] C. Rajendran, "Heuristic algorithm for scheduling in a flowshop to minimize total flowtime," International Journal of Production Economics, vol. 29, no. 1, pp. 65-73, 1993.
[13] J. E. C. Arroyo and A. A. de Souza Pereira, "A GRASP heuristic for the multi-objective permutation flowshop scheduling problem," The International Journal of Advanced Manufacturing Technology, vol. 55, no. 5-8, pp. 741-753, 2010.
[14] V. A. Armentano and J. E. C. Arroyo, "An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem," Journal of Heuristics, vol. 10, no. 5, pp. 463-481, 2004.
[15] J. Arroyo and V. Armentano, "A partial enumeration heuristic for multi-objective flowshop scheduling problems," Journal of the Operational Research Society, vol. 55, no. 9, pp. 1000-1007, 2004.
[16] R. Ruiz and T. Stützle, "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, vol. 177, no. 3, pp. 2033-2049, 2007.
[17] H. R. Lourenço, O. C. Martin, and T. Stützle, Iterated Local Search. Springer, 2003.
[18] J. M. Framinan and R. Leisten, "A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria," OR Spectrum, vol. 30, no. 4, pp. 787-804, 2007.
[19] J. M. Framinan and R. Leisten, "An efficient constructive heuristic for flowtime minimisation in permutation flow shops," Omega, vol. 31, no. 4, pp. 311-317, 2003.
[20] G. Minella, R. Ruiz, and M. Ciavotta, "Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems," Computers & Operations Research, vol. 38, no. 11, pp. 1521-1533, 2011.
[21] L. Paquete, M. Chiarandini, and T. Stützle, "Pareto local optimum sets in the biobjective traveling salesman problem: An experimental study," in Metaheuristics for Multiobjective Optimisation: Springer, 2004, pp. 177-199.
[22] J. Dubois-Lacoste, M. López-Ibáñez, and T. Stützle, "A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems," Computers & Operations Research, vol. 38, no. 8, pp. 1219-1236, 2011.
[23] J. Dubois-Lacoste, M. López-Ibáñez, and T. Stützle, "Adaptive “anytime” two-phase local search," in Learning and Intelligent Optimization: Springer, 2010, pp. 52-67.
[24] L. Paquete and T. Stützle, "A two-phase local search for the biobjective traveling salesman problem," in Evolutionary Multi-Criterion Optimization, 2003, pp. 479-493: Springer.
[25] H. Ishibuchi and T. Murata, "A multi-objective genetic local search algorithm and its application to flowshop scheduling," IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 28, no. 3, pp. 392-403, 1998.
[26] T. Murata and H. Ishibuchi, "MOGA: multi-objective genetic algorithms," in IEEE International Conference on Evolutionary Computation, 1995, vol. 1, pp. 289-294.
[27] H. Ishibuchi, T. Yoshida, and T. Murata, "Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling," IEEE Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 204-223, 2003.
[28] P.-C. Chang, J.-C. Hsieh, and S.-G. Lin, "The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem," International Journal of Production Economics, vol. 79, no. 3, pp. 171-183, 2002.
[29] P. Chang, S. Chen, and C. Liu, "Sub-population genetic algorithm with mining gene structures for multiobjective flowshop scheduling problems," Expert Systems with Applications, vol. 33, no. 3, pp. 762-771, 2007.
[30] P. Chang, S. Chen, and K. Lin, "Two‐phase sub population genetic algorithm for parallel machine-scheduling problem," Expert Systems with Applications, vol. 29, no. 3, pp. 705-712, 2005.
[31] C. Rajendran and H. Ziegler, "A multi-objective ant-colony algorithm for permutation flowshop scheduling to minimize the makespan and total flowtime of jobs," in Computational Intelligence in Flow Shop and Job Shop Scheduling, vol. 230, U. Chakraborty, Ed. (Studies in Computational Intelligence: Springer Berlin Heidelberg, 2009, pp. 53-99.
[32] P. C. Chang, S. H. Chen, Q. Zhang, and J. L. Lin, "MOEA/D for flowshop scheduling problems," in IEEE Congress on Evolutionary Computation, 2008.
CEC 2008. (IEEE World Congress on Computational Intelligence). 2008, pp. 1433-1438.
[33] A. Alhindi and Q. Zhang, "MOEA/D with Tabu Search for multiobjective permutation flow shop scheduling problems," in IEEE Congress on Evolutionary Computation (CEC), 2014, 2014, pp. 1155-1164.
[34] F. Jin, S. Song, and C. Wu, "Structural property and meta-heuristic for the flow shop scheduling problem," in Computational Intelligence in Flow Shop and Job Shop Scheduling: Springer, 2009, pp. 1-20.
[35] J. E. C. Arroyo and V. A. Armentano, "Genetic local search for multi-objective flowshop scheduling problems," European Journal of Operational Research, vol. 167, no. 3, pp. 717-738, 2005.
[36] T. Pasupathy, C. Rajendran, and R. K. Suresh, "A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs," International Journal of Advanced Manufacturing Technology, vol. 27, no. 7-8, pp. 804-815, 2005.
[37] Yandra and H. Tamura, "A new multiobjective genetic algorithm with heterogeneous population for solving flowshop scheduling problems," International Journal of Computer Integrated Manufacturing, vol. 20, no. 5, pp. 465-477, 2007.
[38] H.-C. Cheng, T.-C. Chiang, and L.-C. Fu, "Multiobjective permutation flowshop scheduling by an adaptive genetic local search algorithm," in IEEE Congress on Evolutionary Computation, 2008. CEC 2008.(IEEE World Congress on Computational Intelligence). 2008, pp. 1596-1602: IEEE.
[39] D. W. Corne, N. R. Jerram, J. D. Knowles, and M. J. Oates, "PESA-II: Region-based selection in evolutionary multiobjective optimization," in Proc. of the Genetic and Evolutionary Computation Conference, 2001, pp. 283-290.
[40] X. Li and M. Li, "Multiobjective local search algorithm-based decomposition for multiobjective permutation flow shop scheduling problem," IEEE Transactions on Engineering Management, vol. 62, no. 4, pp. 544-557, 2015.
[41] L. Ke, Q. Zhang, and R. Battiti, "Hybridization of Decomposition and Local Search for Multiobjective Optimization," IEEE Transactions on Cybernetics, vol. 44, no. 10, pp. 1808-1820, 2014.
[42] B.-B. Li and L. Wang, "A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling," IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 37, no. 3, pp. 576-591, 2007.
[43] H. Li and Q. Zhang, "Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II," IEEE Transactions on Evolutionary Computation, vol. 13, no. 2, pp. 284-302, 2009.
[44] J. Liu and C. R. Reeves, "Constructive and composite heuristic solutions to the P//∑Ci scheduling problem," European Journal of Operational Research, vol. 132, no. 2, pp. 439-452, 7/16/ 2001.
[45] C. Rajendran and H. Ziegler, "An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs," European Journal of Operational Research, vol. 103, no. 1, pp. 129-138, 1997.
[46] Q.-K. Pan and R. Ruiz, "A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime," Computers & Operations Research, vol. 40, no. 1, pp. 117-128, 2013.
[47] H. Ishibuchi, Y. Sakane, N. Tsukamoto, and Y. Nojima, "Adaptation of scalarizing functions in MOEA/D: An adaptive scalarizing function-based multiobjective evolutionary algorithm," in Evolutionary Multi-Criterion Optimization, 2009, pp. 438-452: Springer.
[48] Z. Wang, Q. Zhang, A. Zhou, M. Gong, and L. Jiao, "Adaptive Replacement Strategies for MOEA/D," IEEE Transactions on Cybernetics, vol. 46, no. 2, pp. 474 - 486, 2015.
[49] Y. Yuan, H. Xu, B. Wang, B. Zhang, and X. Yao, "Balancing convergence and diversity in decomposition-based many-objective optimizers," IEEE Transactions on Evolutionary Computation, vol. 20, no. 2, pp. 180-198, 2015.
[50] E. Taillard, "Benchmarks for basic scheduling problems," European Journal of Operational Research, vol. 64, no. 2, pp. 278-285, 1993.