Shared processor scheduling of multiprocessor jobs - Publikacja - MOST Wiedzy

Wyszukiwarka

Shared processor scheduling of multiprocessor jobs

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

  • 1

    CrossRef

  • 0

    Web of Science

  • 1

    Scopus

Autorzy (2)

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

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 20 razy

Publikacje, które mogą cię zainteresować

Meta Tagi