Shared multi-processor scheduling

Dariusz Dereniowski and Wiesław Kubiak

European Journal of Operational Research, 2017, vol. 261, issue 2, 503-514

Abstract: We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job’s completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized schedules that complete each job at the same time on its private and shared processor, if any is actually used by the job, include optimal schedules. We prove that the problem is NP-hard in the strong sense for jobs with arbitrary weights, and we give an efficient, polynomial-time algorithm for the problem with equal weights.

Keywords: Combinatorial optimization; Divisible jobs; Shared processors; Subcontracting; Supply chains (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717301819
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:261:y:2017:i:2:p:503-514

DOI: 10.1016/j.ejor.2017.03.002

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