智慧型基因演算法於多目標排程之發展與應用－以PCB鑽孔作業為例

Development Intelligent Genetic Algorithms for Multi-Objective Scheduling—An Example of Drilling Operation Problems in PCB Factory

王治元(Chih-Yuan Wang)

指導教授 ： 張百棧 博士

元智大學/工程學院/工業工程與管理學系/碩士(2004年)

摘要

目前許多排程相關之學術研究多以單一決策目標為發展方向，然而，在真實的生產製造環境中，管理者於決策時往往需同時考量多項衡量指標。此外，多目標基因演算法(MOGA)經學者提出後已成功應用於排程問題，但其基因運算元演化過程及求解效率仍有很大改善空間，有鑑於此，本研究共提出三種不同之智慧型基因演算法(區間變動基因演算法、自我調適型基因演算法及兩階式基因演算法)求解完全相同平行機台之多目標排程問題，以總完工時間、總延遲時間最小化為排程目標，利用智慧型基因演算法獨特之搜尋特性求出多目標最佳化問題之柏拉圖最佳解。最後，以印刷電路板之鑽孔作業為案例，並以MOGA為比較標竿進行驗證，經實驗證明，二階式多目標基因演算法之求解效率最佳，且本研究所提出之三項智慧型基因演算法其求解效果及效率均優於MOGA，尤其在求解中大型問題時更能展現其求解能力之優越性。

關鍵字

多目標基因演算法 ； 智慧型基因演算法 ； 柏拉圖最佳解 ； 印刷電路板

並列摘要

The main task of scheduling problems in the past research is to solve the single objective problem. Nevertheless, there are many different targets in the real-world scheduling problem. Therefore, the main propose of this research is to develop intelligent multi-objective genetic algorithm that can find better Pareto optimal solutions among these conflicting objectives and help the manager to make a suitable scheduling decision in the manufacturing process. In this research, three novel multi-objective genetic algorithms including multi-objective genetic algorithm with variable rates (VMOGA), self-adaptive multi-objective genetic algorithm (SAMOGA) and two-phase multi-objective genetic algorithm (TPMOGA) are proposed to deal with such a complicated real-world case. Real-world instances are applied as well to evaluate the effectiveness and efficiency of VMOGA, SAMOGA and TPMOGA. The result indicates that TPMOGA is more effective than MOGA, VMOGA and SAMOGA in solution quality. Each intelligent multi-objective genetic algorithm are more efficiency than MOGA, especially apply to complicated multi-objective scheduling problems.

並列關鍵字

Intelligent Multi-Objective Genetic Algorithm ； Pareto Optimal Solutions ； Multi-Objectives Scheduling

參考文獻

1. Allahverdi, A. and J. Mittenthal, “Scheduling on M Parallel Machines Subject to Random Breakdowns to Minimize Expected Mean Flow Time,” Naval Research Logistics, 41, pp.677-682, 1994.

2. Bagchi, T. P., Multiobjective Scheduling by Genetic Algorithm, Kluwer Academic Publishers, 1999.

3. Baker, R. K., “Sequence Rules and Due-Date Assignments in A Job Shop,” Management Science, 30(9), 1984.

4. Balakrishnan, N., J. J. Kanet, and S. V. Sridharan, “Early /Tardy Scheduling with Sequence Dependent Setup on Uniform Parallel Machines,” Computers & Operations Research, 26(2), pp127-141, 1999.

5. Basseur, M., F. Seynhaeve, and E. Talbi, “Design of Multi-Objective Evolutionary Algorithms: Application to The Flow-Shop Scheduling Problem,” Proceedings of the 2002 Congress on Evolutionary Computation, 2, pp.1151-1156, 2002.