IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v37y1991i12p1629-1639.html
   My bibliography  Save this article

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

Author

Listed:
  • Lei Lei

    (Graduate School of Management, Rutgers University, Newark, New Jersey 07102)

  • Tzyh-Jong Wang

    (Bell Communications Research, Piscataway, New Jersey 08855)

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.

Suggested Citation

  • Lei Lei & Tzyh-Jong Wang, 1991. "The Minimum Common-Cycle Algorithm for Cyclic Scheduling of Two Material Handling Hoists with Time Window Constraints," Management Science, INFORMS, vol. 37(12), pages 1629-1639, December.
    • Handle: RePEc:inm:ormnsc:v:37:y:1991:i:12:p:1629-1639
    DOI: 10.1287/mnsc.37.12.1629
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.37.12.1629
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.37.12.1629?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. SubaI, Corinne & Baptiste, Pierre & Niel, Eric, 2006. "Scheduling issues for environmentally responsible manufacturing: The case of hoist scheduling in an electroplating line," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 74-87, February.
    2. Selcuk Karabati & Panagiotis Kouvelis, 1996. "Cyclic scheduling in flow lines: Modeling observations, effective heuristics and a cycle time minimization procedure," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(2), pages 211-231, March.
    3. Crama, Yves, 1997. "Combinatorial optimization models for production scheduling in automated manufacturing systems," European Journal of Operational Research, Elsevier, vol. 99(1), pages 136-153, May.
    4. Paul, Henrik J. & Bierwirth, Christian & Kopfer, Herbert, 2007. "A heuristic scheduling procedure for multi-item hoist production lines," International Journal of Production Economics, Elsevier, vol. 105(1), pages 54-69, January.
    5. Jiyin Liu & Yun Jiang, 2005. "An Efficient Optimal Solution to the Two-Hoist No-Wait Cyclic Scheduling Problem," Operations Research, INFORMS, vol. 53(2), pages 313-327, April.
    6. Zhili Zhou & Ling Li, 2009. "A solution for cyclic scheduling of multi-hoists without overlapping," Annals of Operations Research, Springer, vol. 168(1), pages 5-21, April.
    7. Sheen, Gwo-Ji & Liao, Lu-Wen, 2007. "A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags," European Journal of Operational Research, Elsevier, vol. 181(1), pages 102-116, August.
    8. Janny M. Y. Leung & Guoqing Zhang & Xiaoguang Yang & Raymond Mak & Kokin Lam, 2004. "Optimal Cyclic Multi-Hoist Scheduling: A Mixed Integer Programming Approach," Operations Research, INFORMS, vol. 52(6), pages 965-976, December.
    9. Y N Sotskov & A Allahverdi & T-C Lai, 2004. "Flowshop scheduling problem to minimize total completion time with random and bounded processing times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(3), pages 277-286, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:37:y:1991:i:12:p:1629-1639. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.