nach oben

OR Spectrum

Erschienen in:

01.07.2007 | Regular Article

Cyclic hoist scheduling in large real-life electroplating lines

verfasst von: Ada Che, Chengbin Chu

Erschienen in: OR Spectrum | Ausgabe 3/2007

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

Nächster Artikel Tabu search algorithm for flexible flow path design of unidirectional automated-guided vehicle systems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Che A, Chu C, Chu F (2002) Multicyclic hoist scheduling with constant processing times. IEEE Trans Robot Autom 18(1):69–80CrossRef

Che A, Chu C (2005) A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line. Oper Res Lett 33:274–284CrossRef

Chen H, Chu C, Proth JM (1998) Cyclic scheduling of a hoist with time window constraints. IEEE Trans Robot Autom 14(1):144–152CrossRef

Crama Y, van de Klundert J (1997) Cyclic scheduling of identical parts in a robotic cell. Oper Res 45(6):952–965

Crama Y, Kats V, Van de Klundert J, Levner E (2000) Cyclic scheduling in robotic flowshops. Ann Oper Res 96:97–124CrossRef

Dawande M, Geismar HN, Sethi SP, Sriskandarajah C (2005) Sequencing and scheduling in robotic cells: recent developments. J Sched 8(5):387–426CrossRef

Hall NG (1999) Operations research techniques for robotic system planning, design, control and analysis. In: Nof SY (ed) Handbook of Industrial Robotics, vol. II, ch. 30. John Wiley, New York, 543–577

Hall NG, Kamoun H, Sriskandarajah C (1998) Scheduling in robotic cells: complexity and steady state analysis. Eur J Oper Res 109:43–65CrossRef

Hall NG, Lee TE, Posner ME (2002) The complexity of cyclic shop scheduling problems. J Sched 5(4):307–327CrossRef

Ioachim I, Soumis F (1995) Schedule efficiency in a robotic production cell. Int J Flex Manuf Syst 7:5–26CrossRef

Kamoun H, Hall NG, Sriskandarajah C (1999) Scheduling in robotic cells: heuristic and cell design. Oper Res 47:821–835

Kats V, Levner E (1998) 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–138CrossRef

Kim JH, Lee TE, Lee HY, Park DB (2003) Scheduling analysis of time-constrained dual-armed cluster tools. IEEE Trans Semicond Manuf 16(3):521-534CrossRef

Lee TE, Posner ME (1997) Performance measures and schedules in periodic job shops. Oper Res 45(1):72–91

Lee TE (2000) Stable earliest starting schedules for cyclic job shops: a linear system approach. Int J Flex Manuf Syst 12:59–80CrossRef

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

Lee HY, Lee TE (2006) Scheduling single-armed cluster tools with reentrant wafer flows. IEEE Trans Semicond Manuf (in press)

Lei L, Wang TJ (1989) A proof: the cyclic hoist scheduling problem is NP-hard. Working Paper #89-0016, Rutgers University

Lei L, Wang TJ (1994) Determining optimal cyclic hoist schedules in a single-hoist electroplating line. IIE Trans 26(2):25–33

Lim JM (1997) A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line. Comput Ind Eng 33:789–792CrossRef

Liu J, Jiang Y, Zhou Z (2002) Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution. IIE Trans 34:905–914CrossRef

Mak RT, Gupta SM, Lam K (2002) Modeling of material handling hoist operations in a PCB manufacturing facility. J Electron Manuf 11(1):33–50CrossRef

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

Manier MA, Bloch C (2003) A classification for hoist scheduling problems. Int J Flex Manuf Syst 15(1):37–55CrossRef

Matsuo H, Shang JS, Sullivan RS (1991) A crane scheduling problem in a computer-integrated manufacturing environment. Manag Sci 17:587–606

McCormick ST, Pinedo ML, Shenker S, Wolf B (1989) Sequencing in an assembly line with blocking to minimize cycle time. Oper Res 37:925–935CrossRef

Ng WC (1996) A branch and bound algorithm for hoist scheduling of a circuit board production line. Int J Flex Manuf Syst 8:45–65CrossRef

Perkinson TL, Gyurcsik RS, McLarty PK (1996) 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–400CrossRef

Phillips LW, Unger PS (1976) Mathematical programming solution of a hoist scheduling program. AIIE Trans 8/2:219–225

Sethi SP, Sriskandarajah C, Sorger G, Blazewicz J, Kubiak W (1992) Sequencing of parts and robot moves in a robotic cell. Int J Flex Manuf Syst 4:331–358CrossRef

Shapiro GW, Nuttle HW (1998) Hoist scheduling for a PCB electroplating facility. IIE Trans 20/2:157–167

Sriskandarajah C, Hall NG, Kamoun H (1998) Scheduling large robotic cells without buffers. Ann Oper Res 76:287–321CrossRef

Sun T, Lai K, Lam K, So K (1994) A study of heuristics for bidirectional multi-hoist production scheduling systems. Int J Prod Econ 33:207–214CrossRef

Varnier C, Bachelu A, Baptiste P (1997) Resolution of the cyclic multi-hoists scheduling problem with overlapping partitions. INFOR Inf Syst Oper Res 35(4):277–284

Titel: Cyclic hoist scheduling in large real-life electroplating lines
verfasst von: Ada Che
Chengbin Chu
Publikationsdatum: 01.07.2007
Verlag: Springer-Verlag
Erschienen in: OR Spectrum / Ausgabe 3/2007
Print ISSN: 0171-6468
Elektronische ISSN: 1436-6304
DOI: https://doi.org/10.1007/s00291-006-0040-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 3/2007

Two very large-scale neighborhoods for single machine scheduling

Performance evaluation of photolithography cluster tools

Heavy traffic analysis of a single vehicle loop in an automated storage and retrieval system

Scheduling and control of automated manufacturing systems

An efficient GRASP algorithm for disassembly sequence planning

A novel timetabling algorithm for a furnace process for semiconductor fabrication with constrained waiting and frequency-based setups