Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Single machine scheduling problem with resource-dependent setup times and the total weighted completion time criterion
Konferencja
XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
Języki publikacji
Abstrakty
W niniejszej pracy rozpatrywany jest jednomaszynowy problem szeregowania zadań z przezbrojeniami sekwencyjnie niezależnymi i ograniczeniem technologii grupowej. Przyjęto, że czasy przezbrojeń opisane są przez nierosnące, liniowe funkcje zależne od dodatkowego zasobu podzielnego w sposób ciągły lub dyskretny. Jako kryterium optymalności przyjęto minimalizację ważonych czasów zakończenia wykonywania zadań. Wykazano, że problem z zasobem podzielnym w sposób dyskretny jest problemem NP-trudnym. Ponadto, wykazano szereg własności badanego problemu oraz zaproponowano kilka algorytmów przybliżonych, których efektywność zbadano eksperymentalnie.
In the paper a single machine scheduling problem with sequence- independent setup times and group technology is considered. The setup times are given as some nonincreasing, linear functions dependent on additional continuously or discretely-divisible resources. The scheduling criterion is the minimization of the total weighted completion time. It is shown that the problem with discretely-divisible resources is NP-hard. Additionally, some specific properties of the problem are proven, and several approximation algorithms are proposed. The efficiency of these algorithms is verified experimentally.
Słowa kluczowe
Rocznik
Tom
Strony
219--232
Opis fizyczny
Bibliogr. 9 poz.
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL6-0008-0002