Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
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
Abstrakty
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.
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
Rocznik
Tom
Strony
315--320
Opis fizyczny
Bibliogr. 7 poz.
Twórcy
autor
- Katedra Podstaw Informatyki Politechnika Gdańska, 80-952 Gdańsk Wrzeszcz, ul. Narutowicza 11/12, tel. (058) 347-14-55, 347-28-18, conti@eti.pg.gda.pl
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0005-0030