IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v49y2025i2d10.1007_s10878-025-01267-6.html
   My bibliography  Save this article

Multiple identical serial-batch machines scheduling with release dates and submodular rejection penalties

Author

Listed:
  • Zhichao Geng

    (Zhengzhou University)

  • Lingfa Lu

    (Zhengzhou University)

Abstract

In this paper we study a scheduling problem with release dates and submodular rejection penalties on multiple (parallel) identical serial-batch machines. For this problem, each machine processes jobs in batches, jobs in a common batch start and finish simultaneously, and the duration of a batch is equal to the sum of a setup time and the total processing time of jobs in it. Some jobs are accepted and processed on the machines, while the left jobs are rejected with penalty and the total rejection penalty is determined by a submodular function. The objective function to be minimized is the sum of the makespan of accepted jobs and the total rejection penalty. For the scenario of an arbitrary number of machines and submodular rejection penalties, we give a 2-approximation algorithm by which the objective function value of the obtained schedule is no more than twice that of the optimal schedule. For the scenario of a fixed number of machines and linear rejection penalties, we give a pseudo-polynomial-time dynamic programming exact algorithm and a fully polynomial-time approximation scheme.

Suggested Citation

  • Zhichao Geng & Lingfa Lu, 2025. "Multiple identical serial-batch machines scheduling with release dates and submodular rejection penalties," Journal of Combinatorial Optimization, Springer, vol. 49(2), pages 1-27, March.
    • Handle: RePEc:spr:jcomop:v:49:y:2025:i:2:d:10.1007_s10878-025-01267-6
    DOI: 10.1007/s10878-025-01267-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-025-01267-6
    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/s10878-025-01267-6?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. Hongye Zheng & Suogang Gao & Wen Liu & Weili Wu & Ding-Zhu Du & Bo Hou, 2022. "Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 343-353, August.
    2. Xianzhao Zhang & Dachuan Xu & Donglei Du & Chenchen Wu, 2018. "Approximation algorithms for precedence-constrained identical machine scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 35(1), pages 318-330, January.
    3. Xueling Zhong & Jinwen Ou, 2017. "Improved approximation algorithms for parallel machine scheduling with release dates and job rejection," 4OR, Springer, vol. 15(4), pages 387-406, December.
    4. Shabtay, Dvir, 2014. "The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost," European Journal of Operational Research, Elsevier, vol. 233(1), pages 64-74.
    5. Pei, Jun & Liu, Xinbao & Fan, Wenjuan & Pardalos, Panos M. & Lu, Shaojun, 2019. "A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers," Omega, Elsevier, vol. 82(C), pages 55-69.
    6. Philippe Baptiste, 2000. "Batching identical jobs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 52(3), pages 355-367, December.
    7. Cheng He & Chunqi Xu & Hao Lin, 2020. "Serial-batching scheduling with two agents to minimize makespan and maximum cost," Journal of Scheduling, Springer, vol. 23(5), pages 609-617, October.
    8. Peihai Liu & Xiwen Lu, 2020. "New approximation algorithms for machine scheduling with rejection on single and parallel machine," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 929-952, November.
    9. Liqi Zhang & Lingfa Lu, 2016. "Parallel-machine scheduling with release dates and rejection," 4OR, Springer, vol. 14(2), pages 165-172, June.
    10. Ou, Jinwen & Zhong, Xueling & Wang, Guoqing, 2015. "An improved heuristic for parallel machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 241(3), pages 653-661.
    11. Ren-Xia Chen & Shi-Sheng Li, 2020. "Minimizing maximum delivery completion time for order scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1044-1064, November.
    12. Shahvari, Omid & Logendran, Rasaratnam, 2018. "A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning effect," International Journal of Production Economics, Elsevier, vol. 195(C), pages 227-248.
    13. Zhang, Liqi & Lu, Lingfa & Yuan, Jinjiang, 2009. "Single machine scheduling with release dates and rejection," European Journal of Operational Research, Elsevier, vol. 198(3), pages 975-978, November.
    14. Geng, Zhichao & Yuan, Jinjiang & Yuan, Junling, 2018. "Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost," Applied Mathematics and Computation, Elsevier, vol. 332(C), pages 1-18.
    15. Scott Webster & Kenneth R. Baker, 1995. "Scheduling Groups of Jobs on a Single Machine," Operations Research, INFORMS, vol. 43(4), pages 692-703, August.
    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. Xiaofei Liu & Weidong Li & Yaoyu Zhu, 2021. "Single Machine Vector Scheduling with General Penalties," Mathematics, MDPI, vol. 9(16), pages 1-16, August.
    2. Xiaofei Liu & Man Xiao & Weidong Li & Yaoyu Zhu & Lei Ma, 2023. "Algorithms for single machine scheduling problem with release dates and submodular penalties," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-18, May.
    3. Xiaofei Liu & Weidong Li, 2020. "Approximation Algorithm for the Single Machine Scheduling Problem with Release Dates and Submodular Rejection Penalty," Mathematics, MDPI, vol. 8(1), pages 1-11, January.
    4. Ren-Xia Chen & Shi-Sheng Li, 2020. "Minimizing maximum delivery completion time for order scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1044-1064, November.
    5. Gur Mosheiov & Assaf Sarig & Vitaly Strusevich, 2020. "Minmax scheduling and due-window assignment with position-dependent processing times and job rejection," 4OR, Springer, vol. 18(4), pages 439-456, December.
    6. Peihai Liu & Xiwen Lu, 2020. "New approximation algorithms for machine scheduling with rejection on single and parallel machine," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 929-952, November.
    7. Lingfa Lu & Liqi Zhang, 2023. "Scheduling problems with rejection to minimize the k-th power of the makespan plus the total rejection cost," Journal of Combinatorial Optimization, Springer, vol. 46(1), pages 1-17, August.
    8. Guojun Hu & Pengxiang Pan & Suding Liu & Ping Yang & Runtao Xie, 2024. "The prize-collecting single machine scheduling with bounds and penalties," Journal of Combinatorial Optimization, Springer, vol. 48(2), pages 1-13, September.
    9. Zhong, Xueling & Fan, Jie & Ou, Jinwen, 2022. "Coordinated scheduling of the outsourcing, in-house production and distribution operations," European Journal of Operational Research, Elsevier, vol. 302(2), pages 427-437.
    10. 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.
    11. Mohamadreza Dabiri & Mehdi Yazdani & Bahman Naderi & Hassan Haleh, 2022. "Modeling and solution methods for hybrid flow shop scheduling problem with job rejection," Operational Research, Springer, vol. 22(3), pages 2721-2765, July.
    12. Xueling Zhong & Jinwen Ou, 2017. "Improved approximation algorithms for parallel machine scheduling with release dates and job rejection," 4OR, Springer, vol. 15(4), pages 387-406, December.
    13. Xiaofei Liu & Peiyin Xing & Weidong Li, 2020. "Approximation Algorithms for the Submodular Load Balancing with Submodular Penalties," Mathematics, MDPI, vol. 8(10), pages 1-12, October.
    14. Jun-Qiang Wang & Guo-Qiang Fan & Zhixin Liu, 2020. "Mixed batch scheduling on identical machines," Journal of Scheduling, Springer, vol. 23(4), pages 487-496, August.
    15. Ou, Jinwen & Lu, Lingfa & Zhong, Xueling, 2023. "Parallel-batch scheduling with rejection: Structural properties and approximation algorithms," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1017-1032.
    16. Wencheng Wang & Xiaofei Liu, 2021. "A Combinatorial 2-Approximation Algorithm for the Parallel-Machine Scheduling with Release Times and Submodular Penalties," Mathematics, MDPI, vol. 10(1), pages 1-10, December.
    17. Jinwen Ou & Xueling Zhong & Xiangtong Qi, 2016. "Scheduling parallel machines with inclusive processing set restrictions and job rejection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 667-681, December.
    18. Baruch Mor & Gur Mosheiov, 2021. "A note: flowshop scheduling with linear deterioration and job-rejection," 4OR, Springer, vol. 19(1), pages 103-111, March.
    19. Weidong Li & Qianna Cui, 2018. "Vector scheduling with rejection on a single machine," 4OR, Springer, vol. 16(1), pages 95-104, March.
    20. Xueling Zhong & Zhangming Pan & Dakui Jiang, 2017. "Scheduling with release times and rejection on two parallel machines," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 934-944, April.

    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:jcomop:v:49:y:2025:i:2:d:10.1007_s10878-025-01267-6. 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.