A note: approximation algorithms for batch scheduling on shops with job rejection

Gur Mosheiov and Assaf Sarig ()
Additional contact information
Gur Mosheiov: The Hebrew University
Assaf Sarig: The Hebrew University

Operational Research, 2025, vol. 25, issue 2, No 25, 14 pages

Abstract: Abstract The most popular and cited model of batch scheduling was introduced and solved almost four decades ago. This pioneering model assumed a single machine, serial batching of unit-time jobs and batch-independent setup times. In the current note, we extend this setting by (i) allowing job-rejection, and (ii) considering flowshop and openshop. The objective function contains two cost components: sum of job completion times and total rejection cost. We introduce approximation algorithms for these problems, which are based on solving to optimality the relaxed versions (allowing non-integer batches) in the first stage, followed by rounding procedures to create integer batches. The results of our numerical tests verify that these efficient approximation algorithms produce very close-to-optimal schedules.

Keywords: Scheduling; Batching; Total completion time; Job-rejection; Flowshop; Openshop (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-025-00921-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:25:y:2025:i:2:d:10.1007_s12351-025-00921-5

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-025-00921-5

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().