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

• Autorzy: Małafiejski M. , Kuszner Ł. , Kubale M.

Warianty tytułu

EN

Preemptive scheduling of biprocessor tasks on dedicated machines to minimize sum of completion times

• Konferencja: XIIIKrajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

szeregowanie zadań; maszyny dedykowane

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 313--325
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Małafiejski M.

autor

Kuszner Ł.

autor

Kubale M.

• Politechnika Gdańska, Gdańsk