Shared processor scheduling of multiprocessor jobs

Dariusz Dereniowski; Wiesław Kubiak

doi:10.1016/j.ejor.2019.09.033

Shared processor scheduling of multiprocessor jobs

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.

Citations

4

CrossRef
0

Web of Science
5

Scopus

Authors (2)

Dariusz Dereniowski prof. dr hab. inż.
Wiesław Kubiak
- Memorial University Faculty of Business Administration

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach
Published in:: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH no. 282, pages 464 - 477,
ISSN: 0377-2217
Language:: English
Publication year:: 2020
Bibliographic description:: Dereniowski D., Kubiak W.: Shared processor scheduling of multiprocessor jobs// EUROPEAN JOURNAL OF OPERATIONAL RESEARCH -Vol. 282,iss. 2 (2020), s.464-477
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.ejor.2019.09.033
Verified by:: Gdańsk University of Technology