Modified NSGA-II for a Bi-Objective Job Sequencing Problem

Susmita Bandyopadhyay

Department of Production Engineering, Jadavpur University, Kolkata, India.

DOI: 10.4236/iim.2012.46036                

Abstract

This paper proposes a better modified version of a well-known Multi-Objective Evolutionary Algorithm (MOEA) known as Non-dominated Sorting Genetic Algorithm-II (NSGA-II). The proposed algorithm contains a new mutation algorithm and has been applied on a bi-objective job sequencing problem. The objectives are the minimization of total weighted tardiness and the minimization of the deterioration cost. The results of the proposed algorithm have been compared with those of original NSGA-II. The comparison of the results shows that the modified NSGA-II performs better than the original NSGA-II.

Keywords

Job Sequencing; Multi-Objective Evolutionary Algorithm (MOEA); NSGA-II (Non-Dominated Sorting Genetic Algorithm-II); Tardiness; Deterioration Cost

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. J. Xia and Z. M. Wu, “An Effective Hybrid Optimization Approach for Multi-Objective Flexible Job-Shop Scheduling Problems,” Computers & Industrial Engineering, Vol. 48, No. 2, 2005, pp. 409-425. doi:10.1016/j.cie.2005.01.018
[2]	L.-N. Xing, Y.-W. Chen and K.-W. Yang, “Multi-Objective Flexible Job Shop Schedule: Design and Evaluation by Simulation Modeling,” Applied Soft Computing, Vol. 9, No. 1, 2009, pp. 362-376. doi:10.1016/j.asoc.2008.04.013
[3]	C. X. Miao, Y. Z. Zhang and Z. G. Cao, “Bounded Parallel-Batch Scheduling on Single and Multi Machines for Deteriorating Jobs,” Information Processing Letters, Vol. 111, No. 16, 2011, pp. 798-803. doi:10.1016/j.ipl.2011.05.018
[4]	J. Q. Li, Q. K. Pan and S. X. Xie, “An Effective Shuffled Frog-Leaping Algorithm for Multi-Objective Flexible Job Shop Scheduling Problems,” Applied Mathematics and Computation, Vol. 218, No. 18, 2012, pp. 9353-9371. doi:10.1016/j.amc.2012.03.018
[5]	G. H. Zhang, X. Y. Shao, P. G. Li and L. Gao, “An Effective Hybrid Particle Swarm Optimization Algorithm for Multi-Objective Flexible Job-Shop Scheduling Problem,” Computers & Industrial Engineering, Vol. 56, No. 4, 2009, pp. 1309-1318. doi:10.1016/j.cie.2008.07.021
[6]	J.-Q. Li, Q.-K. Pan and Y.-C. Liang, “An Effective Hybrid Tabu Search Algorithm for Multi-Objective Flexible Job-Shop Scheduling Problems,” Computers & Industrial Engineering, Vol. 59, No. 4, 2010, pp. 647-662. doi:10.1016/j.cie.2010.07.014
[7]	J. Gao, L. Y. Sun and M. Gen, “A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems,” Computers & Operations Research, Vol. 35, No. 9, 2008, pp. 2892-2907. doi:10.1016/j.cor.2007.01.001
[8]	A. Rahimi-Vahed and A. H. Mirzaei, “A Hybrid Multi-Objective Shuffled Frog-Leaping Algorithm for a Mixed-Model Assembly Line Sequencing Problem,” Computers & Industrial Engineering, Vol. 53, No. 4, 2007, pp. 642-666. doi:10.1016/j.cie.2007.06.007
[9]	A. R. Rahimi-Vahed, M. Rabbani, R. Tavakkoli-Moghaddam, S. A. Torabi and F. Jolai, “A Multi-Objective Scatter Search for a Mixed-Model Assembly Line Sequencing Problem,” Advanced Engineering Informatics, Vol. 21, No. 1, 2007, pp. 85-99. doi:10.1016/j.aei.2006.09.007
[10]	J. C. Tay and N. B. Ho, “Evolving Dispatching Rules Using Genetic Programming for Solving Multi-Objective Flexible Job-Shop Problems,” Computers & Industrial Engineering, Vol. 54, No. 3, 2008, pp. 453-473. doi:10.1016/j.cie.2007.08.008
[11]	D. Y. Sha and H.-H. Lin, “A Multi-Objective PSO for Job-Shop Scheduling Problems,” Expert Systems with Applications, Vol. 37, No. 2, 2010, pp. 1065-1070. doi:10.1016/j.eswa.2009.06.041
[12]	D. C. Mattfeld and C. Bierwirth, “An Efficient Genetic Algorithm for Job Shop Scheduling with Tardiness Objectives,” European Journal of Operational Research, Vol. 155, No. 3, 2004, pp. 616-630. doi:10.1016/S0377-2217(03)00016-X
[13]	T. K. Varadharajan and C. Rajendran, “A Multi-Objective Simulated-Annealing Algorithm for Scheduling in Flowshops to Minimize the Makespan and Total Flowtime of Jobs,” European Journal of Operational Research, Vol. 167, No. 3, 2005, pp. 772-795. doi:10.1016/j.ejor.2004.07.020
[14]	B. Yagmahan and M. M. Yenisey, “A Multi-Objective ant Colony System Algorithm for Flow Shop Scheduling Problem,” Expert Systems with Applications, Vol. 37, No. 2, 2010, pp. 1361-1368. doi:10.1016/j.eswa.2009.06.105
[15]	J. Behnamian, S. M. T. Fatemi Ghomi and M. Zandieh, “A Multi-Phase Covering Pareto-Optimal Front Method to Multi-Objective Scheduling in a Realistic Hybrid Flowshop Using a Hybrid Metaheuristic,” Expert Systems with Applications, Vol. 36, No. 8, 2009, pp. 11057-11069. doi:10.1016/j.eswa.2009.02.080
[16]	T.-C. Chiang, H.-C. Cheng and L.-C. Fu, “NNMA: An Effective Memetic Algorithm for Solving Multiobjective Permutation Flow Shop Scheduling Problems,” Expert Systems with Applications, Vol. 38, No. 5, 2011, pp. 5986-5999. doi:10.1016/j.eswa.2010.11.022
[17]	Z. Lian, “A United Search Particle Swarm Optimization Algorithm for Multiobjective Scheduling Problem,” Applied Mathematical Modelling, Vol. 34, No. 11, 2010, pp. 3518-3526. doi:10.1016/j.apm.2010.03.001
[18]	R. Tavakkoli-Moghaddam, A. Rahimi-Vahed and A. H. Mirzaei, “A Hybrid Multi-Objective Immune Algorithm for a Flow Shop Scheduling Problem with Bi-Objectives: Weighted Mean Completion Time and Weighted Mean Tardiness,” Information Sciences, Vol. 177, No. 22, 2007, pp. 5072-5090. doi:10.1016/j.ins.2007.06.001
[19]	M. M. Mazdeh, F. Zaerpour, A. Zareei and A. Hajinezhad, “Parallel Machines Scheduling to Minimize Job Tardiness and Machine Deteriorating Cost with Deteriorating Jobs,” Applied Mathematical Modelling, Vol. 34, No. 6, 2010, pp. 1498-1510. doi:10.1016/j.apm.2009.08.023
[20]	H. F. Lewis and S. A. Slotnick, “Multi-Period Job Selection: Planning Workloads to Maximize Profit,” Computers & Operations Research, Vol. 29, No. 8, 2002, pp. 1081-1098. doi:10.1016/S0305-0548(00)00105-2
[21]	K. R. Baker and B. Keller, “Solving the Single-Machine Sequencing Problem Using Integer Programming,” Computers & Industrial Engineering, Vol. 59, No. 4, 2010, pp. 730-735. doi:10.1016/j.cie.2010.07.028
[22]	L. Lin and H. Jia-Zhen, “Multi-Objective Flexible Job-Shop Scheduling Problem in Steel Tubes Production,” Systems Engineering—Theory & Practice, Vol. 29, No. 8, 2009, pp. 117-126.
[23]	B. Yagmahan and M. M. Yenisey, “Ant Colony Optimization for Multi-Objective Flow Shop Scheduling Problem,” Computers & Industrial Engineering, Vol. 54, No. 3, 2008, pp. 411-420. doi:10.1016/j.cie.2007.08.003
[24]	R.-H. Huang, “Multi-Objective Job-Shop Scheduling with Lot-Splitting Production,” International Journal of Production Economics, Vol. 124, No. 1, 2010, pp. 206-213. doi:10.1016/j.ijpe.2009.10.026
[25]	R. Zhang and C. Wu, “A Hybrid Immune Simulated Annealing Algorithm for the Job Shop Scheduling Problem,” Applied Soft Computing, Vol. 10, No. 1, 2010, pp. 79-89. doi:10.1016/j.asoc.2009.06.008
[26]	L. Wang, Q.-K. Pan, P. N. Suganthan, W.-H. Wang and Y.-M. Wang, “A Novel Hybrid Discrete Differential Evolution Algorithm for Blocking Flow Shop Scheduling Problems,” Computers & Operations Research, Vol. 37, No. 3, 2010, pp. 509-520. doi:10.1016/j.cor.2008.12.004
[27]	E. Moradi, S. M. T. Fatemi Ghomi and M. Zandieh, “Bi-Objective Optimization Research on Integrated Fixed Time Interval Preventive Maintenance and Production for Scheduling Flexible Job-Shop Problem,” Expert Systems with Applications, Vol. 38, No. 6, 2011, pp. 7169-7178. doi:10.1016/j.eswa.2010.12.043
[28]	K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computing, Vol. 6, No. 2, 2002, pp. 182-197. doi:10.1109/4235.996017
[29]	N. Lakashminarasimman, S. Baskar, A. Alphones and M. W. Iruthayarajan, “Multiobjective Mobile Antenna Location Identification Using Evolutionary Optimization Algorithm,” Second International conference on Computing, Communication and Networking Technologies, Chettinand, 29-31 July 2010, pp. 1-4. doi:10.1109/ICCCNT.2010.5591640
[30]	H. Ishibuchi, N. Tsukamoto and Y. Nojima, “Empirical Analysis of Using Weighted Sum Fitness Functions in NSGA-II for Many-Objective 0/1 Knapsack Problems,” UKSim 2009: 11th International Conference on Computer Modelling and Simulation, Cambridge, 25-27 March 2009, pp. 71-76.
[31]	A. Kumar, D. Sharma and K. Deb, “A Hybrid Multi-Objective Optimization Procedure Using PCX Based NSGA-II and Sequential Quadratic Programming,” IEEE Congress on Evolutionary Computation, 25-28 September, 2007, Singapore, pp. 3011-3018.
[32]	Y. Liu, C. Zhou and W. J. Ye, “A Fast Optimization Method of Using Nondominated Sorting Genetic Algorithm (NSGA-II) and 1-Nearest Neighbor (1 NN) Classifier for Numerical Model Calibration,” IEEE International Conference on Granular Computing, Beijing, 25-27 July 2005, pp. 544-549.
[33]	M. C. Wang, G. M. Dai, H. P. Hu and M. C. Wang, “Improved NSGA-II Algorithm for Optimization of Constrained Functions,” International Conference on Machine Vision and Human-machine Interface, TBD Kaifeng, 24-25 April 2010, pp. 673-675.
[34]	M. T. Jensen, “Reducing the Run-Time Complexity of Multiobjective EAs: The NSGA-II and Other Algorithms,” IEEE Transactions on Evolutionary Computation, Vol. 7, No. 5, 2003, pp. 503-515. doi:10.1109/TEVC.2003.817234
[35]	M. Sato, H. E. Aguirre and K. Tanaka, “Effects of δ-Similar Elimination and Controlled Elitism in the NSGA-II Multiobjective Evolutionary Algorithm,” IEEE Congress on Evolutionary Computation, Vancouver, 16-21 July 2006, pp. 1164-1171.
[36]	L. Yu, P. Wang and H. S. Zhu, “A Novel Diversity Preservation Strategy based on Ranking Integration for Solving Some Specific Multi-Objective Problems,” Ninth International Symposium on Distributed Computing and Applications to Business, Engineering and Science, Hong Kong, 10-12 August 2010, pp. 97-101. doi:10.1109/DCABES.2010.145
[37]	M. R. Mansour, A. C. Santos, J. B. London Jr., A. C. B. Delbem and N. G. Bretas, “Node-Depth Encoding and Evolutionary Algorithms Applied to Service Restoration in Distribution Systems,” IEEE Power and Energy Society General Meeting, Minneapolis, 25-29 July 2010, pp. 1-8.