Computer Science ›› 2018, Vol. 45 ›› Issue (4): 233-239.doi: 10.11896/j.issn.1002-137X.2018.04.039

Previous Articles     Next Articles

Study on Flexible Job-shop Scheduling Problem Based on Improved Discrete Particle Swarm Optimization Algorithm

DING Shu-yang, LI Bing and SHI Hong-bo   

  • Online:2018-04-15 Published:2018-05-11

Abstract: Flexible job-shop scheduling problem is an extension of the classical job-shop scheduling problem.The former is much closer to the practical production. Aiming at minimizing the maximum completion time,this paper proposed an improved discrete particle swarm optimization algorithm.The traditional particle swarm optimization algorithm is applicable to optimize the continuous models.As a combinatorial optimization problem with high complexity,FJSP is a typically discrete model.The proposed algorithm utilizes the load balancing mechanism for the machines to initiate the population,and introduces three operators into the procedure of updating the individuals’ status in the population.The three operators are respectively described as follows:the mutation based on the operation sequencing or the machine assignment,the precedence preserving order based crossover between current particle and the individual optimal,and rand-point preservation crossover between current particle and the global optimal.A particle is completely updated by using three operators sucessively.This method makes the population converge to the optimal solution very fast.The experimental results of benchmark instances show that the proposed algorithm can practically solve the flexible job-shop scheduling problem and search the near optimal solutions very fast.The proposed algorithm outperforms the other similar algorithms with respect to searching efficiency and convergence speed.

Key words: Job-shop scheduling,Discrete optimization problem,Flexibility,Particle swarm optimization

[1] BRANDIMARTE P.Routing and Scheduling in a Flexible JobShop by Tabu Search [J].Annals of Operations Research,1993,41(3):157-183.
[2] KACEM I,HAMMADI S,BORNE P.Approach by Localization and Multi-Objective Evolutionary Optimization for Flexible Job-Shop Scheduling Problems [J].IEEE Transactions on Systems,Man and Cybernetics,Part C(Applications and Reviews),2002,32(1):1-3.
[3] PEZZELLA F,MORGANTI G,CIASCHETTI G.A GeneticAlgorithm for the Flexible Job-Shop Scheduling Problem[J].Computers & Operations Research,2008,35(10):3202-3212.
[4] XING L N,CHEN Y W,WANG P,et al.A Knowledge-Based Ant Colony Optimization for Flexible Job Shop Scheduling Problems [J].Applied Soft Computing,2010,10(3):888-896.
[5] ZHANG G,GAO L,SHI Y,et al.An Effective Genetic Algorithm for the Flexible Job-Shop Scheduling Problem [J].Expert Systems with Application,2011,38(4):3563-3573.
[6] AL-HINAI N,ELMEKKAWY T Y.Robust and Stable Flexible Job Shop Scheduling with Random Machine Breakdowns Using a Hybrid Genetic Algorithm [J].International Journal of Production Economics,2011,132(2):279-291.
[7] WANG J,CHU K.An Application of Genetic Algorithms for the Flexible Job-Shop Scheduling Problem [J].International Journal of Advancements in Computing Technology,2012,4(3):271-278.
[8] YAZDANI M,AMIRI M,ZANDIEH M.Flexible Job-ShopScheduling with Parallel Variable Neighborhood Search Algorithm [J].Expert Systems with Application,2010,37(1):678-687.
[9] DEFERSHA F M,MINGYUAN C.A Parallel Genetic Algo-rithm for a Flexible Job-Shop Scheduling Problem with Sequence Dependent Setups [J].International Journal of Advanced Manufacturing Technology,2010,49(1/4):263-279.
[10] KENNEDY J,EBERHART R C.A Discrete Binary Version of the Particle Swarm Algorithm [C]∥IEEE International Confe-rence on Systems.2002:4104-4108.
[11] CEHN J,PAN Q K.A Discrete Particle Swarm Optimization Algorithm for Independent Task Scheduling Problem [J].Computer Engineering,2008,4(6):214-215,8.(in Chinese) 陈晶,潘全科.求解独立任务调度的离散粒子群优化算法[J].计算机工程,2008,4(6):214-215,8.
[12] COELLO C A C,PULIDO G T,LECHUGA M S.Handlingmultiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.
[13] MONTGOMERY D C.Design and Analysis of Experiments[M].New York:John Wiley & Sons,2008.
[14] TANG X X,HE W P,HE Y L,et al.Research and Implementation of Job Shop Scheduling System [J].Aeronautical Manufacturing Technology,2011(5):69-73.(in Chinese) 唐欣欣,何卫平,和延立,等.面向作业车间的调度系统研究与实现[J].航空制造技术,2011(5):69-73.
[15] ZIAEE M.A Heuristic Algorithm for Solving Flexible Job Shop Scheduling Problem [J].The International Journal of Advanced Manufacturing Technology,2014,1(1-4):519-528.
[16] WOJCIECH B,MARIUSZ U,MIECZYSLAW W.Parallel Hybrid Metaheuristics for the Flexible Job Shop Problem [J].Computers & Industrial Engineering,2010,9(2):323-333.
[17] ZHANG T N,HAN B,YU B,et al.Flexible Job Shop Scheduling Optimization with Production Capacity Constraints [J].System Engineering-Theory & Practice,2011,1(3):505-511.(in Chinese) 张铁男,韩兵,于渤,等.生产能力约束条件下的柔性作业车间调度优化[J].系统工程理论与实践,2011,1(3):505-511.

No related articles found!
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .