×

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

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
PDF BibTeX XML Cite
Full Text: DOI Link

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
[12] Dietrich BL, Escudero LF. On solving a 0-1 model for workload allocation on parallel unrelated machines with setups. In: Proceedings of the third ORSA/TIMS conference on flexible manufacturing systems: operations research models and applications, 1989. p. 181-6.
[13] Pinedo M. Scheduling: theory, algorithms and systems. Springer series in operations research and financial engineering, 1995.
[14] Tamaki H, Hasegawa Y, Kozasa J, Araki M. Application of search methods to scheduling problem in plastics forming plant: a binary representation approach. In: Proceedings of the 32nd IEEE conference on decision and control, 1993. p. 3845-50.
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.