使用多目標演化演算法及移動瓶頸法之多目標排程

Multiobjective Scheduling by Multiobjective Evolutionary Algorithm and Shifting Bottleneck Procedure

鄭學謙(Hsueh-Chien Cheng)

指導教授 ： 傅立成

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.03022

摘要

這篇論文中研究如何解決多目標排程問題，由於基於週期時間(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.

並列關鍵字

Production scheduling ； Multiobjective optimization ； Evolutionary algorithm ； Shifting bottleneck

參考文獻

dispatching rules for manufacturing job shop operations,” International Journal

of Production Research, vol. 20, no. 1, pp. 27–45, 1982.

Ph.D. dissertation, Massachusetts Institute of Technology, 1965.

[4] J. H. Chen, L. C. Fu, M. H. Lin, and A. C. Huang, “Petri-net and GA-based

approach to modeling, scheduling, andperformance evaluation for wafer fabrication,”