A study on cyclic hoist scheduling problems

This thesis studies 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 thesis 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.; We then study multi-hoist problems. Problems with multiple hoists involve additional difficulties. One difficulty comes from the new decisions on assigning hoists to tasks. The other comes from the restriction on the relative positions of the hoists to avoid collision between them. We study the no-wait version of the problems in which the processing time and part transfer times are all fixed constants. For the two-hoist problem, we develop a polynomial algorithm to solve it based on comprehensive analysis of the non-collision requirements.; For the no-wait multi-hoist scheduling problem with any number of hoists, we identify a group of assignment constraints for any given cycle length. The feasibility of the cycle length is determined by solving this group of constraints. A polynomial algorithm is then developed to search for the optimal cycle length and to construct an optimal schedule.; The last problem discussed in the thesis is the multi-hoist problem with processing time windows. The introduction of time windows makes the problem NP-complete. We transform the non-collision requirements to some compact mathematical constraints and develop a mixed integer programming model for this problem. A numerical example shows that the model is solvable for problems with small size.; Finally, we briefly discuss the extension of this study to other scheduling problems for further research. Two similar problems in container terminals with non-collision requirements are described.