Journal of Shandong University(Engineering Science) ›› 2019, Vol. 49 ›› Issue (1): 75-82.doi: 10.6040/j.issn.1672-3961.0.2018.540

• Control Science & Engineering • Previous Articles     Next Articles

Optimization of job shop scheduling based on improved particle swarm optimization algorithm

Hongming LIU(),Hongyan ZENG,Wei ZHOU*(),Tao WANG   

  1. College of Automation Engineering, Chengdu University of Technology, Chengdu 610059, Sichuan, China
  • Received:2018-12-18 Online:2019-02-01 Published:2019-03-01
  • Contact: Wei ZHOU E-mail:1270078949@qq.com;zhouwei@cdut.edu.cn
  • Supported by:
    国家自然科学基金资助项目(11675028)

RichHTML

37

PDF (PC)

1193

Abstract:

An improved particle swarm optimization algorithm was proposed based on adaptive weights and chaos aiming at the job shop scheduling. A multiple constrained job shop scheduling model was built with the shortest machining time as the optimization goal. The mapping relationship between particle parameters and operation sequences was obtained by coding method based on ranked order value. The inertial coefficient and acceleration factor in the particle swarm optimization algorithm were improved based on the adaptive weights, so that the algorithm could dynamically adjust parameters based on the fitness value. The reverse learning was used to improve the quality of initial solution. Considering the problem of local optimum, some measures were used to enhance the search of algorithm, such as Lévy flight, variable neighborhood search and chaos. The results showed that improved particle swarm optimization could effectively improve utilization of particles, balance the global search and local search, avoid the premature convergence of the traditional particle swarm optimization algorithm, and get better results.

Key words: job shop scheduling, adaptive weights, chaos, Lévy flight, particle swarm optimization

CLC Number: 

  • TP391

Fig.1

Flowchart of improved particle swarm algorithm"

Table 1

Comparison of IPSO and PSO test results"

实例 问题规模 已知最优解/s IPSO PSO 最小值提升率/% 平均值提升率/%
最小值/ s 平均值/ s 寻优成功率/% 最小值/ s 平均值/ s 寻优成功率/%
FT06 6×6 55 55 55 100 56 58 0 1.79 5.17
FT10 10×10 930 975 1 027 0 1 075 1 196 0 9.30 14.13
FT20 20×5 1 165 1 206 1 222 0 1 429 1 526 0 15.6 19.92
LA01 10×5 666 666 666 100 666 709 5 0 4.58
LA06 15×5 926 926 926 100 926 938 35 0 1.28
LA11 20×5 1 222 1 222 1 222 100 1 222 1 259 15 0 2.94
LA16 10×10 945 973 1 011 0 1 043 1 118 0 9.40 9.57

Fig.2

Comparison of IPSO and PSO optimization curves"

1 RUDOLPH G . Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5 (1): 96- 101.
doi: 10.1109/72.265964
2 BHOSALE K C , PAWAR P J . Material flow optimization of flexible manufacturing system using real coded genetic algorithm(RCGA)[J]. Materials Today Proceedings, 2018, 5 (2): 7160- 7167.
doi: 10.1016/j.matpr.2017.11.381
3 CRUZCHÁVEZ M A , MARTÍNEZRANGEL M G , CRUZROSALES M H . Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem[J]. International Transactions in Operational Research, 2017, 24 (5): 1119- 1137.
doi: 10.1111/itor.2017.24.issue-5
4 BERTSIMAS D , TSITSIKLIS J . Simulated annealing[J]. Statistical Science, 1993, 8 (1): 10- 15.
doi: 10.1214/ss/1177011077
5 陈知美, 顾幸生. 基于蚁群算法的不确定条件下的Job Shop调度[J]. 山东大学学报(工学版), 2005, 35 (4): 74- 79.
doi: 10.3969/j.issn.1672-3961.2005.04.018
CHEN Zhimei , GU Xingsheng . Job shop scheduling with uncertain processing time based on ant colony system[J]. Journal of Shandong University (Engineering Science), 2005, 35 (4): 74- 79.
doi: 10.3969/j.issn.1672-3961.2005.04.018
6 DORIGO M , BIRATTARI M , STUTZLE T . Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2007, 1 (4): 28- 39.
7 NIU Qun , JIAO Bin , GU Xingsheng . Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time[J]. Applied Mathematics and Computation, 2008, 205 (1): 148- 158.
doi: 10.1016/j.amc.2008.05.086
8 DU Hui , LIU Dacheng , ZHANG Mianhao , et al. A hybrid algorithm based on particle swarm optimization and artificial immune for an assembly job shop scheduling problem[J]. Mathematical Problems in Engineering, 2016, 2016 (2): 1- 10.
9 AMIN J , MOHAMMAD A S , REZA T M . A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2011, 54 (1/4): 309- 322.
10 DONG Wenyong , KANG Lanlan , ZHANG Wensheng . Opposition-based particle swarm optimization with adaptive mutation strategy[J]. Soft Computing, 2017, 21 (17): 5081- 5090.
doi: 10.1007/s00500-016-2102-5
11 MAY B R . Simple mathematical models with very complicated dynamics[J]. Nature, 1976, 261 (5560): 459- 467.
doi: 10.1038/261459a0
12 WANG H , WU Z , RAHNAMAYAN S , et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181 (20): 4699- 4714.
doi: 10.1016/j.ins.2011.03.016
13 李荣雨, 王颖. 基于莱维飞行的改进粒子群算法[J]. 系统仿真学报, 2017, 29 (8): 1685- 1691, 1701.
LI Rongyu , WANG Ying . Improved particle swarm optimization based on Lévy flights[J]. Journal of System Simulation, 2017, 29 (8): 1685- 1691, 1701.
14 姜天华. 猫群优化算法求解柔性作业车间调度问题[J]. 计算机工程与应用, 2018, 54 (23): 259- 263, 270.
doi: 10.3778/j.issn.1002-8331.1708-0297
JIANG Tianhua . Cat swarm optimization for solving flexible job shop scheduling problem[J]. Computer Engineering and Applications, 2018, 54 (23): 259- 263, 270.
doi: 10.3778/j.issn.1002-8331.1708-0297
15 RATNAWEERA A , HALGAMUGE S K , WATSON H C . Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J]. IEEE Transactions on Evolutionary Computation, 2004, 8 (3): 240- 255.
16 BEAN J . Genetic algorithms and random keys for sequencing and optimization[J]. Orsa Journal on Computing, 1994, 6 (2): 154- 160.
doi: 10.1287/ijoc.6.2.154
17 张飞, 耿红琴. 基于混沌粒子群算法的车间作业调度优化[J]. 山东大学学报(工学版), 2013, 43 (3): 19- 22, 37.
ZHANG Fei , GENG Hongqin . Optimization of job shop scheduling problem based on chaos particle swarm optimization algorithm[J]. Journal of Shandong University(Engineering Science), 2013, 43 (3): 19- 22, 37.
18 ELGOHARY A , ALRUZAIZA A S . Chaos and adaptive control in two prey, one predator system with nonlinear feedback[J]. Chaos Solitons & Fractals, 2007, 34 (2): 443- 453.
19 OUYANG X , ZHOU Y , LUO Q , et al. A novel discrete cuckoo search algorithm for spherical traveling salesman problem[J]. Applied Mathematics & Information Sciences, 2013, 7 (2): 777- 784.
20 YANG X S , KARAMANOGLU M , HE X . Flower pollination algorithm: a novel approach for multiobjective optimization[J]. Engineering Optimization, 2014, 46 (9): 1222- 1237.
doi: 10.1080/0305215X.2013.832237
21 HANSEN P , MLADENOVIC N . Variable neighborhood search: principles and applications[J]. European Journal of Operational Research, 2001, 130 (3): 449- 467.
doi: 10.1016/S0377-2217(00)00100-4
22 潘全科, 王文宏, 朱剑英, 等. 基于粒子群优化和变邻域搜索的混合调度算法[J]. 计算机集成制造系统, 2007, 13 (2): 323- 328.
doi: 10.3969/j.issn.1006-5911.2007.02.019
PAN Quanke , WANG Wenhong , ZHU Jianying , et al. Hybrid heuristics based on particle swarm optimization and variable neighborhood search for job shop scheduling[J]. Computer Integrated Manufacturing Systems, 2007, 13 (2): 323- 328.
doi: 10.3969/j.issn.1006-5911.2007.02.019
23 钱晓雯. 求解作业车间调度问题的变邻域动态烟花算法[J]. 实验室研究与探索, 2018, 37 (1): 19- 21, 124.
doi: 10.3969/j.issn.1006-7167.2018.01.006
QIAN Xiaowen . Dynamic fireworks algorithm based on variable neighborhood search for job shop scheduling problem[J]. Research and Exploration in Laboratory, 2018, 37 (1): 19- 21, 124.
doi: 10.3969/j.issn.1006-7167.2018.01.006
24 姚远远, 叶春明. 求解作业车间调度问题的改进混合灰狼优化算法[J]. 计算机应用研究, 2018, 35 (5): 1310- 1314.
doi: 10.3969/j.issn.1001-3695.2018.05.007
YAO Yuanyuan , YE Chunming . Solving job shop scheduling problem using improved hybrid grey wolf optimizer[J]. Application Research of Computers, 2018, 35 (5): 1310- 1314.
doi: 10.3969/j.issn.1001-3695.2018.05.007
25 BEASLEY J E. OR-Library[DB/OL]. (2004-09-07)[2018-10-24]. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt.
[1] Meng LIU,Taoyang XU,Changgang LI,Yue WU,Zhi WANG,Fangfang SHI,Jianjun SU,Guohui ZHANG,Kuan LI. Optimization of emergency load shedding of receiving-end power grid based on Particle Swarm Optimization [J]. Journal of Shandong University(Engineering Science), 2019, 49(1): 120-128.
[2] Dongxiao WANG. Two methods for sliding mode synchronization of five-dimensional fractional-order chaotic systems with entanglement iterms [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 85-90.
[3] MAO Beixing. Ratio integral sliding mode synchronization control of entanglement chaotic systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(4): 50-54.
[4] MENG Xiaoling, WANG Jianjun. Chaos synchronization of a class of fractional-order coronary artery systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(4): 55-60.
[5] MAO Beixing, CHENG Chunrui. Self-adaptive sliding mode control of fractional-order Victor-Carmen chaotic systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 31-36.
[6] LI Qingbin, WANG Xiaodong. Terminal sliding model control chaos synchronization of fractional-order emotion mode systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 84-88.
[7] MAO Beixing, WANG Dongxiao. Sliding model chaos synchronization control of a class of fractional-order multi-scroll systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 79-83.
[8] YI Yunfei, MIAO Jian, LIN Guolong, YIN Zhi. Particle network optimization algorithm based on Newtonian mechanics and game theory model [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 28-36.
[9] FAN Debin, DENG Changshou, YUAN Sihao, TAN Xujie, DONG Xiaogang. Distributed particle swarm optimization algorithm based on mapreduce [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(6): 23-30.
[10] LIU Zhijun. Color image encryption algorithm based on complex chaos and affine transform [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 1-8.
[11] SUN Meimei, HU Yun'an, WEI Jianming. Synchronization of multiwing hyperchaotic systems via adaptive sliding mode control [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(6): 45-51.
[12] DONG Hongbin, ZHANG Guangjiang, PANG Jinwei, HAN Qilong. A clustering ensemble algorithm based on co-evolution [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 1-9.
[13] WANG Huifang, ZHAO Zhicheng, ZHANG Jinggang. Design of a fractional order IMC-IDμ controller for high order systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 77-82.
[14] ZHANG Junpeng, ZHANG Qingfan, YANG Hongjuan. Images tamper detection and recovery based on block features and chaotic sequence [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 63-69.
[15] HUA Jingxin, BO Yuming, CHEN Zhimin. Forecasting of real estate market based on particle swarm optimized neural network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(4): 22-30.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] QIN Tong, SUN Fengrong*, WANG Limei, WANG Qinghao, LI Xincai. 3D surface reconstruction using the shape based interpolation guided by maximal discs[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 1 -5 .
[2] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[3] XIA Bin,ZHANG Lian-jun . Energy comparison-based TOA estimation algorithm for the DS-CDMA UWB system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(1): 70 -73 .
[4] BO De-Yun, ZHANG Dao-Jiang. Adaptive spectral clustering algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 22 -26 .
[5] LI Shan-ping,ZHAO Yu-xiao,QIAO Peng,FENG Zheng-zhi . Cultivation of aerobic granular sludge and the kinetics of substrate degradation and biomass growth[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 95 -98 .
[6] ZHAO Ke-Jun, WANG Xin-Jun, LIU Xiang, CHOU Yi-Hong. Algorithms of continuous top-k join query over structured overlay networks[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 32 -37 .
[7] LI Xin-Ping, DAI Yi-Fei, HU Jing. Fluid-solid coupling analysis of surrounding rock mass stability and water inflow forecast of a tunnel in a karst zone[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(4): 1 -6 .
[8] DING Wan-Tao, LI Shu-Cai, ZHANG Qing-Song. Discussion on interface error regularity of inclined  stratum predicted by TSP[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(4): 57 -60 .
[9] WANG Bai-wei,CAO Sheng-le . A mult-objective assessment method of the effects of industrial waste-water management[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 89 -92 .
[10] GAO Yang, ZHANG Qing-Song, YUAN Xiao-Shuai, XU Zhen-Hao, LIU Bin. Application of geological radar to geological forecast in karst tunnel[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(4): 82 -86 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd