A Study on Cyclic Multiple Hoist Scheduling Problems

by
Yun Jiang
The Hong Kong University of Science and Technology

This talk presents cyclic hoist scheduling problems in electroplating lines. Electroplating is a necessary
process in producing printed circuit boards (PCBs). A number of computer controlled hoists mounted
on a common track are responsible for transferring PCBs between processing tanks in an electroplating
line. Scheduling the movement of these hoists is generally known as the Hoist Scheduling Problem (HSP).

This talk addresses a number of HSPs in cyclic production to minimize the cycle length.
We first study the single-hoist problem with processing time windows and two extended features. The
first extension is that each PCB can visit a processing tank more than once. The second is that more
than one identical tank may be used for one processing stage. These extensions are common in practical
electroplating lines and can increase the processing capacities of lines. We formulate the problem with
all these features as a mixed integer programming model. Numerical examples show that the model can
be solved to optimum within reasonable time.

Problems with multiple hoists involve additional difficulties. One difficulty comes from the restriction
on the relative positions of the hoists to avoid collision since hoists run on the same track. Transforming
the hoist non-collision requirement to some compact mathematical constraints, we formulate the problem
with process time windows as a mixed integer programming model. A numerical example shows that the
model is solvable for problems with small size.

At last, we address the no-wait version of multi-hoist problems in which the process times and part
transfer times are all fixed constants. An polynomial algorithm is developed to solve general multihoist
problem. For two-hoist version, we propose a more efficient algorithm with lower computational
complexity.