The Minimum Common-Cycle Algorithm for Cyclic Scheduling of Two Material Handling Hoists with Time Window Constraints
针对双天车循环调度问题，提出一种启发式算法，通过将系统划分为连续工作站并分别优化单天车周期，再耦合为可行双天车公共周期调度，适用于制造系统调度优化。
The problem of cyclic scheduling of two hoists is defined as follows. There are N + 1 workstations, S 0 , S 1 , …, S N , 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 S i , for a period of at least a i and at most b i time units. Both a i and b i , i = 2, …, N, are given constants. Define m i , 0 ≤ i ≤ N, to be a move of a job from S i to S i +1 . A cyclic schedule determines the order of N + 1 moves, m i , 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. In this paper, we propose 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.