The problem of cyclic scheduling of two hoists is defined as follows. There are N+1 workstations, S0,S1,...,SN, and two identical hoists that move jobs between stations. Jobs are identical and each job has to visit all stations in the order that stations are numbered. It is assumed that the hoist traveling times between stations are given constants. Each station can hold one job at a time, and each job must remain at station Si for a period of at least ai and at most bi time units. Both ai and bi, i=2,...,N are given constants. Define mi, 0•i•N, to be a move of a job from Si to SiÅ+1. A cyclic schedule determines the order of N+1 moves, {mi, i=0,1,...,N}, an assignment of these moves to hoists, and the start time of the moves in a cycle. The problem is to find a cyclic schedule that minimizes the total time (the cycle time) to complete all the N+1 moves. Previous approaches toward solving cyclic hoist scheduling problems have been limited to single-hoist cases. This paper proposes a heuristic algorithm that finds schedules for systems with two hoists, and discuss an extension to the problem with more than two hoists. The algorithm uses a partitioning approach by which a system is partitioned into two sets of contiguous workstations and each hoist is assigned to a set. A sequence of alternative partitions is evaluated. For each partition, two single-hoist subproblems are formed and the optimal (minimal) cycle time for each subproblem is independently computed. The two optimal single-hoist schedules are then coupled and refined into a feasible two-hoist schedule with a common-cycle time for both hoists. The best of the generated schedules, that results in the minimum common-cycle time among the different partitions, is given as the final solution. Computational experience with both randomly generated problems and a benchmark problem arising from a real system is discussed.
