Unrelated Parallel Machines Scheduling Problem Using an Ant Colony Optimization Approach
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.
[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
[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
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:64704", author = "Y. K. Lin and H. T. Hsieh and F. Y. Hsieh", title = "Unrelated Parallel Machines Scheduling Problem Using an Ant Colony Optimization Approach", 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.", volume = "6", number = "8", pages = "1794-6", }
