Jobs Scheduling and Worker Assignment Problem to Minimize Makespan using Ant Colony Optimization Metaheuristic

Authors: Mian Tahir Aftab, Muhammad Umer, Riaz Ahmad

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.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058337

References:

[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.