粒子群演算法結合低閒置策略於生產排程之應用

An Application of Particle Swarm Optimization with Low Idle Strategy on Job-Shop Scheduling

鄒佳臻(Chia-Chen Tsou)

指導教授 ： 李維平

中原大學/商學院/資訊管理學系/碩士(2008年)

https://doi.org/10.6840/cycu200900493

摘要

排程問題是一NP-complete的問題，當工作數目和機器數目增大時，求解的複雜度變的相當高。本研究欲改善目前文獻於求解排成問題的求解效率。
本研究提出一個以粒子群演算法為基礎的粒子群演算法結合低閒置策略。在此策略中，結合了五種方法。第一，採用LRPT(Longest Remaining Process Time)的方式，初始粒子位置；第二，採用作業為基礎編碼方式(Operation-based)進行編碼；第三，在求得適應值的過程中，透過低閒置策略，轉變粒子位置；第四，最佳解的更新方式則採用D.Y. Sha and Cheng-Yu Hsu (2006)所提出的多樣化策略，以增加粒子的多樣性；第五，利用任意兩點交換法避免落入區域最佳解。
在粒子群演算法(PSO)中，訂定初始化規則，有助於改善起始解。在計算目標值得過程中，增加低閒置策略，並依據處理結果，更新粒子資料，可加速求得最佳解。多樣化策略，可增加粒子的多樣性，避免粒子落入區域最佳解。任意兩點交換法，將工作隨機交換，亦可避免落入區域最佳解。透過停滯次數，當粒子久未更新，則使用任意兩點交換法，以縮減運算時間，提高演算速率。
本研究將透過標竿測試問題(FT06，FT10，FT20, LA01, LA08)，探討粒子群演算法結合低閒置策略對於生產排程的搜尋成效，相較於先前文獻的閒置法則，本研究提出的低閒置策略可達到較佳的收斂效益。成效評估將以運算時間進行評估。

關鍵字

閒置時間 ； 任意兩點交換法 ； 排程 ； 粒子群演算法

並列摘要

Job shop scheduling problem usually is treated as a NP-complete problem. As the job number and the machine number(variables) are increased, the complex level of solution will become higher. In this paper, we are focus on improving the efficiency to solve the JSP problem.
We develop a particle swarm optimization with low idle strategy, which is based on PSO. There are five methods in this strategy. First, it will initialize particle position by LRPT(Longest Remaining Process Time). Second, it uses operation-based method to encode. Third, it changes particle position by low idle strategy when reaching fitness value. Forth, it uses diversification strategy( D.Y. Sha and Cheng-Yu Hsu, 2006) to increate particle diversities and finally, it uses two point change method to avoid to fall into a local solution.
In particle swarm optimization, defining initial rule could improve initial fitness. Low idle strategy in calculating fitness value and changing particle position by process result could speed up the process of searching solution. Diversification strategy could increase particle diversities and avoid particle for falling into a local solution. Also, two point swap method could avoid particle for falling into a local solution by operation exchange. By stand times, we use two point swap method to decrease calculating time and increate performance when the particle have not been updated for a long time.
We discuss searching performance of PSO with low idle strategy and test this strategy on FT06, FT10, FT20, LA01 and LA08 test problems. Compare with idle rule quoted before, the new idle strategy which we propose could calculate a better convergence and we can evaluate the performance by the executing time.

並列關鍵字

Schedule ； Idle time ； PSO ； Two point swap method

參考文獻

李旺蒼，民95，” 以粒子群最佳化為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究”，中央大學碩士學位論文。

D.Y. Sha and Cheng-Yu Hsu, 2006, “A hybrid particle swarm optimization for job shop scheduling problem,” Computers & Industrial Engineering 51 (2006) 791-808.

Xinggang Luo, Dingwei Wang, Jiafu Tang, Yiliu Tu, Jun. 2006, “An Improved PSO Algorithm for Resource-Constrained Project Scheduling Problem,” Proceedings of the 6th World Congress on Intelligent Control and Automation, June 21-23, 2006, Dalian, China.

Fuqing Zhao, Qiuyu Zhang, Yahong Yang, Jun. 2006, “An Improved Particle Swarm Optimization-Based Approach for Production Scheduling Problems,” Proc IEEE Intemational Conference on Mechatronics and Automation June 25-28, 2006, Luoyang, China.

Jie Gao, Mitsuo Gen, Linyan Sun, July 2006, “A Hybrid of Genetic Algorithm and Bottlenect Shifting for Flexible Job Shop Scheduling Problem” GECCO’06 ACM 1-59593-186-4/06/0007