Unrelated Parallel Machines Scheduling Problem Using an Ant Colony Optimization Approach

Authors: Y. K. Lin, H. T. Hsieh, F. Y. Hsieh

Abstract:

Total weighted tardiness is a measure of customer satisfaction. Minimizing it represents satisfying the general requirement of on-time delivery. In this research, we consider an ant colony optimization (ACO) algorithm to solve the problem of scheduling unrelated parallel machines to minimize total weighted tardiness. The problem is NP-hard in the strong sense. Computational results show that the proposed ACO algorithm is giving promising results compared to other existing algorithms.

Keywords: ant colony optimization, total weighted tardiness, unrelated parallel machines.

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

References:

[1] B. Alidaee, D. Rosa, "Scheduling parallel machines to minimize total weighted and unweighted tardiness," Comput Oper Res , vol. 24, pp. 775-788, August 1997.
[2] A. Bauer, B. Bullnheimer, R. F. Hartl, and C. Strauss, "An ant colony optimization approach for the single machine total tardiness problem, " Evolutionary Computation, CEC 99. Proceedings of the 1999 Congress on Evolutionary Computation. IEEE Press.
[3] J. Behnamian, M. Zandieh, and S. F. Ghomi, " Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm," Expert Syst Appl, vol. 36, pp. 9637-9644, August 2009.
[4] M. D. Besten, T. St├╝tzle, and D. Dorigo, "Ant colony optimization for the total weighted tardiness problem," Lecture Notes in Computer Science, pp. 611-620, 2000.
[5] D. Biskup, J. Herrmann, and J. N. D. Gupta, "Scheduling identical parallel machines to minimize total tardiness," Int J Prod Econ, vol. 115, pp. 134-142, September 2008.
[6] J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, and WeglarzJ, Scheduling computer and manufacturing process, Berlin, New York: Springer Verlag, 1996.
[7] P. Brucker, Scheduling Algorithm (4th ed.). Berlin: Springer Verlag, 2004.
[8] D. Cao, M. Chen, and G. Wan, "Parallel machine selection and job scheduling to minimize machine cost and job tardiness," Comput Oper Res, vol. 32, pp. 1995-2012, 2005.
[9] M. Dorigo, G. D. Caro, and L. M. Gambardella, "Ant algorithms for distributed discrete optimization," Artificial Life, vol. 5, pp. 137-172, Spring 1999.
[10] M. Dorig and T. St├╝tzle, Ant colony optimization. MIT Press, Cambridge, MA, 2004.
[11] M. Dorigo and T. St├╝tzle, "Ant colony optimization: overview and recent advances," Int Ser Oper Res Manage Sci, vol. 146, pp. 227-263, 2010.
[12] R. Graham, E. Lawler, J. Lenstra, and K. A. Rinnooy, "Optimization and approximation in deterministric sequencing and scheduling: A survey," Ann Discrete Math, vol. 5, pp. 287-326, 1979.
[13] O. Holthaus and C. Rajendran, " A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs," Journal of the Operational Research Society, vol. 56, pp. 947-953, August 2005.
[14] C. Koulamas, "Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem, " Naval Research Logistics, vol. 44, pp. 109-125, February 1997.
[15] J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Bricker, "Complexity of machine scheduling problems," Ann Discrete Math, vol. 1, pp. 343-362, 1977.
[16] C. J. Liao and H. C. Juan, "An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups," Computers and Operations Research, vol. 34, pp. 1899-1909, August 2007.
[17] C. F. Liaw, Y. K. Lin, C. Y. Cheng, and M. C. Chen, "Scheduling unrelated parallel machines to minimize total weighted tardiness, " Comput Oper Res, vol. 30, pp. 1777-1789, January 2003.
[18] Y. K. Lin, M. E. Pfund, and J. W. Fowler, "Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems," Comput Oper Res, vol. 38, pp. 901-916, June 2011.
[19] D. Merkle and M. Middendorf, "Ant colony optimization with global pheromone evaluation for scheduling a single machine, " Applied Intelligence, vol. 18, pp. 105-111, 2003.
[20] L. Mönch, "Heuristics to minimize total weighted tardiness of jobs on unrelated parallel machines," Proceedings of the 4th IEEE Conference on Automation Science and Engineering, 2008, pp. 572-577.
[21] L. Mönch and C. Almeder, "Ant colony optimization approaches for scheduling jobs with incompatible families on parallel batch machines," Dublin, Ireland, Multidisciplinary International Conference on Scheduling, Theory and Applications, 2009, pp. 105-114.
[22] S. S. Panwalkar, M. L. Smith, and C. P. Koulamas, "A heuristic for the single machine tardiness problem," Eur J Oper Res, vol. 70, pp.304-310, November 1993.
[23] M. Pfund, J. W. Fowler, and J. N. D. Gupta, "A survey of algorithm for single and multi-objective unrelated parallel-machine deterministic scheduling problems, " Journal of the Chinese Institute of Industrial Engineers vol. 21, pp. 230-241, 2004.
[24] C. N. Potts and L. N. Van Wassenhove, "A decomposition algorithm for the single machine total tardiness problem," Operations Research Letters, vol. 1, pp. 177-181, 1982.
[25] M. Pinedo, Scheduling Theory, Algorithms, and Systems, 3rd ed., Prentice Hall, 2008.
[26] S. S. Sankar, S. Ponnambalam, V. Rathinavel, and M. Visveshvaren, " Scheduling in parallel machine shop: an ant colony optimization approach," Industrial Technology, 2005, pp. 276-280. Hong Kong: IEEE.
[27] S. O. Shim and Y. D. Kim, "Scheduling on parallel identical machines to minimize total tardiness, " Eur J Oper Res, vol. 177, pp. 135-146, February 2007.
[28] N. R. Srinivasa Raghavan and M. Venkataramana, "Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization," Int J Adv Manuf Tech, vol. 41, pp. 986-996, May 2009.
[29] A. P. J. Vepsalainen and T. E. Morton, "Priority rules and lead time estimation for job shop scheduling with weighted tardiness costs, " Manage Sci, vol. 33, pp. 1035-1047, August 1987.
[30] K. C. Ying and C. J. Liao, "An ant colony system approach for scheduling problems, " Production Planning and Control: The Management of Operations, vol.14, pp. 68-75, November 2003.
[31] H. Zhou, Z. Li, and X. Wu, "Scheduling unrelated parallel machine to minimize total weighted tardiness using ant colony optimization, " Proceedings of the IEEE International Conference on Automation and Logistics, 2007, pp. 132-136