Jednomaszynowy problem szeregowania zadań o zmiennych wartościach

• Autorzy: Bachman A. , Janiak A. , Krysiak T.

Warianty tytułu

EN

Single machine cheduling problem with job values dependent or their completion times

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrzono jednomaszynowy problem szeregowania, w którym wartości zadań są opisane potęgową funkcją zależną od czasów zakończenia ich wykonywania. Rozpatrzono kryterium maksymalizacji sumy wartości zadań. Analizowany problem został przeformułowany w taki sposób, że zamiast maksymalizacji sumy wartości zadań, optymalizowanym kryterium jest minimalizacja sumy strat ich wartości. Określono złożoność obliczeniową ogólnej wersji problemu wykorzystując transformację z Problemu Podziału. Dla szczególnych przypadków badanego problemu wykazano szereg własności określających optymalne rozwiązanie.

EN

The paper deals with a single machine scheduling problem where job values are characterized by an exponential function dependent on the completion time of job execution. Maximization of the total values is considered as an optimization criterion. However, to simplify the considerations, we reformulate the problem so that the total lost of job values should be minimized. We prove that the general version of the problem stated above is NT-hard. The proof is done from the well known Partition Problem. We construct some optimal algorithms which solve special cases of the general problem in polynomial time.

Słowa kluczowe

PL

problem jednomaszynowy; szeregowanie zadań

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 33--42
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Bachman A.

autor

Janiak A.

autor

Krysiak T.

• Politechnika Wrocławska, Wrocław