This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Liu, J. Articles by Jiang, Y. Search for Related Content

An Efficient Optimal Solution to the Two-Hoist No-Wait Cyclic Scheduling Problem

Business School, Loughborough University, Loughborough, Leicestershire LE11 3TU, United Kingdom
Department of Industrial Engineering, Bilkent University, 06800 Bilkent, Ankara, Turkey
j.y.liu{at}lboro.ac.uk
jiangyun{at}bilkent.edu.tr

Hoist scheduling is a typical problem in the operation of electroplating systems. The cyclic scheduling policy is widely used in these systems in industry. Research on hoist scheduling has focused on the cyclic problem to minimize the cycle length. Most previous studies consider the single-hoist case. In practice, however, more than one hoist is often used in an electroplating line. This paper addresses the two-hoist, no-wait cyclic scheduling problem, in which the tank-processing times are constants and, upon completion of processing in a tank, the parts have to be moved to the next tank immediately. Based on the analysis of the problem properties, a polynomial algorithm is developed to obtain an optimal schedule. This algorithm first identifies a set of thresholds, which are special values of the cycle length, so that the feasibility property may change only at these thresholds. Feasibility checking is then carried out on each individual threshold in ascending order. The first feasible threshold found will be the optimal cycle length, and the corresponding feasible schedule is an optimal hoist schedule.

Subject classifications: production/scheduling: cyclic; two hoists; no-wait; noncrossing; manufacturing: automated electroplating systems; robotic cells.
History: Received February 2002; revision received November 2003; accepted December 2003.