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.