Jednomaszynowy problem szeregowania zadań o zmiennych wartościach

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.

---

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.