求解零工式生產排程問題的仿水流優化演算法

Abstract

本研究提出利用零工式生產排程問題的前行限制階層特性進行演化的技術，並使用機器加工步驟排序編碼法增加求解效率，同時開發一套以仿水流演算法求解零工式生產排程問題(Water Flow-like Algorithm for Job-shop scheduling Problems, WFA4JSP)的系統。仿水流演算法是近代創新的演算法，透過模擬水流在自然界中的流動和循環方式來進行演化作業，主要的特色在於能動態調整解代理人的數量，並利用分流移步、匯流、蒸發、和降雨四個作業來進行演化。有別於傳統求解零工式生產排程問題常使用的加工步驟排序的編碼法常出現重複搜尋的浪費，本研究使用以機器加工步驟排序編碼法(Machining-sequence Coding, MSC)來增加求解效率，並融合零工式生產排程問題的加工步驟前行限制特性和因為使用MSC所形成的機器加工步驟前行限制特性設計出以機器為基的部分前行階層加工步驟重新指派法(Partial Machine Based Precedence Level Operation Reallocated, PMBPLOR)來進行水流的移步作業，最後與優加劣減螞蟻擇段系統和兩階段粒子群演算法做求解效能比較。結果顯示，在設定相同目標函數呼叫次數上限的停止條件之下，WFA4JSP於複雜度小的問題普遍可以搜尋到最佳解，而複雜度較大的問題其相對誤差與其他演算法則不相上下。

This research propose a technique which is using the level property of precedence constraints of job-shop scheduling problems to process the evolution, and use machining-sequence coding method to improve the efficiency of evolution, furthermore, develop a system which is using the water flow-like algorithm to solve the job-shop scheduling problems(WFA4JSP). Water flow-like algorithm is a modern innovative algorithm which is imitating the concept of water flow on the ground. The main characteristics of water flow-like algorithm is dynamically adjusting the number of solution agents, and using splitting, merging, evaporation, and precipitation operators to process the evolution. Instead of using the traditional operation sequence coding method which often cause a waste of re-search, this research using machining-sequence coding method to improve the efficiency of evolution and combining with the operation precedence constraints of job-shop scheduling problems and the machining-operation precedence constraints which is formed by using machining-sequence coding method to develop a partial machine based precedence level operation reallocated method to execute splitting operator. Compared with the “Added to the superior segments and subtracted from inferior segments ant system” and “A two-stage PSO” method, under the same stop criterion, the results show WFA4JSP can find the best solution of most small complexity problems, and the relative deviation value of large complexity problems are comparable.