Coordinated order scheduling and outsourcing on dedicated parallel machines

Jinwen Ou, Weidong Li and Xueling Zhong

European Journal of Operational Research, 2026, vol. 329, issue 3, 798-807

Abstract: In this paper we investigate two order scheduling problems with bundled operations on m dedicated parallel machines when outsourcing is allowed. In the first problem, the objective is to minimize the makespan of the accepted jobs (orders) subject to the constraint that the total rejection (outsourcing) cost is no more than a budget. In the second problem, the objective is to minimize the makespan of accepted jobs plus the total rejection cost of rejected jobs. We show that the first problem cannot be approximated within a factor less than 2 in polynomial time, unless P = NP. For each of the two problems when m is fixed, we present a quasi-linear-time FPTAS (fully polynomial time approximation scheme). For the second problem when m=2, we develop a faster FPTAS by an interesting problem transformation and advanced rounding method.

Keywords: Order scheduling; Dedicated machines; Bundled operation; Approximation algorithm; FPTAS (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725006733
Full text for ScienceDirect subscribers only

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:eee:ejores:v:329:y:2026:i:3:p:798-807

DOI: 10.1016/j.ejor.2025.08.035

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
Bibliographic data for series maintained by Catherine Liu ().