IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v21y2018i6d10.1007_s10951-018-0561-5.html
   My bibliography  Save this article

Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

Author

Listed:
  • Dominik Kress

    (University of Siegen)

  • Maksim Barketau

    (National Academy of Sciences of Belarus)

  • Erwin Pesch

    (University of Siegen
    HHL Leipzig)

Abstract

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an $$O(n\log n+nF)$$ O ( n log n + n F ) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.

Suggested Citation

  • Dominik Kress & Maksim Barketau & Erwin Pesch, 2018. "Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines," Journal of Scheduling, Springer, vol. 21(6), pages 595-606, December.
    • Handle: RePEc:spr:jsched:v:21:y:2018:i:6:d:10.1007_s10951-018-0561-5
    DOI: 10.1007/s10951-018-0561-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-018-0561-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-018-0561-5?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. Allahverdi, Ali, 2015. "The third comprehensive survey on scheduling problems with setup times/costs," European Journal of Operational Research, Elsevier, vol. 246(2), pages 345-378.
    2. 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.
    3. A.E. Gerodimos & C.A. Glass & C.N. Potts & T. Tautenhahn, 1999. "Scheduling multi‐operation jobs on a single machine," Annals of Operations Research, Springer, vol. 92(0), pages 87-105, January.
    4. 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.
    5. Jacek Błażewicz & Klaus H. Ecker & Erwin Pesch & Günter Schmidt & Jan Węglarz, 2007. "Handbook on Scheduling," International Handbooks on Information Systems, Springer, number 978-3-540-32220-7, November.
    6. 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.
    7. 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.
    8. Lu, L.F. & Yuan, J.J., 2007. "The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard," European Journal of Operational Research, Elsevier, vol. 177(2), pages 1302-1309, March.
    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. Eduardo Queiroga & Rian G. S. Pinheiro & Quentin Christ & Anand Subramanian & Artur A. Pessoa, 2021. "Iterated local search for single machine total weighted tardiness batch scheduling," Journal of Heuristics, Springer, vol. 27(3), pages 353-438, June.
    2. Shaojun Lu & Jun Pei & Xinbao Liu & Xiaofei Qian & Nenad Mladenovic & Panos M. Pardalos, 2020. "Less is more: variable neighborhood search for integrated production and assembly in smart manufacturing," Journal of Scheduling, Springer, vol. 23(6), pages 649-664, December.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Rossit, Daniel Alejandro & Tohmé, Fernando & Frutos, Mariano, 2018. "The Non-Permutation Flow-Shop scheduling problem: A literature review," Omega, Elsevier, vol. 77(C), pages 143-153.
    6. 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.
    7. Dominik Kress & David Müller & Jenny Nossack, 2019. "A worker constrained flexible job shop scheduling problem with sequence-dependent setup times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 179-217, March.
    8. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    9. 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.
    10. Dirk Briskorn & Konrad Stephan & Nils Boysen, 2022. "Minimizing the makespan on a single machine subject to modular setups," Journal of Scheduling, Springer, vol. 25(1), pages 125-137, February.
    11. Rauchecker, Gerhard & Schryen, Guido, 2019. "An exact branch-and-price algorithm for scheduling rescue units during disaster response," European Journal of Operational Research, Elsevier, vol. 272(1), pages 352-363.
    12. Mohammad Reza Hosseinzadeh & Mehdi Heydari & Mohammad Mahdavi Mazdeh, 2022. "Mathematical modeling and two metaheuristic algorithms for integrated process planning and group scheduling with sequence-dependent setup time," Operational Research, Springer, vol. 22(5), pages 5055-5105, November.
    13. Fátima Pilar & Eliana Costa e Silva & Ana Borges, 2023. "Optimizing Vehicle Repairs Scheduling Using Mixed Integer Linear Programming: A Case Study in the Portuguese Automobile Sector," Mathematics, MDPI, vol. 11(11), pages 1-23, June.
    14. Sheikh, Shaya & Komaki, G.M. & Kayvanfar, Vahid & Teymourian, Ehsan, 2019. "Multi-Stage assembly flow shop with setup time and release time," Operations Research Perspectives, Elsevier, vol. 6(C).
    15. Soares, Leonardo Cabral R. & Carvalho, Marco Antonio M., 2020. "Biased random-key genetic algorithm for scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 285(3), pages 955-964.
    16. Lele Zhang & Andrew Wirth, 2016. "Online Machine Scheduling with Family Setups," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(04), pages 1-16, August.
    17. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Nossack, Jenny & Pesch, Erwin, 2014. "Minimizing setup costs in a transfer line design problem with sequential operation processing," International Journal of Production Economics, Elsevier, vol. 151(C), pages 186-194.
    18. Yanıkoğlu, İhsan & Yavuz, Tonguc, 2022. "Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 301(3), pages 875-895.
    19. Jinwen Ou, 2020. "Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection," Journal of Scheduling, Springer, vol. 23(5), pages 525-538, October.
    20. Zhang, Zhe & Song, Xiaoling & Huang, Huijung & Zhou, Xiaoyang & Yin, Yong, 2022. "Logic-based Benders decomposition method for the seru scheduling problem with sequence-dependent setup time and DeJong’s learning effect," European Journal of Operational Research, Elsevier, vol. 297(3), pages 866-877.

    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:jsched:v:21:y:2018:i:6:d:10.1007_s10951-018-0561-5. 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.