An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times. (English) Zbl 1251.90155

Keskinturk, Timur; Yildirim, Mehmet B.; Barut, Mehmet

Comput. Oper. Res. 39, No. 6, 1225-1235 (2012).

Summary: This study introduces the problem of minimizing average relative percentage of imbalance (ARPI) with sequence-dependent setup times in a parallel-machine environment. A mathematical model that minimizes ARPI is proposed. Some heuristics, and two metaheuristics, an ant colony optimization algorithm and a genetic algorithm are developed and tested on various random data. The proposed ant colony optimization method outperforms heuristics and genetic algorithm. On the other hand, heuristics using the cumulative processing time obtain better results than heuristics using setup avoidance and a hybrid rule in assignment.

MSC:

90B35	Deterministic scheduling theory in operations research
90C59	Approximation methods and heuristics in mathematical programming
68T05	Learning and adaptive systems in artificial intelligence

Keywords:

load balancing; parallel-machine scheduling; sequence-dependent setups; ant colony optimization; genetic algorithm; heuristics

References:

[1]	Rajakumar, S.; Arunachalam, V. P.; Selladurai, V., Workflow balancing strategies in parallel machine scheduling, International Journal of Advanced Manufacturing Technology, 23, 366-374 (2004)
[2]	Rajakumar, S.; Arunachalam, V. P.; Selladurai, V., Workflow balancing in parallel machine scheduling with precedence constraints using genetic algorithm, Journal of Manufacturing Technology Management, 17, 2, 239-254 (2006)
[3]	Rajakumar, S.; Arunachalam, V. P.; Selladurai, V., Workflow balancing in parallel machine scheduling using genetic algorithm, International Journal of Advanced Manufacturing Technology, 33, 11-12, 1212-1221 (2007)
[4]	Aubry, A.; Rossi, A.; Espinouse, M. L.; Jacomino, M., Minimizing setup costs for parallel multi-purpose machines under load-balancing constraint, European Journal of Operations Research, 187, 1115-1125 (2008) · Zbl 1137.90477
[5]	Duman, E.; Yildirim, M. B.; Alkaya, A. F., Scheduling continuous aluminum casting lines, International Journal of Production Research, 46, 20, 5701-5718 (2008) · Zbl 1157.90413
[6]	Yildirim, M. B.; Duman, E.; Krishna, K.; Senniappan, K., Parallel machine scheduling with load balancing and sequence dependent setups, International Journal of Operations Research, 4, 1, 1-8 (2007) · Zbl 1143.90342
[7]	Chen, Z. L.; Powell, W. B., Exact algorithms for scheduling multiple families of jobs on parallel machines, Naval Research Logistics, 50, 823-840 (2003) · Zbl 1044.90033
[8]	Hillier, M. S.; Brandeau, M. L., Cost minimization and workload balancing in printed circuit board assembly, IIE Transactions, 33, 7, 547-557 (2001)
[9]	Allahverdi, A.; Gupta, J. N.D.; Aldowaisan, T., A review of scheduling research involving setup consideration, International Journal of Management Science, 27, 219-239 (1999)
[10]	Fowler, J. W.; Horng, S. M.; Cochran, J. K., A hybridized genetic algorithm to solve parallel machine scheduling problems with sequence dependent setups, International Journal of Industrial Engineering, 10, 3, 232-243 (2003)
[11]	Gascon, A.; Leachman, R. C., A dynamic programming solution to the dynamic, multi-item, single-machine scheduling problem, Operations Research, 36, 1, 50-56 (1998) · Zbl 0657.90045
[15]	Yalaoui, F.; Chu, C., An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times, IIE Transactions, 35, 2, 183-190 (2003)
[16]	Tahar, D. N.; Yalaoui, F.; Chu, C.; Amodeo, L., A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times, International Journal of Production Economics, 99, 1-2, 63-73 (2006)
[17]	Chen, J. F., Minimization of maximum tardiness on unrelated parallel machines with process restrictions and setups, International Journal of Advanced Manufacturing Technology, 29, 557-563 (2006)
[18]	Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics—Part B, 26, 1, 29-41 (1996)
[19]	Dorigo, M.; Gambardella, L. M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66 (1997)
[20]	Ip, W. H.; Li, Y.; Man, K. F.; Tang, K. S., Multi-product planning and scheduling using genetic algorithm approach, Computers & Industrial Engineering, 38, 2, 283-296 (2000)