Wyszukiwarka
Abstrakt
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.
Cytowania
-
4
CrossRef
-
0
Web of Science
-
5
Scopus
Autorzy (2)
-
Wiesław Kubiak
- Memorial University Faculty of Business Administration
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
nr 282,
strony 464 - 477,
ISSN: 0377-2217 - Język:
- angielski
- Rok wydania:
- 2020
- Opis bibliograficzny:
- Dereniowski D., Kubiak W.: Shared processor scheduling of multiprocessor jobs// EUROPEAN JOURNAL OF OPERATIONAL RESEARCH -Vol. 282,iss. 2 (2020), s.464-477
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.ejor.2019.09.033
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 151 razy