Shared processor scheduling - Publikacja - MOST Wiedzy

Wyszukiwarka

Shared processor scheduling

Abstrakt

We study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an (log)-time optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights—this instance generalizes the unweighted case of the problem. This algorithm also leads to a 1/2-approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open.

Cytowania

  • 0
    CrossRef
  • 0
    Web of Science
  • 0
    Scopus

Dariusz Dereniowski, Wiesław Kubiak. (2018). Shared processor scheduling, 21(6), 583-593. https://doi.org/10.1007/s10951-018-0566-0

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
JOURNAL OF SCHEDULING nr 21, wydanie 6, strony 583 - 593,
ISSN: 1094-6136
Język:
angielski
Rok wydania:
2018
Opis bibliograficzny:
Dereniowski D., Kubiak W.: Shared processor scheduling// JOURNAL OF SCHEDULING. -Vol. 21, iss. 6 (2018), s.583-593

wyświetlono 1 razy

Publikacje, które mogą cię zainteresować

Meta Tagi