摘要
本研究旨在比較構造啟發式算法、模擬退火算法與粒子群優化算法於流水線排列排程問題最佳解之求解能力與穩健性。排程問題為Carlier問題，排程目標為最大完工時間最小化。文中首先以WinQSB軟體中的Palmer、CDS與RA構造啟發式算法求解Carlier排程問題，其次以MATLAB最佳化工具箱之模擬退火算法求解Carlier排程問題，之後再以自行撰寫之粒子群優化算法MATLAB程式求解Carlier排程問題。經比較後發現，Palmer、CDS與RA皆無法求得最佳解，僅能求得較佳解。模擬退火法與粒子群優化算法雖有能力求得最佳解，但求解能力易受算法參數之影響。最後，針對模擬退火法與粒子群優化算法，以全因子實驗與變異數分析探討影響算法求解能力之顯著因子。
關鍵字：流水線排列排程、構造啟發式、模擬退火法、粒子群優化算法。
ABSTRACT
This paper aims to compare the difference among constructive heuristics, simulated annealing, and particle swarm optimization in solving the permutation flow shop scheduling problems. The scheduling problems are Carlier problems. The maximum completion time is chosen as the objective function. First of all, constructive heuristics such as Palmer, CDS and RA provided by WinQSB software are applied to solve the Carlier problems. Then, simulated annealing provided in MATLAB optimization toolbox is used to solve the Carlier problems. Next, particle swarm optimization created by the authors in MATLAB is used to solve the Carlier problems. According to the results, it can be found that Palmer, CDS and RA cannot find optimal solutions. Simulated annealing and particle swarm optimization could find optimal solutions, but the ability of finding optimal solutions is easy to be affected by the parameters of algorithms. This paper applies a full factorial design of experiments and analysis of variance method to identify significant parameters of algorithms for simulated annealing and particle swarm optimization.
Keywords: Permutation Flow Shop Scheduling; Constructive Heuristics; Simulated Annealing; Particle Swarm Optimization
|