傅立成臺灣大學:資訊工程學研究所鄭學謙Cheng, Hsueh-ChienHsueh-ChienCheng2010-05-172018-07-052010-05-172018-07-052009U0001-2807200915274000http://ntur.lib.ntu.edu.tw//handle/246246/183345這篇論文中研究如何解決多目標排程問題，由於基於週期時間(cycle time)與交期(due date)的目標時常互相抵觸，因此如何找出維持兩者間的平衡之排程對製造系統而 言是很重要的。我們提出了一個兩層的多目標瀰集演化演算法(memetic algorithm)及移動瓶頸法(shifting bottleneck procedure)來解決多目標排程問題，第一層使用瀰集演化演算法來搜尋初始排程，接著第二層使用移動瓶頸法中的重新最佳化程序，在我們提出的第一層演算法中使用的元件可以維持探索及利用間的平衡，在第二層中，重新最佳化程序使用了基於瀰集演化演算法的子問題解決法。透過在公開的測試資料上與一個最近的文獻比較的實驗結果驗證我們提出的方法是有效的，優秀的實驗結果指出我們提出的方法有實際應用到製造系統的潛力。In this thesis, a multiobjective scheduling problem is addressed. Since cycle time-based objectives and due date-based objectives frequently contradicts with each other, a well-balanced schedule is important for manufacturing systems. A two-stage algorithm, multiobjective memetic algorithm and shifting bottleneck, MOMASB, is proposed to solve multiobjective scheduling problem. The first stage is a memetic algorithm, RMA, to generate initial schedules followed by the second stage, which is a re-optimization procedure inspired by SB. The components of the proposed RMA are carefully designed to maintain a balance between exploration and exploitation. In the second stage, the re-optimization applys a memetic algorithm-based subproblem, SSPMA. Experimental results compared with a recent approach in the literature show the effectiveness of the proposed MOMASB. The promising results indicate the potential of MOMASB to be applied to practical use.1 Introduction 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Rule-based Dispatching . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Multiobjective Evolutionary Algorithm . . . . . . . . . . . . . 3.2.3 Multiobjective Evolutionary Scheduling . . . . . . . . . . . . . 5.2.4 Shifting Bottleneck Procedure . . . . . . . . . . . . . . . . . . 6.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Preliminary 9.1 Multiobjective Optimization . . . . . . . . . . . . . . . . . . . . . . . 9.1.1 Multiobjective Optimization Problems (MOPs) . . . . . . . . 9.1.2 Existing Approaches to MOPs . . . . . . . . . . . . . . . . . . 10.2 Evolutionary Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 13.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.2.2 Multiobjective Evolutionary Algorithm . . . . . . . . . . . . . 17.3 Multiobjective Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 18.4 Shifting Bottleneck Procedure . . . . . . . . . . . . . . . . . . . . . . 21 Multiobjective Memetic Algorithm and Shifting Bottleneck Proce-ure (MOMASB) for Multiobjective Scheduling 23.1 Overview of MOMASB . . . . . . . . . . . . . . . . . . . . . . . . . . 23.2 First Stage: Initial Schedule Generation . . . . . . . . . . . . . . . . 25.2.1 Chromosome Encoding and Decoding . . . . . . . . . . . . . . 25.2.2 Genetic Algorithm Components . . . . . . . . . . . . . . . . . 28.2.3 Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34.2.4 Stopping Criterion . . . . . . . . . . . . . . . . . . . . . . . . 35.3 Second Stage: Schedule Re-optimization . . . . . . . . . . . . . . . . 35.3.1 Bottleneck Selection . . . . . . . . . . . . . . . . . . . . . . . 37.3.2 Subproblem Formulation . . . . . . . . . . . . . . . . . . . . . 37.3.3 Memetic Algorithm-based Subproblem Solution Procedure . . 40.3.4 Best Schedule Selection . . . . . . . . . . . . . . . . . . . . . . 45.3.5 Stopping Criterion . . . . . . . . . . . . . . . . . . . . . . . . 46 Experiments and Results 47.1 Description of Problem Addressed . . . . . . . . . . . . . . . . . . . . 47.1.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . 47.1.2 Concerned objectives . . . . . . . . . . . . . . . . . . . . . . . 48.2 Benchmark Instances and Algorithm . . . . . . . . . . . . . . . . . . 48.2.1 Benchmark Instances . . . . . . . . . . . . . . . . . . . . . . . 48.2.2 Benchmark Algorithm . . . . . . . . . . . . . . . . . . . . . . 49.3 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50.3.1 The Proposed MOMASB . . . . . . . . . . . . . . . . . . . . . 50.3.2 Benchmark Algorithm . . . . . . . . . . . . . . . . . . . . . . 51.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 51.4.1 Performance Assessment . . . . . . . . . . . . . . . . . . . . . 52.4.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 53.4.3 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Conclusions and Future Work 64ppendix A | | Notation 66ppendix B Disjunctive Graph Representation 67eference 69application/pdf742352 bytesapplication/pdfen-US生產排程多目標最佳化演化式演算法瓶頸飄移法Production schedulingMultiobjective optimizationEvolutionary algorithmShifting bottleneckthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183345/1/ntu-98-R96922066-1.pdf