Minimalizacja globalnej ilości wykorzystanych zasobów dla jednomaszynowych problemów szeregowania zadań ze zmiennymi czasami wykonania

• Autorzy: Iwanowski D. , Janiak A.

Warianty tytułu

EN

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: PL

Abstrakty

PL

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.

EN

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

PL

szeregowanie zadań; czasy wykonywania; problem jednomaszynowy

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

Twórcy

autor

Iwanowski D.

autor

Janiak A.

• Politechnika Wrocławska