Cyclic hoist scheduling in large real-life electroplating lines. (English) Zbl 1173.90400

Summary: This paper addresses cyclic scheduling of a single hoist in large real-life electroplating lines, where a part visits some processing tanks more than once and multiple duplicate tanks are used at some production stages having long processing times. We present a formal analysis of the problem and propose an efficient branch-and-bound algorithm. The developed analytical properties allow us to considerably eliminate dominated or infeasible solutions in the branch-and-bound procedure. Computational results on benchmark and real-life instances show that the algorithm is very efficient in scheduling large electroplating lines.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Che, A.; Chu, C.; Chu, F., Multicyclic hoist scheduling with constant processing times, IEEE Trans Robot Autom, 18, 1, 69-80 (2002)
[2] Che, A.; Chu, C., A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line, Oper Res Lett, 33, 274-284 (2005) · Zbl 1140.90393
[3] Chen, H.; Chu, C.; Proth, JM, Cyclic scheduling of a hoist with time window constraints, IEEE Trans Robot Autom, 14, 1, 144-152 (1998)
[4] Crama, Y.; van de Klundert, J., Cyclic scheduling of identical parts in a robotic cell, Oper Res, 45, 6, 952-965 (1997) · Zbl 0895.90113
[5] Crama, Y.; Kats, V.; Van de Klundert, J.; Levner, E., Cyclic scheduling in robotic flowshops, Ann Oper Res, 96, 97-124 (2000) · Zbl 0997.90032
[6] Dawande, M.; Geismar, HN; Sethi, SP; Sriskandarajah, C., Sequencing and scheduling in robotic cells: recent developments, J Sched, 8, 5, 387-426 (2005) · Zbl 1123.90020
[7] Hall, NG; Nof, SY, Operations research techniques for robotic system planning, design, control and analysis, Handbook of Industrial Robotics, vol. II, ch. 30, 543-577 (1999), New York: John Wiley, New York
[8] Hall, NG; Kamoun, H.; Sriskandarajah, C., Scheduling in robotic cells: complexity and steady state analysis, Eur J Oper Res, 109, 43-65 (1998) · Zbl 0949.90041
[9] Hall, NG; Lee, TE; Posner, ME, The complexity of cyclic shop scheduling problems, J Sched, 5, 4, 307-327 (2002) · Zbl 1009.90048
[10] Ioachim, I.; Soumis, F., Schedule efficiency in a robotic production cell, Int J Flex Manuf Syst, 7, 5-26 (1995)
[11] Kamoun, H.; Hall, NG; Sriskandarajah, C., Scheduling in robotic cells: heuristic and cell design, Oper Res, 47, 821-835 (1999) · Zbl 1009.90049
[12] Kats, V.; Levner, E., Cyclic scheduling of operations for a part type in an FMS handled by a single robot: a parametric critical-path approach, Int J Flex Manuf Syst, 10, 129-138 (1998)
[13] Kim, JH; Lee, TE; Lee, HY; Park, DB, Scheduling analysis of time-constrained dual-armed cluster tools, IEEE Trans Semicond Manuf, 16, 3, 521-534 gdgd (2003)
[14] Lee, TE; Posner, ME, Performance measures and schedules in periodic job shops, Oper Res, 45, 1, 72-91 (1997) · Zbl 0892.90102
[15] Lee, TE, Stable earliest starting schedules for cyclic job shops: a linear system approach, Int J Flex Manuf Syst, 12, 59-80 (2000)
[16] Lee TE, Lee HY, Shin YH (2004) Workload balancing and scheduling of a single-armed cluster tool. In: Proceedings of the Fifth Asia Pacific Industrial Engineering and Management Systems (APIEMS) Conference, Gold Coast, Australia, pp 1-15
[17] Lee HY, Lee TE (2006) Scheduling single-armed cluster tools with reentrant wafer flows. IEEE Trans Semicond Manuf (in press)
[18] Lei L, Wang TJ (1989) A proof: the cyclic hoist scheduling problem is NP-hard. Working Paper #89-0016, Rutgers University
[19] Lei, L.; Wang, TJ, Determining optimal cyclic hoist schedules in a single-hoist electroplating line, IIE Trans, 26, 2, 25-33 (1994)
[20] Lim, JM, A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line, Comput Ind Eng, 33, 789-792 (1997)
[21] Liu, J.; Jiang, Y.; Zhou, Z., Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution, IIE Trans, 34, 905-914 (2002)
[22] Mak, RT; Gupta, SM; Lam, K., Modeling of material handling hoist operations in a PCB manufacturing facility, J Electron Manuf, 11, 1, 33-50 (2002)
[23] Manier MA (1994) Contribution à l’ordonnancement cyclique du système de manutention d’une ligne de galvanoplastie. Thèse de doctorat, Université de Franche-Comté, France
[24] Manier, MA; Bloch, C., A classification for hoist scheduling problems, Int J Flex Manuf Syst, 15, 1, 37-55 (2003)
[25] Matsuo, H.; Shang, JS; Sullivan, RS, A crane scheduling problem in a computer-integrated manufacturing environment, Manag Sci, 17, 587-606 (1991)
[26] McCormick, ST; Pinedo, ML; Shenker, S.; Wolf, B., Sequencing in an assembly line with blocking to minimize cycle time, Oper Res, 37, 925-935 (1989) · Zbl 0689.90048
[27] Ng, WC, A branch and bound algorithm for hoist scheduling of a circuit board production line, Int J Flex Manuf Syst, 8, 45-65 (1996)
[28] Perkinson, TL; Gyurcsik, RS; McLarty, PK, Single-wafer cluster tool performance: an analysis of the effects of redundant chambers and revisitation sequences on throughput, IEEE Trans Semicond Manuf, 9, 3, 384-400 (1996)
[29] Phillips, LW; Unger, PS, Mathematical programming solution of a hoist scheduling program, AIIE Trans, 8/2, 219-225 (1976)
[30] Sethi, SP; Sriskandarajah, C.; Sorger, G.; Blazewicz, J.; Kubiak, W., Sequencing of parts and robot moves in a robotic cell, Int J Flex Manuf Syst, 4, 331-358 (1992)
[31] Shapiro, GW; Nuttle, HW, Hoist scheduling for a PCB electroplating facility, IIE Trans, 20/2, 157-167 (1998)
[32] Sriskandarajah, C.; Hall, NG; Kamoun, H., Scheduling large robotic cells without buffers, Ann Oper Res, 76, 287-321 (1998) · Zbl 0895.90109
[33] Sun, T.; Lai, K.; Lam, K.; So, K., A study of heuristics for bidirectional multi-hoist production scheduling systems, Int J Prod Econ, 33, 207-214 (1994)
[34] Varnier, C.; Bachelu, A.; Baptiste, P., Resolution of the cyclic multi-hoists scheduling problem with overlapping partitions, INFOR Inf Syst Oper Res, 35, 4, 277-284 (1997) · Zbl 0894.90084
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.