Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Minimizing the total resource consumption for single machine job scheduling problems with variable execution times
Konferencja
Automatyzacja procesów dyskretnych/krajowa konferencja (XII ; 13-16.09.2000 ; Zakopane)
Języki publikacji
Abstrakty
W niniejszej pracy badane są jednomaszynowe problemy szeregowania zadań z czasami wykonania zależnymi od momentu rozpoczęcia wykonywania oraz ilości dostarczonego zasobu. Wykazano, że jeśli problem minimalizacji kryteriów czasowych takich jak długość uszeregowania oraz całkowity czas zakończenia wszystkich zadań przy ograniczeniu na całkowitą dostępną ilość zasobu jest problemem wielomianowym, to odpowiadający mu problem minimalizacji całkowitej ilości zasobu przy ograniczeniu na odpowiednie kryterium czasowe jest również problemem wielomianowym.
The single machine job scheduling problems with time and resource dependent execution times have been examined in this paper. We proved, that if the problem of minimising the time criteria such as the makespan and the total completion time subject to a given constraint on the total resource consumption could be solved in polynomial time, then the corresponding problem of minimizing the total resource consumption subject to a given constraint on the value of the appropriate time criterion can be solved also in polynomial time.
Słowa kluczowe
Rocznik
Tom
Strony
123--134
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0005-0012