An evolutionary approach for the design and scheduling of electroplating facilities. (English) Zbl 1140.90379

Summary: This paper tackles the Cyclic Hoists Scheduling Problem. This problem is often encountered in electroplating facilities when mass production is required. Then a repetitive sequence of moves is searched for the hoists. We more precisely deal with a global optimization problem that simultaneously considers the design and the scheduling of such production lines. It consists in studying systems integrating several transportation resources, called hoists, by minimizing the cycle time, while minimizing the number of hoists used. To achieve these goals, we use an evolutionary approach. The encoding of one solution is based on the representation of the empty moves of the hoists. To evaluate each individual, we propose a linear programming model. This one both verifies the satisfaction of constraints and provides the best cycle time for the considered number of hoists. This contribution describes a promising approach to solving a simple version of this problem, namely cyclic hoist scheduling, based on Evolutionary Algorithms (EAs), which is an optimization method inspired by biological evolution models. The issues of solution encoding and specialised genetic operators with a repair procedure of the infeasible solutions are discussed. Some results are presented with benchmark examples.


90B30 Production models
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming


Full Text: DOI


[1] Lei, L., Wang, T.-J.: A proof: the cyclic hoist scheduling problem is NP-complete. Working paper no. 89-16, Rutgers University (1989)
[2] Manier, M.-A., Bloch, C.: A classification for hoist scheduling problems. Int. J. Flex. Manuf. Syst. 15(1), 37–55 (2003) · doi:10.1023/A:1023952906934
[3] Grunder, O., Baptiste, P., Chappe, D.: The relationship between the physical layout of the work stations and the productivity of a saturated single-hoist production line. Int. J. Prod. Res. 35(8), 2189–2211 (1997) · Zbl 0934.90030 · doi:10.1080/002075497194804
[4] Lei, L., Wang, T.-J.: The minimum common cycle algorithm for cycle scheduling of two material handling hoists with time window constraints. Manage. Sci. 37(12), 1629–1639 (1991) · Zbl 0741.90036 · doi:10.1287/mnsc.37.12.1629
[5] Armstrong, R., Gu, S., Lei, L.: A greedy algorithm to determine the number of transporters in a cyclic electroplating process. IIE Trans. 28(5), 347–355 (1996) · doi:10.1080/07408179608966281
[6] Manier, M.-A., Varnier, C., Baptiste, P.: Constraint-based model for the cyclic multi-hoists scheduling problem. Prod. Plan. Control. 11(3), 244–257 (2000) · doi:10.1080/095372800232216
[7] Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution, Programs. Springer-Verlag (1992) · Zbl 0763.68054
[8] Goldberg, D.: Algorithmes Génétiques. Elaboration, Optimisation et Apprentissage Automatique. Addison Wesley (1994)
[9] Talbi, G.: Métaheuristiques pour l’optimisation combinatoire multi-objectif : état de l’art. Working paper (1999)
[10] Manier, M.-A., Lamrous, S.: Design and scheduling of electroplating facilities. In: Proceedings of the Conference IEEE International Conference on Service Systems and Service Management (ICSSSM’06), pp. 1114–1119 (2006) · Zbl 1140.90379
[11] Deb, K.: Multiobjective Optimization Using Evolutionary Algorithms. Hardcover (2001) · Zbl 0970.90091
[12] Lamrous, S., Manier, M.-A.: Diversification de populations pour un algorithme génétique appliqué à l’ordonnancement de lignes de traitement de surface. In: Proceedings of 1er workshop Métaheuristiques : Théorie et Applications (META’06) (2006)
[13] Phillips, L.W., Unger, P.S.: Mathematical programming solution of a hoist scheduling program. AIIE Trans. 8(2), 219–225 (1976)
[14] Manier-Lacoste, M.-A.: Contribution à l’ordonnancement cyclique du système de manutention d’une ligne de galvanoplastie. Ph.D. thesis. University of Franche-Comté, France (1994)
[15] Shapiro, G.W.: Hoist scheduling for a PCB electroplating facility. Ph.D. thesis for the degree of Master Science, graduate faculty of North Carolina State University (1985)
[16] Lim, J-M.: A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line. Comput. Ind. Eng. 33(3–4), 789–792 (1997) · doi:10.1016/S0360-8352(97)00254-4
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.