Mixed batch scheduling with non-identical job sizes to minimize makespan

Guo-Qiang Fan (), Jun-Qiang Wang () and Zhixin Liu ()
Additional contact information
Guo-Qiang Fan: Xidian University
Jun-Qiang Wang: Northwestern Polytechnical University
Zhixin Liu: University of Michigan-Dearborn

OR Spectrum: Quantitative Approaches in Management, 2025, vol. 47, issue 1, No 4, 105-127

Abstract: Abstract This paper studies a mixed batch scheduling problem with non-identical job sizes to minimize the makespan. Multiple jobs can be processed simultaneously as a batch on a mixed batch machine as long as the total size of the jobs in the batch does not exceed the machine capacity. The processing time of a batch is the weighted sum of the maximum processing time and total processing time of the jobs in the batch. We show that the problem is strongly NP-hard even with a single machine, and analyze the worst-case performance ratio of the longest processing time first fit (LPTFF) algorithm. Furthermore, we present the longest processing time first fit greedy (LPTFFG) algorithm, and show that the worst-case performance ratio of algorithm LPTFFG is better than that of algorithm LPTFF. Computational experiments show that algorithm LPTFFG fits the case with a large number of machines, small job sizes, and small weight of the maximum processing time.

Keywords: Scheduling; Mixed batch; Algorithm; Complexity; Worst-case performance ratio (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00291-024-00770-2 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:orspec:v:47:y:2025:i:1:d:10.1007_s00291-024-00770-2

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-024-00770-2

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().