Username   Password       Forgot your password?  Forgot your username? 


Improved NSGA-II for the Job-Shop Multi-Objective Scheduling Problem 

Volume 14, Number 5, May 2018, pp.891-898
DOI: 10.23940/ijpe.18.05.p7.891898

Xiaoyun Jiang and Yi Li

School of Economics and Management, Xiamen University of Technology, Xiamen, 361024, China

(Submitted on February 1, 2018; Revised on March 16, 2018; Accepted on April 27, 2018)


Job-shop scheduling is essential to advanced manufacturing and modern management. In light of the difficulty of obtaining the optimal solution using simple genetic algorithms in the process of solving multi-objective job-shop scheduling problems, with maximum customer satisfaction and minimum makespan in mind, we constructed a multi-objective job-shop scheduling model with factory capacity constraints and propose an improved NSGA-II algorithm. This algorithm not only uses an improved elitism strategy to dynamically update the elite solution set, but also enhances the Pareto sorting algorithm to make density computations more accurate, thereby ensuring population diversity. An example is given to verify that this algorithm can effectively enhance global search capabilities, save computing resources, and lead to a better optimal solution. Using this algorithm for job-shop scheduling optimization oriented towards multi-objective decision-making can provide corporate executives with a scientific quantitative basis for management and decision-making, thereby enhancing their companies’ competitiveness.


References: 24

      1. S. Chatterjee, K. Abhishek and S. S. Mahapatra, “NSGA-II Approach of Optimization to Study the Effects of Drilling Parameters in AISI-304 Stainless Steel,” Procedia Engineering, vol. 97, pp. 78-84, 2014
      2. K. Deb, “Multi-Objective Optimization Using Evolutionary Algorithms,” John Wiley & Sons, New York, 2001
      3. K. Deb, A. Pratap and S. Agarwal, “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, June 2002
      4. C. M. Fonseca and P. J. Fleming, “Genetic Algorithms f or Multiobjective Optimization: Formulation Discussion and Generalization,” in Proceedings of the International Conference on Genetic Algorithms, pp. 416-423, California, US, June 1993
      5. J. Gao, M. Gen, L. Sun and X. Zhao, “A Hybrid of Genetic Algorithm and Bottleneck Shifting for Multi-Objective Flexible Job Shop Scheduling Problems,” Computers and Industrial Engineering, vol. 53, no. 1, pp. 149-162, 2007
      6. J. Horn, N. Nafpliotis and D. E. Goldberg, “Multiobjective Optimization Using the Niched Pareto Genetic Algorithm,” in Proceedings of the International Conference on Evolutionary Computation, pp. 82-87, Piscataway, US, June 1994
      7. R. F. Huang, X.W. Luo and B. Ji, “Multi-Objective Optimization of a Mixed-flow Pump Impeller Using Modified NSGA-II Algorithm,” Science China Technological Sciences, vol. 58, no. 12, pp. 2122-2130, November 2015
      8. 8. X. Y. Jiang and W. C. Chen, “An Effective Approach for the Optimisation of Cutting Parameters”, International Journal of Computer Applications in Technology, Vol. 50, No. 3/4, pp. 180–185, December 2014 
      9. X. Y. Jiang and H. H. Wu, “Optimization of Setup Frequency for TOC Supply Chain Replenishment System with Capacity Constraints”, Neural Computing and Applications, vol. 23, no. 6, pp.1831-1838, November 2013
      10. V. Kaplanoğlu, “An Object-Oriented Approach for Multi-Objective Flexible Job-Shop Scheduling Problem,” Expert Systems with Applications, vol. 45, pp.71-84, November 2016
      11. J. Kennedy, “Encyclopedia of Machine Learning: Particle Swarm Optimization,” Springer US, New York, 2011
      12. A. Kurapati and S. Azarm, “Immune Network Simulation with Multiobjective Genetic Algorithms for Multidisciplinary Design Optimization,” Engineering Optimization, vol. 33, no. 2, pp. 245-260, March 2000
      13. M. Y. Liu and E. B. Chen, “An Improved Differential Evolution Algorithm for Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Windows”, Engineering Applications of Artificial Intelligence, vol. 23, no. 2, pp. 188-195, 2010
      14. A. Martínez-Vargas, J. Domínguez-Guerrero and A. G. Andrade, “Application of NSGA-II Algorithm to the Spectrum Assignment Problem in Spectrum Sharing Networks,” Applied Soft Computing, vol. 39, pp. 188-198, May 2016
      15. A. X. Ni, Y. F. Zhang and H. X. Chen, “An Improvement to NSGA-II Algorithm and Its Application in Optimization Design of Multi-element Airfoil,” Acta Aerodynamica Sinica, vol.32, no.2, pp. 252-257, June 2014
      16. R. Pérez-Rodríguez, S. Jöns and A. Hernández-Aguirre, “Simulation Optimization for a Flexible Jobshop Scheduling Problem Using an Estimation of Distribution Algorithm,” the International Journal of Advanced Manufacturing Technology, vol. 73, no.4, pp.3-21, September 2014
      17. M. Rohaninejad, A. Kheirkhah A and P. Fattahi, “A Hybrid Multi-Objective Genetic Algorithm Based on the ELECTRE Method for a Capacitated Flexible Job Shop Scheduling Problem,” the International Journal of Advanced Manufacturing Technology, vol. 77, no. 4, pp. 51-66, September 2015
      18. M. Sakawa and R. Kubota, “Fuzzy Programming for Multi-object Ive Job Shop Scheduling with Fuzzy Processing Time and Fuzzy Due Date through Genetic Algorithm”, European Journal of Operational Research, vol. 12, no. 2, pp. 393-407, June 2000
      19. J. D. Schaffer, “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms,” in Proceedings of the International Conference on Genetic Algorithms and their Applications, pp. 93-100, Pittsburgh, US, May 1985
      20. X. Shao, W. Liu and Q. Liu, “Hybrid Discrete Particle Swarm Optimization for Multi-Objective Flexible Job-Shop Scheduling Problem,” the International Journal of Advanced Manufacturing Technology, vol. 67, no. 9, pp. 2885-2901, 2013
      21. N. Srinivas and K. Deb, “Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms,” Evolutionary computation, vol.2, no.3, pp. 221-248, August 1994
      22. L. Wang, G. Zhou and Y. Xu, “An Enhanced Pareto-Based Artificial Bee Colony Algorithm for the Multi-Objective Flexible Job-Shop Scheduling,” the International Journal of Advanced Manufacturing Technology, vol. 60, no. 9, pp. 1111-1123, 2012
      23. 23. H. H. Wu and X.Y. Jiang, “Improved Genetic Algorithms for Optimization of Inventory Allocation in LED Chip Manufacturing Plants,” Journal of Interdisciplinary Mathematics, vol. 20, no. 3, pp. 727-738, August 2017 
      24. L. K. Zhang, “A Two-Stage Optimization Algorithm of NSGA2 Guided by the Improved Bee Evolutionary Genetic Algorithm and Its Application”, Hunan university, Hunan, 2016


          Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

          Download this file (IJPE-2018-05-07.pdf)IJPE-2018-05-07.pdf[Improved NSGA-II for the Job-Shop Multi-Objective Scheduling Problem]368 Kb
          This site uses encryption for transmitting your passwords.