Solving Flexible Job-Shop Scheduling Problem by Improved Chicken Swarm Optimization Algorithm

doi:10.16182/j.issn1004731x.joss.201707014

Abstract

Abstract: To solve the flexible job-shop scheduling problem (FJSP) more effectively, an improved chicken swarm optimization (ICSO) algorithm was proposed. A flexible job-shop scheduling model was established for the purpose of minimizing the machine makespan. The improved chicken swarm optimization algorithm was presented. Algorithm improved the update formula of chicks and combined the advantages of simulated annealing algorithm and dynamic inertia cosine weight strategy, which achieved an effective balance of global search and local exploration. According to simulating and testing four standard functions and a flexible job shop scheduling model and compared with particle swarm optimization (PSO) and chicken swarm optimization (CSO), makespan of the optimal value of ICSO is reduced by 12 and 7 respectively, and the mean value is reduced by 16.3 and 5.7, validating the effectiveness and the superiority of ICSO.

Key words: flexible job-shop scheduling, improved chicken swarm optimization algorithm, simulated annealing algorithm, dynamic inertia cosine

CLC Number:

TP391.9

Xu Shipeng, Wu Dinghui, Kong Fei, Ji Zhicheng. Solving Flexible Job-Shop Scheduling Problem by Improved Chicken Swarm Optimization Algorithm[J]. Journal of System Simulation, 2017, 29(7): 1497-1505.

References

[1] Jia S, Hu Z H.Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem[J]. Computers & Operations Research (S0305-0548), 2014, 47(9): 11-26.
[2] Brucker P, Schlie R.Job-shop scheduling with multi-purpose machines[J]. Computing (S0010-485X), 1990, 45(4): 369-375.
[3] Driss I, Mouss K N, Laggoun A.A new genetic algorithm for flexible job-shop scheduling problems[J]. Journal of Mechanical Science and Technology (S1738-494X), 2015, 29(3): 1273-1281.
[4] Thammano A, Phu-ang A. A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-Shop Scheduling Problem[J]. Procedia Computer Science (S1877-0509), 2013, 20(9): 96-101.
[5] Lalwani S, Kumar R, Gupta N.A Review on Particle Swarm Optimization variants and their applications to Multiple Sequence Alignment[J]. Journal of Applied Mathematics and Bioinformatics (S1792-6602), 2013, 3(2): 87-124.
[6] Dorigo M, Caro G, Gambardella L.Ant algorithms for discrete optimization[J]. Artificial life (S1064-5462), 1999, 5(2): 137-172.
[7] 李修琳, 鲁建厦, 柴国钟, 等. 混合蜂群算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2011, 17(7): 1495-1500.
(Li X L, Lu J S, Chai G Z, et al.Hybrid Bee Colony Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2011, 17(7): 1495-1500.)
[8] 陈成, 邢立宁. 求解柔性作业车间调度问题的遗传-蚁群算法[J]. 计算机集成制造系统, 2011, 17(3): 615-621.
(Chen C, Xing L N.Genetic Algorithm - Ant Colony Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2011, 17(3): 615-621.)
[9] Karthikeyan S, Asokan P, Nickolas S.A hybrid discrete firefly algorithm for multi-objective flexible job shop scheduling problem with limited resource constraints[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2014, 72(9/12): 1567-1579.
[10] Meng X, Liu Y, Gao X, et al.A New Bio-inspired Algorithm: Chicken Swarm Optimization [M]// Advances in Swarm Intelligence. Germany: Springer International Publishing, 2014: 86-94.
[11] Ho N B, Tay J C, Lai E M K. An effective architecture for learning and evolving flexible job-shop schedules[J]. European Journal of Operational Research (S0377-2217), 2007, 179(2): 316-333.
[12] 焦晓璇, 景博, 黄以锋, 等. 基于模拟退火离散粒子群算法的测试点优化[J]. 计算机应用, 2014, 34(6): 1649-1652.
(Jiao X X, Jing B, Huang Y F, et al.Optimization for test selection based on simulated annealing binary particle swarm optimization algorithm[J]. Journal of Computer Applications, 2014, 34(6): 1649-1652.)
[13] 陈贵敏, 贾建援, 韩琪. 粒子群优化算法的惯性权值递减策略研究[J]. 西安交通大学学报, 2006, 40(1): 53-56.
(Chen G M, Jia J Y, Han Q.Study on the Strategy of Decreasing Inertia Weight in Particle Swarm Optimization Algorithm[J]. Journal of Xi'an Jiaotong University, 2006, 40(1): 53-56.)
[14] 田旻. 基于Baldwin效应粒子群优化算法的研究 [D]. 西安: 西安电子科技大学, 2012.
(Tian M.Research on Particle Swarm Optimization Algorithm Based on Baldwin Effect [D]. Xi'an, China: Xi'an University of Electronic Science and Technology, 2012.)