IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i3p1091-1102.html
   My bibliography  Save this article

An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints

Author

Listed:
  • Wenda Zhang

    (Department of Industrial and Systems Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801)

  • Jason J. Sauppe

    (Department of Computer Science, University of Wisconsin–La Crosse, La Crosse, Wisconsin 54601)

  • Sheldon H. Jacobson

    (Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801)

Abstract

In this paper, we discuss the one-machine scheduling problem with release and delivery times with the minimum makespan objective. Both heuristics and branch-and-bound algorithms have been formulated for the problem. One such branch-and-bound algorithm solves the problem and a variation that requires a delay between the completion of one job and the start of another (delayed precedence constraints). This paper analyzes key components of this branch-and-bound algorithm and proposes an improved heuristic to be used in conjunction with a different search strategy. Computational experiments demonstrate that the modifications lead to substantial improvements in running time and number of iterations on the one-machine problem instances both with and without delayed precedence constraints.

Suggested Citation

  • Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2021. "An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1091-1102, July.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:3:p:1091-1102
    DOI: 10.1287/ijoc.2020.0988
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.0988
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2020.0988?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
    ---><---

    References listed on IDEAS

    as
    1. Carlier, Jacques, 1982. "The one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 42-47, September.
    2. E. C. Sewell & S. H. Jacobson, 2012. "A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 433-442, August.
    3. C. N. Potts, 1980. "Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times," Operations Research, INFORMS, vol. 28(6), pages 1436-1441, December.
    4. Graham McMahon & Michael Florian, 1975. "On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness," Operations Research, INFORMS, vol. 23(3), pages 475-482, June.
    5. David R. Morrison & Edward C. Sewell & Sheldon H. Jacobson, 2016. "Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams," INFORMS Journal on Computing, INFORMS, vol. 28(1), pages 67-82, February.
    6. Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    7. B. J. Lageweg & J. K. Lenstra & A. H. G. Rinnooy Kan, 1976. "Minimizing maximum lateness on one machine: computational experience and some applications," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 30(1), pages 25-41, March.
    8. Kenneth R. Baker & Zaw‐Sing Su, 1974. "Sequencing with due‐dates and early start times to minimize maximum tardiness," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 21(1), pages 171-176, March.
    9. Morrison, David R. & Sewell, Edward C. & Jacobson, Sheldon H., 2014. "An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset," European Journal of Operational Research, Elsevier, vol. 236(2), pages 403-409.
    10. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    11. Pan, Yunpeng & Shi, Leyuan, 2006. "Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 168(3), pages 1030-1039, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Reha Uzsoy & Chung‐Yee Lee & Louis A. Martin‐Vega, 1992. "Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(3), pages 369-388, April.
    2. Dauzere-Peres, Stephane, 1995. "A procedure for the one-machine sequencing problem with dependent jobs," European Journal of Operational Research, Elsevier, vol. 81(3), pages 579-589, March.
    3. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    4. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    5. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2023. "Results for the close-enough traveling salesman problem with a branch-and-bound algorithm," Computational Optimization and Applications, Springer, vol. 85(2), pages 369-407, June.
    6. Alexander A. Lazarev & Nikolay Pravdivets & Frank Werner, 2020. "On the Dual and Inverse Problems of Scheduling Jobs to Minimize the Maximum Penalty," Mathematics, MDPI, vol. 8(7), pages 1-15, July.
    7. Joao António Noivo & Helena Ramalhinho-Lourenço, 1998. "Solving two production scheduling problems with sequence-dependent set-up times," Economics Working Papers 338, Department of Economics and Business, Universitat Pompeu Fabra.
    8. Lancia, Giuseppe, 2000. "Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 120(2), pages 277-288, January.
    9. Ivens, Philip & Lambrecht, Marc, 1996. "Extending the shifting bottleneck procedure to real-life applications," European Journal of Operational Research, Elsevier, vol. 90(2), pages 252-268, April.
    10. Pan, Yunpeng & Shi, Leyuan, 2006. "Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 168(3), pages 1030-1039, February.
    11. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    12. David R. Morrison & Jason J. Sauppe & Wenda Zhang & Sheldon H. Jacobson & Edward C. Sewell, 2017. "Cyclic best first search: Using contours to guide branch‐and‐bound algorithms," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 64-82, February.
    13. Federico Alonso-Pecina & José Alberto Hernández & José Maria Sigarreta & Nodari Vakhania, 2020. "Fast Approximation for Scheduling One Machine," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    14. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    15. Egon Balas & Alkis Vazacopoulos, 1998. "Guided Local Search with Shifting Bottleneck for Job Shop Scheduling," Management Science, INFORMS, vol. 44(2), pages 262-275, February.
    16. Philip Kaminsky, 2003. "The effectiveness of the longest delivery time rule for the flow shop delivery time problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(3), pages 257-272, April.
    17. García-Villoria, Alberto & Corominas, Albert & Nadal, Adrià & Pastor, Rafael, 2018. "Solving the accessibility windows assembly line problem level 1 and variant 1 (AWALBP-L1-1) with precedence constraints," European Journal of Operational Research, Elsevier, vol. 271(3), pages 882-895.
    18. Li, Zixiang & Kucukkoc, Ibrahim & Zhang, Zikai, 2020. "Branch, bound and remember algorithm for two-sided assembly line balancing problem," European Journal of Operational Research, Elsevier, vol. 284(3), pages 896-905.
    19. Mukherjee, Saral & Chatterjee Ashis K, 2002. "Applying Machine Based Decomposition in 2-Machine Flow Shops," IIMA Working Papers WP2002-08-05, Indian Institute of Management Ahmedabad, Research and Publication Department.
    20. Imed Kacem, 2009. "Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 117-133, February.

    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:orijoc:v:33:y:2021:i:3:p:1091-1102. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.