|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 16 van 24 gevonden artikelen
| Titel: |
Scheduling one and two-processor tasks on two parallel processors |
| Auteur: |
Lee, Chung-Yee Cai, Xiaoqiang |
| Verschenen in: |
IIE transactions |
| Paginering: | Jaargang 31 (1999) nr. 5 pagina's 445-455 |
| Jaar: |
1999-05-01 |
| Inhoud: |
In this paper we study a two-processor scheduling problem where some tasks need to be processed by one processor, while the others have to be processed by both processors simultaneously. The objective is to minimize the total weighted completion time. We first examine the complexity of the problem, showing that it is NP-complete in the strong sense. We then derive optimality properties, and present dynamic programming algorithms, which can find optimal solutions in pseudo-polynomial time. Heuristic methods that can find approximate solutions efficiently are also proposed, and the error bounds of the approximate solutions are established. Finally, a special case is examined and a polynomial algorithm is provided. We show in the Appendix that the problem of minimizing the maximum lateness is also strongly NP-complete and that most of our approaches can be modified to solve this problem. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 16 van 24 gevonden artikelen
| << vorige | volgende >> |