IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v57y2006i3d10.1057_palgrave.jors.2601989.html
   My bibliography  Save this article

Minimizing sum of completion times on a single machine with sequence-dependent family setup times

Author

Listed:
  • S Karabatı

    (Koç University, Rumelifeneri Yolu)

  • C Akkan

    (Sabancı University, Orhanlı)

Abstract

This paper presents a branch-and-bound (B&B) algorithm for minimizing the sum of completion times in a single-machine scheduling setting with sequence-dependent family setup times. The main feature of the B&B algorithm is a new lower bounding scheme that is based on a network formulation of the problem. With extensive computational tests, we demonstrate that the B&B algorithm can solve problems with up to 60 jobs and 12 families, where setup and processing times are uniformly distributed in various combinations of the [1,50] and [1,100] ranges.

Suggested Citation

  • S Karabatı & C Akkan, 2006. "Minimizing sum of completion times on a single machine with sequence-dependent family setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 271-280, March.
    • Handle: RePEc:pal:jorsoc:v:57:y:2006:i:3:d:10.1057_palgrave.jors.2601989
    DOI: 10.1057/palgrave.jors.2601989
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2601989
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2601989?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. Clyde L. Monma & Chris N. Potts, 1989. "On the Complexity of Scheduling with Batch Setup Times," Operations Research, INFORMS, vol. 37(5), pages 798-804, October.
    2. H.A.J. Crauwels & A.M.A. Hariri & C.N. Potts & L.N. Van Wassenhove, 1998. "Branch and bound algorithms for single-machinescheduling with batch set-up times to minimizetotal weighted completion time," Annals of Operations Research, Springer, vol. 83(0), pages 59-76, October.
    3. N.D. Gupta, Jatinder, 1988. "Single facility scheduling with multiple job classes," European Journal of Operational Research, Elsevier, vol. 33(1), pages 42-45, January.
    4. Marshall L. Fisher, 1985. "An Applications Oriented Guide to Lagrangian Relaxation," Interfaces, INFORMS, vol. 15(2), pages 10-21, April.
    5. Scott Webster & Kenneth R. Baker, 1995. "Scheduling Groups of Jobs on a Single Machine," Operations Research, INFORMS, vol. 43(4), pages 692-703, August.
    6. H.A.J. Crauwels & C.N. Potts & L.N. Van Wassenhove, 1997. "Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time," Annals of Operations Research, Springer, vol. 70(0), pages 261-279, April.
    7. Steven Moss & Cheryl Dale & Glenn Brame, 2000. "Sequence-Dependent Scheduling at Baxter International," Interfaces, INFORMS, vol. 30(2), pages 70-80, April.
    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. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.

    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. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    2. Liaee, Mohammad Mehdi & Emmons, Hamilton, 1997. "Scheduling families of jobs with setup times," International Journal of Production Economics, Elsevier, vol. 51(3), pages 165-176, September.
    3. Hinder, Oliver & Mason, Andrew J., 2017. "A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness," European Journal of Operational Research, Elsevier, vol. 262(2), pages 411-423.
    4. Kramer, Arthur & Iori, Manuel & Lacomme, Philippe, 2021. "Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization," European Journal of Operational Research, Elsevier, vol. 289(3), pages 825-840.
    5. 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.
    6. Selvarajah, Esaignani & Steiner, George, 2006. "Batch scheduling in a two-level supply chain--a focus on the supplier," European Journal of Operational Research, Elsevier, vol. 173(1), pages 226-240, August.
    7. Grundel, Soesja & Çiftçi, Barış & Borm, Peter & Hamers, Herbert, 2013. "Family sequencing and cooperation," European Journal of Operational Research, Elsevier, vol. 226(3), pages 414-424.
    8. Schaller, Jeffrey, 2007. "Scheduling on a single machine with family setups to minimize total tardiness," International Journal of Production Economics, Elsevier, vol. 105(2), pages 329-344, February.
    9. Kenneth R. Baker, 1999. "Heuristic procedures for scheduling job families with setups and due dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(8), pages 978-991, December.
    10. 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.
    11. Gupta, Jatinder N. D. & Ho, Johnny C., 1996. "Scheduling with two job classes and setup times to minimize the number of tardy jobs," International Journal of Production Economics, Elsevier, vol. 42(3), pages 205-216, April.
    12. Dunstall, Simon & Wirth, Andrew, 2005. "A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines," European Journal of Operational Research, Elsevier, vol. 167(2), pages 283-296, December.
    13. Esaignani Selvarajah & George Steiner, 2009. "Approximation Algorithms for the Supplier's Supply Chain Scheduling Problem to Minimize Delivery and Inventory Holding Costs," Operations Research, INFORMS, vol. 57(2), pages 426-438, April.
    14. Zhi‐Long Chen & Warren B. Powell, 2003. "Exact algorithms for scheduling multiple families of jobs on parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 823-840, October.
    15. Carsten Jordan & Andreas Drexl, 1998. "Discrete Lotsizing and Scheduling by Batch Sequencing," Management Science, INFORMS, vol. 44(5), pages 698-713, May.
    16. Mazdeh, Mohammad Mahdavi & Sarhadi, Mansoor & Hindi, Khalil S., 2007. "A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs," European Journal of Operational Research, Elsevier, vol. 183(1), pages 74-86, November.
    17. Liji Shen & Lars Mönch & Udo Buscher, 2013. "An iterative approach for the serial batching problem with parallel machines and job families," Annals of Operations Research, Springer, vol. 206(1), pages 425-448, July.
    18. F Jin & J N D Gupta & S Song & C Wu, 2010. "Single machine scheduling with sequence-dependent family setups to minimize maximum lateness," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(7), pages 1181-1189, July.
    19. Amin-Naseri, Mohammad Reza & Beheshti-Nia, Mohammad Ali, 2009. "Hybrid flow shop scheduling with parallel batching," International Journal of Production Economics, Elsevier, vol. 117(1), pages 185-196, January.
    20. Hongyu He & Yanzhi Zhao & Xiaojun Ma & Zheng-Guo Lv & Ji-Bo Wang, 2023. "Branch-and-Bound and Heuristic Algorithms for Group Scheduling with Due-Date Assignment and Resource Allocation," Mathematics, MDPI, vol. 11(23), pages 1-14, November.

    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:pal:jorsoc:v:57:y:2006:i:3:d:10.1057_palgrave.jors.2601989. 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.palgrave-journals.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.