Szeregowanie zadań z optymalizacją średniego czasu zakończenia operacji w systemie otwartym

• Autorzy: Piwakowski K.

Warianty tytułu

EN

Open shop scheduling to minimize average completion time of the operations

• Konferencja: Automatyzacja procesów dyskretnych/krajowa konferencja (XII ; 13-16.09.2000 ; Zakopane)
• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy rozważamy graniczne przypadki otwartego systemu obsługi zadań niepodzielnych NOSS (Non-Preemptive Open-Shop Scheduling), dla których problem szeregowania z optymalizacją średniego czasu zakończenia operacji przestaje być wielomianowy i staje się NP-trudny. W szczególności dowodzimy, że wielomianowy przypadek pojedynczego zadania składającego się z n operacji wykonywanych na n różnych procesorach staje się NP-trudny po dołączeniu drugiego zadania, składającego się z jednej operacji wykonywanej na jednym (z góry określonym) procesorze.

EN

In this paper we consider some special cases of the Non-Preemptive Open-Shop Scheduling model with the average completion time of all operations as the optimality criterion. In particular we prove that the polynomial solvable case where there is only one job consisting of n operations, becomes NP-hard when another job with only one operation sharing one of the processors is added.

Słowa kluczowe

PL

szeregowanie zadań; dyskretna optymalizacja

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2000
• Tom: z. 129
• Strony: 315--320
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Piwakowski K.

• Katedra Podstaw Informatyki Politechnika Gdańska, 80-952 Gdańsk Wrzeszcz, ul. Narutowicza 11/12, tel. [phone],