 Scheduling mixed batch machines with inclusive processing set restrictions and non-identical capacitiesJinwen Ou and Weidong Li European Journal of Operational Research, 2026, vol. 328, issue 2, 407-414 Abstract: A new batch scheduling problem, name mixed batch scheduling problem, is received attentions recently. In a mixed batch scheduling model, the processing time of a job batch H is defined as αmaxj∈H{pj}+(1−α)∑j∈Hpj, where α∈[0,1] is a constant. In other words, the processing time of a job batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. In this paper, we study the problem of scheduling mixed batch machines with non-identical capacities under inclusive processing set restrictions, where the objective is to minimize the makespan of finishing all the jobs. We present a fast approximation algorithm with a performance ratio of 4/3+α for the problem, which improves up the existing performance bounds in the literature. By providing a technical lemma, we are able to develop the first polynomial time approximation scheme (PTAS) for the problem. We also design linear-time approximation schemes for two important special cases of the problem. Keywords: Scheduling; Batch machine; Mixed batch; Approximation algorithm; Approximation scheme (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:328:y:2026:i:2:p:407-414 DOI: 10.1016/j.ejor.2025.07.012 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.