IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v159y2008i1p135-15910.1007-s10479-007-0283-0.html
   My bibliography  Save this article

A branch and bound method for the job-shop problem with sequence-dependent setup times

Author

Listed:
  • Christian Artigues
  • Dominique Feillet

Abstract

This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds. Copyright Springer Science+Business Media, LLC 2008

Suggested Citation

  • Christian Artigues & Dominique Feillet, 2008. "A branch and bound method for the job-shop problem with sequence-dependent setup times," Annals of Operations Research, Springer, vol. 159(1), pages 135-159, March.
    • Handle: RePEc:spr:annopr:v:159:y:2008:i:1:p:135-159:10.1007/s10479-007-0283-0
    DOI: 10.1007/s10479-007-0283-0
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-007-0283-0
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-007-0283-0?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Filippo Focacci & Andrea Lodi & Michela Milano, 2002. "A Hybrid Exact Algorithm for the TSPTW," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 403-417, November.
    2. Jon K. Wilbrecht & William B. Prescott, 1969. "The Influence of Setup Time on Job Shop Performance," Management Science, INFORMS, vol. 16(4), pages 274-280, December.
    3. Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
    4. 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.
    5. J. Carlier & E. Pinson, 1989. "An Algorithm for Solving the Job-Shop Problem," Management Science, INFORMS, vol. 35(2), pages 164-176, February.
    6. Carlier, Jacques, 1982. "The one-machine sequencing problem," European Journal of Operational Research, Elsevier, vol. 11(1), pages 42-47, September.
    7. Eugeniusz Nowicki & Czeslaw Smutnicki, 1996. "A Fast Taboo Search Algorithm for the Job Shop Problem," Management Science, INFORMS, vol. 42(6), pages 797-813, June.
    8. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
    9. R. J. M. Vaessens & E. H. L. Aarts & J. K. Lenstra, 1996. "Job Shop Scheduling by Local Search," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 302-317, August.
    10. In-Chan Choi & Osman Korkmaz, 1997. "Job shop scheduling with separable sequence-dependent setups," Annals of Operations Research, Springer, vol. 70(0), pages 155-170, April.
    11. 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.
    12. 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.
    13. Sophie Demassey & Christian Artigues & Philippe Michelon, 2005. "Constraint-Propagation-Based Cutting Planes: An Application to the Resource-Constrained Project Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 52-65, February.
    14. Egon Balas & Neil Simonetti, 2001. "Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study," INFORMS Journal on Computing, INFORMS, vol. 13(1), pages 56-75, February.
    15. 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.
    16. Christian Artigues & Pierre Lopez & Pierre-Dimitri Ayache, 2005. "Schedule Generation Schemes for the Job-Shop Problem with Sequence-Dependent Setup Times: Dominance Properties and Computational Analysis," Annals of Operations Research, Springer, vol. 138(1), pages 21-52, September.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Ansis Ozolins, 2020. "Bounded dynamic programming algorithm for the job shop problem with sequence dependent setup times," Operational Research, Springer, vol. 20(3), pages 1701-1728, September.
    2. Carlos Mencía & María Sierra & Ramiro Varela, 2013. "Depth-first heuristic search for the job shop scheduling problem," Annals of Operations Research, Springer, vol. 206(1), pages 265-296, July.
    3. Gaby Pinto & Yariv Ben-Dov & Gad Rabinowitz, 2013. "Formulating and solving a multi-mode resource-collaboration and constrained scheduling problem (MRCCSP)," Annals of Operations Research, Springer, vol. 206(1), pages 311-339, July.
    4. Velez, Sara & Dong, Yachao & Maravelias, Christos T., 2017. "Changeover formulations for discrete-time mixed-integer programming scheduling models," European Journal of Operational Research, Elsevier, vol. 260(3), pages 949-963.
    5. Sascha Cauwelaert & Cyrille Dejemeppe & Pierre Schaus, 2020. "An Efficient Filtering Algorithm for the Unary Resource Constraint with Transition Times and Optional Activities," Journal of Scheduling, Springer, vol. 23(4), pages 431-449, August.
    6. Dario Medić & Srećko Krile & Igor Jelaska & Rino Bošnjak, 2021. "Adriatic Sea Hub Ports Feeder Service Optimization Using Multi-Criteria Decision-Making Methods," Sustainability, MDPI, vol. 13(21), pages 1-12, November.
    7. Tomasz Gawroński, 2012. "Optimization of setup times in the furniture industry," Annals of Operations Research, Springer, vol. 201(1), pages 169-182, December.
    8. Amir Elalouf, 2014. "Fast approximation algorithms for routing problems with hop-wise constraints," Annals of Operations Research, Springer, vol. 222(1), pages 279-291, November.
    9. Zhe Liu & Shurong Li, 2022. "A numerical method for interval multi-objective mixed-integer optimal control problems based on quantum heuristic algorithm," Annals of Operations Research, Springer, vol. 311(2), pages 853-898, April.
    10. Diarmuid Grimes & Emmanuel Hebrard, 2015. "Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 268-284, May.

    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. 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.
    2. Kurowski, Krzysztof & Pecyna, Tomasz & Slysz, Mateusz & Różycki, Rafał & Waligóra, Grzegorz & Wȩglarz, Jan, 2023. "Application of quantum approximate optimization algorithm to job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 310(2), pages 518-528.
    3. F. Guerriero, 2008. "Hybrid Rollout Approaches for the Job Shop Scheduling Problem," Journal of Optimization Theory and Applications, Springer, vol. 139(2), pages 419-438, November.
    4. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    5. Pezzella, Ferdinando & Merelli, Emanuela, 2000. "A tabu search method guided by shifting bottleneck for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 120(2), pages 297-310, January.
    6. Francis Sourd & Wim Nuijten, 2000. "Multiple-Machine Lower Bounds for Shop-Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 341-352, November.
    7. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    8. 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.
    9. Ansis Ozolins, 2020. "Bounded dynamic programming algorithm for the job shop problem with sequence dependent setup times," Operational Research, Springer, vol. 20(3), pages 1701-1728, September.
    10. Rego, César & Duarte, Renato, 2009. "A filter-and-fan approach to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 650-662, May.
    11. Bürgy, Reinhard & Bülbül, Kerem, 2018. "The job shop scheduling problem with convex costs," European Journal of Operational Research, Elsevier, vol. 268(1), pages 82-100.
    12. Raúl Mencía & Carlos Mencía, 2021. "One-Machine Scheduling with Time-Dependent Capacity via Efficient Memetic Algorithms," Mathematics, MDPI, vol. 9(23), pages 1-24, November.
    13. Giuseppe Lancia & Franca Rinaldi & Paolo Serafini, 2011. "A time-indexed LP-based approach for min-sum job-shop problems," Annals of Operations Research, Springer, vol. 186(1), pages 175-198, June.
    14. El-Bouri, A. & Azizi, N. & Zolfaghari, S., 2007. "A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1894-1910, March.
    15. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    16. Tarantilis, C. D. & Kiranoudis, C. T., 2002. "A list-based threshold accepting method for job shop scheduling problems," International Journal of Production Economics, Elsevier, vol. 77(2), pages 159-171, May.
    17. Susana Fernandes & Helena Ramalhinho-Lourenço, 2007. "A simple optimised search heuristic for the job-shop scheduling problem," Economics Working Papers 1050, Department of Economics and Business, Universitat Pompeu Fabra.
    18. Raja Awais Liaqait & Shermeen Hamid & Salman Sagheer Warsi & Azfar Khalid, 2021. "A Critical Analysis of Job Shop Scheduling in Context of Industry 4.0," Sustainability, MDPI, vol. 13(14), pages 1-19, July.
    19. Murovec, Boštjan, 2015. "Job-shop local-search move evaluation without direct consideration of the criterion’s value," European Journal of Operational Research, Elsevier, vol. 241(2), pages 320-329.
    20. Murovec, Bostjan & Suhel, Peter, 2004. "A repairing technique for the local search of the job-shop problem," European Journal of Operational Research, Elsevier, vol. 153(1), pages 220-238, 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:spr:annopr:v:159:y:2008:i:1:p:135-159:10.1007/s10479-007-0283-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.