The Minimum Common-Cycle Algorithm for Cyclic Scheduling of Two Material Handling Hoists with Time Window Constraints

Lei Lei and Tzyh-Jong Wang
Additional contact information
Lei Lei: Graduate School of Management, Rutgers University, Newark, New Jersey 07102
Tzyh-Jong Wang: Bell Communications Research, Piscataway, New Jersey 08855

Management Science, 1991, vol. 37, issue 12, 1629-1639

Abstract: 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 \le i \le 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.

Keywords: cyclic scheduling; heuristic algorithms; hoists; time window constraints; problem partitioning (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.37.12.1629 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:37:y:1991:i:12:p:1629-1639

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().