Mixed batch scheduling on identical machines

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

Journal of Scheduling, 2020, vol. 23, issue 4, No 5, 487-496

Abstract: Abstract This paper studies a new mixed batch scheduling problem that arises in vacuum heat treatment. A mixed batch machine can process at most a given number of jobs simultaneously. The processing time of a batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimize the makespan. We first prove that the problem on a single machine can be solved in polynomial time, while the problem on multiple identical machines is NP-hard. Then, we develop a pseudopolynomial time exact algorithm when the number of machines is fixed. Further, we analyze the worst-case performance ratio of a full batch longest processing time algorithm and design Algorithm LPT-Greedy with improved worst-case performance.

Keywords: Scheduling; Batch; Algorithm; Complexity; Worst-case performance ratio (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-019-00623-9 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:jsched:v:23:y:2020:i:4:d:10.1007_s10951-019-00623-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-019-00623-9

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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