Jednomaszynowe problemy szeregowania zadań ze zmiennymi czasami wykonania - podejście dwukryterialne

• Autorzy: Iwanowski D. , Janiak A.

Warianty tytułu

EN

Single machine job scheduling problems with variable execution times - bicriterional approach

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

Abstrakty

PL

W pracy badane są jednomaszynowe problemy szeregowania zadań z czasami wykonania zależnymi od momentów rozpoczęcia oraz ilości dostarczonych zasobów. Wykazano, że jeśli problem minimalizacji kryteriów czasowych takich jak długość uszeregowani oraz całkowity czas zakończenia wszystkich zadań przy ograniczeniu na całkowitą dostępną ilość zasobów jest problemem wielomianowym, a także odpowiadający mu problem minimalizacji całkowitej ilości zasobu przy ograniczeniu na odpowiednie kryterium czasowe jest problemem wielomianowym, to możliwe jest skonstruowanie zbioru rozwiązań Pareto optymalnych (podejście dwukryterialne) również w czasie wielomianowym.

EN

The single machine job scheduling problems with time and resource dependent execution times are examined in this paper. We proved, that if the problem of minimizing criteria such as the makespan and total completion time with constrained value of total amount of resources available could be solved in polynomial time as well as corresponding version of this problem, where the total resource consumption is minimised subject to a given constraint on a time criterion, then the set of Pareto optimal solutions (bicriterional approach) can be easily constructed 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: 111--121
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Iwanowski D.

autor

Janiak A.

• Politechnika Wrocławska