Shared processor scheduling of multiprocessor jobs

Dariusz Dereniowski and Wiesław Kubiak

European Journal of Operational Research, 2020, vol. 282, issue 2, 464-477

Abstract: We study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total weighted overlap of all jobs. This is a key problem in subcontractor scheduling in extended enterprises and supply chains, and in divisible load scheduling in computing. We introduce synchronized schedules that complete each job that uses some shared processor at the same time on its private and on the shared processors. We prove that, quite surprisingly, the synchronized schedules include optimal ones. We obtain an α-approximation algorithm that runs in strongly polynomial time for the problem, where α=1/2+1/(4(m+1)). This improves the 1/2-approximation reported recently in the literature to 5/8-approximation for a single shared processor problem, m=1. The computational complexity of the problem, both in case of single and multi-shared processor, remains open. We show however an LP-based optimal algorithm for antithetical instances where for any pair of jobs j and i, if the processing time of j is smaller than or equal to the processing time of i, then the weight of j is greater than or equal to the weight of i.

Keywords: Scheduling; Subcontracting; Supply chains; Extended enterprises; Shared processors (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719307908
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:282:y:2020:i:2:p:464-477

DOI: 10.1016/j.ejor.2019.09.033

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 ().