以強化突變機制之基因演算法求解多目標彈性零工式工廠排程問題

Abstract

如何有效分配資源以及提高生產效率、降低生產成本，是製造業一直以來想要達到的目標，這就是為何十幾年來生產排程問題可以如此的熱門。排程問題大部分都屬於組合最佳化問題，零工式工廠排程問題（Job-shop Scheduling Problem, JSP）便是其一。由於此類問題的複雜度很高，通常難以求得最佳解。彈性零工式工廠排程問題（Flexible Job-shop Scheduling Problem, FJSP）則為零工式工廠排程問題的延伸，主要透過分配製程的作業機台（路由問題），以及變換製程在機台上的順序（排序問題）來最小化最大完工時間（makespan）、機台總工作量（total workload）和最大機台工作量（maximum workload）。 本論文所提出的演算法主體為基因演算法（Genetic Algorithm, GA），搭配交換關鍵製程以及重新插入關鍵製程來做突變，並且強化插入關鍵製程的方式。而為了求得在多個目標上的最佳化，本論文採用柏拉圖分級法（Pareto ranking）當作選擇機制，目的在於找到柏拉圖最佳解（Pareto optimal solutions）。 實驗的問題為 BR data 的十個測試問題。本論文提出的演算法在非凌越解（non-dominated solutions）個數較多的問題中能大幅度更新目前的已知非凌越解。