Wyszukiwarka
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
-
2
CrossRef
-
0
Web of Science
-
2
Scopus
Autorzy (2)
-
Wiesław Kubiak
- Faculty of Business Administration Memorial University
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10951-018-0566-0
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
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
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10951-018-0566-0
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 134 razy