- 學位論文
應用限制式粒子群及基因演算法於解決排程問題之研究
Research of a Constraint-Based Particle Swarm Optimization and Genetic Algorithm Approach for Scheduling Problems
摘要
近年來，由於網路科技的發達進而改變了企業的競爭區域、客戶的消費行為、及製造業的生產方式。所以如何能在顧及穩定的產品品質的情況下於消費者的期限內完成，已是目前生產製造業中所需達成的重要指標之一。 本論文發展出一個整合限制推理之粒子群及基因演算法，用來解決零工型排程問題，由於粒子群演算法主要透過適應函數方式來評估可行的排程，但針對複雜的排程問題，則缺乏有效且正確率高的解題效果。本研究整合限制推理及粒子更新機制於粒子群演算法架構中，用來減少粒子產生的搜尋空間，使得粒子群演算法能夠更快速的找出符合限制之最佳解。於粒子更新機制中，本研究於粒子更新時混合了基因演算法更新機制以補足粒子群演算法於區域搜尋能力不足的缺點，使粒子之搜尋範圍及效能得到良好的提升。根據實驗結果顯示，限制式粒子群及基因演算法較一般傳統的粒子群演算法有更快速且較符合排程目標之結果。
並列摘要
The job-shop scheduling(JSP) problem is a process of assigning a limited number of machines to operations over time in a consistent manner. Existing particle swarm optimization (PSO) designed for the JSP are devise an appropriate representation of solutions together with problem-specific particle operators to avoid infeasible or illegal schedules. In this paper, we propose a constraint-based approach to generate valid particle in either the initial phase or the evolutionary process. This approach allows constraints to be specified as relationships among operations according to precedent constraints and capacity constraints in the form of a constraint network. The constraint-based reasoning is employed to produce valid particles using constraint propagation to assure the particle in complying the predefined constraint network. Additionly, the new udate approach based on genetic algorithm (GA) is incorporated to produce better schedules. The proposed approach is compared with a traditional PSO using well-known benchmarks for the JSP. Better computational efficiency and optimal schedules form constraint-based PSO and GA are demonstrated.