Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Minimizing maximum lateness for the deteriorating jobs
Konferencja
XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych; Zakopane 24-27.09.1998
Języki publikacji
Abstrakty
W pracy rozpatrywano jednomaszynowy problem szeregowania zadań czasowo zależnych przy kryterium minimalizacji maksymalnej nieterminowości wykonania. Założono, że czas wykonywania zadania, dany w postaci liniowej, niemalejącej funkcji terminu rozpoczęcia wykonywania składa się z dwóch części: stałej i zmiennej. Stała część, niezależna od terminu rozpoczęcia, określa pewną minimalną długość czasu wykonywania zadania, wynikającą z uwarunkowań technologicznych. Natomiast zmienna część, charakteryzowana przez czynnik wzrostu, opisuje wpływ terminu rozpoczęcia wykonywania na wydłużenie zadania. Pokazano, że przy tak scharakteryzowanym modelu jednomaszynowy problem szeregowania zadań przy kryterium minimalizacji maksymalnej nieterminowości jest NP-zupełny.
The paper deals with the single machine scheduling problem, where the job processing time is given as a linear, nondecreasing function dependent on the processing start time. The function describing the job processing time consists of two parts, where one is constant and describes the minimal time required to complete the job if its starting moment is equal to zero. The second part, characterized by the growth rate, describes how fast the job processing time deteriorate. We showed that such a described problem for the maximum lateness criterion is NP-complete by reducing to it NP-complete Partition Problem.
Słowa kluczowe
Rocznik
Tom
Strony
23--31
Opis fizyczny
Bibliogr. 6 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL2-0001-0015
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.