Podzielne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych w celu minimalizacji sumy czasów zakończenia

W pracy rozważamy deterministyczne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych, które minimalizuje sumę czasów zakończenia, przy czym dopuszcza się możliwość przerwania wykonywania zadania i ponownego wznowienia obsługi z pomijalnie małym kosztem. W standardowej notacji ten problem zapisujemy jako P|fix j = 2, pmtn| Sigma Cj. Wiadomo, że tak postawione zagadnienie jest problemem silnie NP-trudnym. W pracy badamy złożoność obliczeniową problemu, ograniczając liczbę maszyn. Podajemy wielomianowy algorytm dla problemu P4|fix j = 2, pmtn|Sigma Cj.

---

In this paper we consider a problem of preemptive scheduling of biprocessor tasks on dedicated processors in order to minimize the sum of completion times. Using the standard notation this problem is denoted as P|fix j = 2, pmtn|Sigma Cj. This problem is strongly NP-hard. We analyze the subproblems obtained by reducing the number of processors. We give an exact polynomial algorithm for open problem P4|fix j = 2, pmtn|Sigma Cj.