International Journal of Information Technology and Computer Science(IJITCS)

ISSN: 2074-9007 (Print), ISSN: 2074-9015 (Online)

Published By: MECS Press

IJITCS Vol.8, No.8, Aug. 2016

A Multi-objective Mathematical Model for Job Scheduling on Parallel Machines Using NSGA-II

Full Text (PDF, 667KB), PP.43-49

Views:69   Downloads:2


Shahram Saeidi

Index Terms

Parallel Machines Scheduling;Linear Programming;NSGA-II;MOPSO


In the current industrial world, Time and cost are two the most important concepts affecting whole our planning, activities and scheduling. Effective use of these factors, will lead to increasing performance and profit. Solving the parallel-machine problem is one of the basic and important problems in industrial and service delivery systems. In this paper, a new mathematical multi-objective linear programming model is proposed for scheduling the parallel machines to minimize the total make-span and total machines cost. The proposed model is implemented in Matlab using the NSGA-II approach and the results are compared with MOPSO approach. The computational results show the effectiveness and superiority of the proposed model.

Cite This Paper

Shahram Saeidi,"A Multi-objective Mathematical Model for Job Scheduling on Parallel Machines Using NSGA-II", International Journal of Information Technology and Computer Science(IJITCS), Vol.8, No.8, pp.43-49, 2016. DOI: 10.5815/ijitcs.2016.08.05


[1]J. Blazewicz, ,J.K. Lenstra, A.H. G. Kan,  Scheduling Subject to Resource Cconstraints: Classification and Complexity. Discrete Applied Mathematics, 1983, 5(1), 11-24.

[2]O. Seraj, R. Tavakkoli-Moghaddam,F. Jolai, A Fuzzy Multi-objective Tabu-search Method for a New bi-objective Open Shop Scheduling Problem. Paper presented at the Computers & Industrial Engineering, 2009. CIE 2009. International Conference on

[3]I. Kacem,S. Hammadi, P. Borne, Approach by Llocalization and Multiobjective Evolutionary Optimization for Flexible Job-shop Scheduling Problems. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions, 2009, 32(1), 1-13. 

[4]B. Naderi, M. Zandieh, S.M.T. Fatemi-Ghomi, S. Scheduling Sequence-dependent Setup Time Job Shops with Preventive Maintenance. The International Journal of Advanced Manufacturing Technology, 2009,43(1-2), 170-181.

[5]M. Calhoun, K.,R.F. Deckro,J.T. Moore, J.W. Chrissis, J.C. Van Hove, J. C.. Planning and Re-planning in Project and Production Scheduling. Omega, 2002, 30(3), 155-170. 

[6]V. Sels, ,J. Coelho, A. Manuel Dias, M. Vanhoucke, Hybrid Tabu Search and a Truncated Branch-and-bound for the Unrelated Parallel Machine Scheduling Problem. Computers & Operations Research, 2015, 53, 107-117. 

[7]B. Ak, E. Koc, . A Guide for Genetic Algorithm Based on Parallel Machine Scheduling and Flexible Job-Shop  

Scheduling. Procedia - Social and Behavioral Sciences, 2012, 62, 817-823.

[8]W. Teekeng, A. Thammano, Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems. Procedia Computer Science, 20102, 12, 122-128. 

[9]K. Kim, Y. Yun, J. Yoon, M. Gen, G. Yamazaki,  Hybrid Genetic Algorithm with Adaptive Abilities for Resource-constrained Multiple Project Scheduling. Computers in Industry, 2005, 56(2), 143-160. 

[10]C. Liu, A Hybrid Genetic Algorithm to Minimize Total Tardiness for Unrelated Parallel Machine Scheduling with Precedence Constraints. Mathematical Problems in Engineering, 2013, 11. 

[11]M. Gen, L.& Lin, L. Multiobjective Evolutionary Algorithm for Manufacturing Scheduling Problems: state-of-the-art survey. Journal of Intelligent Manufacturing, 2014, 25(5), 849-866. doi: 10.1007/s10845-013-0804-4

[12]M. Rostami, A. Ebrahimzadeh, M. Mahdavi, Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment, Computers and Industrial Engineering, 2015, 85, 206-215.

[13]S. Bandyopadhyay, R. Bhattacharya, Solving multi-objective parallel machine scheduling problem by a modified NSGA-II, Applied Mathematical Modeling, 2013, 37(10-11), 6718-6729.

[14]X. Li, L. Amdeo, F. Yalaoeui, H. Chehade, A Multi-objective Optimization Approach to Solve a Parallel Machines Scheduling Problem. Advances inArtifical Intelligence, 2010, Article ID 943050, 10 pages, 2010. doi:10.1155/2010/943050.

[15]R. Tavakkoli-Moghaddam, F. Taheri, M. Bazzazi, Multi0Objective Unrelated Parallel Machines Scheduling with Sequence-Dependant Setup Times and Precedence Constraints, IJE Transactions, 2008, 21 (3), 269-278.

[16]F. Baesler, C. Palma, Multi-objective parallel machine scheduling in the sawmill industry using memetic algorithms, The International Journal of Advance Manufacturing Technology, 2014, 74 (5), 757-768.

[17]Sh. Yin, K. Ling, W. Wu and Y. Chiang, Multi-objective unrelated parallel machine scheduling: a Tabu-enhanced iterated Pareto greedy algorithm, International Journal of Production Research, 2015, DOI: 10.1080/00207543.2015.1047981.

[18]Ch. Liu, W. Tsai, Multi-objective parallel machine scheduling problems by considering controllable processing times, Journal of the Operational Research Society, 2015, doi:10.1057/jors.2015.82.

[19]C.C. Coello, D.A.V. Veldhuizen, Lamont G.B. Evolutionary Algoorithms for solving Multi-Objective problems. Springer Scinece and Bussiness Media, 2013.