遺傳演算法在製造業排程問題之應用

製造業排程問題，乃是融合彈性製造系統、隨機變動工作生產，少量多樣工作生產模式之完成總時間最佳化排程問題。本研究針對工作生產隨機變動特性，目前實務上藉由經驗法則進行排程或面對 NP-Hard (Non-Deterministic Hard) 無法以合理時間內求解，也就是沒有立即可行最佳策略的問題，提出最適之演算法。本研究提出中斷接合的原則，將工作生產的序先求最佳化，再藉由訂定工作生產績效權重，來軟化求解目標。運用具求解最佳解能力之遺傳基因演算法 (Genetic Algorithm) ，發展出一套最適化的演算模式。隨後在求解過程中，探討分析總完工時間、總延遲時間、總延遲訂單數之改善率，三大製造業界所最關心的指標。最後以模式驗證、實例驗證，求解製造業彈性製造系統隨機變動工作生產排程之最適解。本研究之主要貢獻在於建立彈性製造系統最適化排程演算公式，針對隨機變動生產工作所面臨 NP-Hard 問題84%為無效解之情況下，提出優先權重中斷接合軟化目標的方法，經驗證測試能有效求解且改良求解之速度，可提供製造業排程使用且可達績效指標。

關鍵字

遺傳基因演算法；製造業排程問題；隨機變動工作生產

並列摘要

Manufacturing scheduling is a complicated and non-deterministic polynomial-time hardness problem. The fundamental issue lies in how to find the best corresponding relations between different factors such as manufacturing stars with the task due soonest, an N job in one machine sequencing algorithms for minimizing the number of late jobs, shortest sum of completion time, shortest processing time and various optimizers for single-stage production in any production lines. There is no absolutely satisfying solution formula in the practical research field. Henceforth, the manufacturing scheduling defines the problem as the essential qualities of permutations and combinations, then the satisfy constraints research in an extremely large number of solution sets. For this thesis, the method of Genetic Algorithms is adopted to construct solution models. The range of research in this thesis is limited to the current production lines and S.P.S.S. software is used to develop formulas for calculation. Finally this way of manufacturing scheduling problem solving solution proves to be workable.