Jobs Scheduling and Worker Assignment Problem to Minimize Makespan using Ant Colony Optimization Metaheuristic
This article proposes an Ant Colony Optimization
(ACO) metaheuristic to minimize total makespan for scheduling a set
of jobs and assign workers for uniformly related parallel machines.
An algorithm based on ACO has been developed and coded on a
computer program Matlab®, to solve this problem. The paper
explains various steps to apply Ant Colony approach to the problem
of minimizing makespan for the worker assignment & jobs
scheduling problem in a parallel machine model and is aimed at
evaluating the strength of ACO as compared to other conventional
approaches. One data set containing 100 problems (12 Jobs, 03
machines and 10 workers) which is available on internet, has been
taken and solved through this ACO algorithm. The results of our
ACO based algorithm has shown drastically improved results,
especially, in terms of negligible computational effort of CPU, to
reach the optimal solution. In our case, the time taken to solve all 100
problems is even lesser than the average time taken to solve one
problem in the data set by other conventional approaches like GA
algorithm and SPT-A/LMC heuristics.
[1] B. Chen, C. N. Potts, G. J. Woeginger, "A review of machine
scheduling: Complexity, algorithms and approximability", in: D. Z. Du,
P. M. Pardalos (Eds.), Handbook of Combinatorial Optimization,
Kluwer Academic Publishers, Dordrecht, 1998, pp. 21-169.
[2] T. C. E. Cheng, C. C. S. Sin, "A state-of-the-art review of parallelmachine
scheduling research", European Journal of Operational
Research, vol. 47, 1990, pp. 271-292.
[3] E. Mokotoff, "Parallel machine scheduling problems: A survey", Asia-
Pacific Journal of Operational Research, vol. 18, 2001, pp. 193-242.
[4] M. R. Garey and D. S. Johnson, Computers and Intractability: A guide
to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
[5] P-C. Hu, "Minimizing total tardiness for the worker assignment
scheduling problem in identical parallel-machine models", International
Journal of Advanced Manufacturing Technology, vol. 23(5-6), 2004, pp.
383-388.
[6] P-C. Hu, "Minimizing total flow time for the worker assignment
scheduling problem in the identical parallel-machine models",
International Journal of Advanced Manufacturing Technology, vol.
25(9-10), 2005, pp. 1046-1052.
[7] P-C. Hu, "Further study of minimizing total tardiness for the worker
assignment scheduling problem in the identical parallel machine
models", International Journal of Advanced Manufacturing Technology,
vol. 29, 2006, pp. 165-169.
[8] P-C. Hu, "Further study of minimizing total flow time for the worker
assignment scheduling problem in the identical parallel machine
models" International Journal of Advanced Manufacturing Technology,
vol. 29(7-8), 2006, pp. 753-757.
[9] I. A. Chaudhary and P. R. Drake, "Minimizing total tardiness for the
machine scheduling and worker assignment problems in identical
parallel machines using genetic algorithms", International Journal of
Advanced Manufacturing Technology, vol. 42, 2008, pp. 581-594.
[10] I. A. Chaudhary, "Minimizing flow time for the worker assignment
problem in identical parallel machine models using GA", International
Journal of Advanced Manufacturing Technology, 2009, DOI
10.1007/s00170-009-2323-1.
[11] I. A. Chaudhary, "Minimizing makespan for the worker assignment
problem in identical parallel machine models using GA", Proceedings of
the World Congress on Engineering 2010
Vol III WCE 2010, June 30 - July 2, 2010, London, U.K.
[12] P-C. Hu. Online research data set available at
http://sparc.nfu.edu.tw/~pchu/research_data.htm.
[13] Marco Dorigo and Krzysztof Socha, "An Introduction to Ant Colony
Optimization", Technical Report No. TR/IRIDIA/2006-010, April 2006,
Last revision: April 2007.
[14] Jun Zhang, Xiaomin Hu, X. Tan, J.H. Zhong and Q. Huang,
"Implementation of an Ant Colony Optimization technique for job shop
scheduling problem", 2006, The Institute of Measurement and Control
10.1191/0142331206tm165oa.
[15] Ahmad Rabbani Motlagh, "An Efficient Ant Colony Optimization
Algorithm for Multi-objective Flow Shop Scheduling Problem", World
Academy of Science, Engineering and Technology 75 2011.
[16] Benjamin Doerr, Frank Neumann, Dirk Sudholt and Carsten Witt, "On
the Influence of Pheromone Updates in ACO Algorithms", Technical
Report ISSN 1433-3325 January 2007.
[17] Christian Blum, "Review Ant colony optimization: Introduction and
recent trends", available online at www.sciencedirect.com.
[18] Frederic Villeneuve, "A Method for Concept and Technology
Exploration of Aerospace Architectures", School of Aerospace
Engineering, Georgia Institute of Technology, USA, August, 2007.
[1] B. Chen, C. N. Potts, G. J. Woeginger, "A review of machine
scheduling: Complexity, algorithms and approximability", in: D. Z. Du,
P. M. Pardalos (Eds.), Handbook of Combinatorial Optimization,
Kluwer Academic Publishers, Dordrecht, 1998, pp. 21-169.
[2] T. C. E. Cheng, C. C. S. Sin, "A state-of-the-art review of parallelmachine
scheduling research", European Journal of Operational
Research, vol. 47, 1990, pp. 271-292.
[3] E. Mokotoff, "Parallel machine scheduling problems: A survey", Asia-
Pacific Journal of Operational Research, vol. 18, 2001, pp. 193-242.
[4] M. R. Garey and D. S. Johnson, Computers and Intractability: A guide
to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
[5] P-C. Hu, "Minimizing total tardiness for the worker assignment
scheduling problem in identical parallel-machine models", International
Journal of Advanced Manufacturing Technology, vol. 23(5-6), 2004, pp.
383-388.
[6] P-C. Hu, "Minimizing total flow time for the worker assignment
scheduling problem in the identical parallel-machine models",
International Journal of Advanced Manufacturing Technology, vol.
25(9-10), 2005, pp. 1046-1052.
[7] P-C. Hu, "Further study of minimizing total tardiness for the worker
assignment scheduling problem in the identical parallel machine
models", International Journal of Advanced Manufacturing Technology,
vol. 29, 2006, pp. 165-169.
[8] P-C. Hu, "Further study of minimizing total flow time for the worker
assignment scheduling problem in the identical parallel machine
models" International Journal of Advanced Manufacturing Technology,
vol. 29(7-8), 2006, pp. 753-757.
[9] I. A. Chaudhary and P. R. Drake, "Minimizing total tardiness for the
machine scheduling and worker assignment problems in identical
parallel machines using genetic algorithms", International Journal of
Advanced Manufacturing Technology, vol. 42, 2008, pp. 581-594.
[10] I. A. Chaudhary, "Minimizing flow time for the worker assignment
problem in identical parallel machine models using GA", International
Journal of Advanced Manufacturing Technology, 2009, DOI
10.1007/s00170-009-2323-1.
[11] I. A. Chaudhary, "Minimizing makespan for the worker assignment
problem in identical parallel machine models using GA", Proceedings of
the World Congress on Engineering 2010
Vol III WCE 2010, June 30 - July 2, 2010, London, U.K.
[12] P-C. Hu. Online research data set available at
http://sparc.nfu.edu.tw/~pchu/research_data.htm.
[13] Marco Dorigo and Krzysztof Socha, "An Introduction to Ant Colony
Optimization", Technical Report No. TR/IRIDIA/2006-010, April 2006,
Last revision: April 2007.
[14] Jun Zhang, Xiaomin Hu, X. Tan, J.H. Zhong and Q. Huang,
"Implementation of an Ant Colony Optimization technique for job shop
scheduling problem", 2006, The Institute of Measurement and Control
10.1191/0142331206tm165oa.
[15] Ahmad Rabbani Motlagh, "An Efficient Ant Colony Optimization
Algorithm for Multi-objective Flow Shop Scheduling Problem", World
Academy of Science, Engineering and Technology 75 2011.
[16] Benjamin Doerr, Frank Neumann, Dirk Sudholt and Carsten Witt, "On
the Influence of Pheromone Updates in ACO Algorithms", Technical
Report ISSN 1433-3325 January 2007.
[17] Christian Blum, "Review Ant colony optimization: Introduction and
recent trends", available online at www.sciencedirect.com.
[18] Frederic Villeneuve, "A Method for Concept and Technology
Exploration of Aerospace Architectures", School of Aerospace
Engineering, Georgia Institute of Technology, USA, August, 2007.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:52141", author = "Mian Tahir Aftab and Muhammad Umer and Riaz Ahmad", title = "Jobs Scheduling and Worker Assignment Problem to Minimize Makespan using Ant Colony Optimization Metaheuristic", abstract = "This article proposes an Ant Colony Optimization
(ACO) metaheuristic to minimize total makespan for scheduling a set
of jobs and assign workers for uniformly related parallel machines.
An algorithm based on ACO has been developed and coded on a
computer program Matlab®, to solve this problem. The paper
explains various steps to apply Ant Colony approach to the problem
of minimizing makespan for the worker assignment & jobs
scheduling problem in a parallel machine model and is aimed at
evaluating the strength of ACO as compared to other conventional
approaches. One data set containing 100 problems (12 Jobs, 03
machines and 10 workers) which is available on internet, has been
taken and solved through this ACO algorithm. The results of our
ACO based algorithm has shown drastically improved results,
especially, in terms of negligible computational effort of CPU, to
reach the optimal solution. In our case, the time taken to solve all 100
problems is even lesser than the average time taken to solve one
problem in the data set by other conventional approaches like GA
algorithm and SPT-A/LMC heuristics.", keywords = "Ant Colony Optimization (ACO), Genetic
algorithms (GA), Makespan, SPT-A/LMC heuristic.", volume = "6", number = "12", pages = "2652-4", }
