Jednomaszynowe problemy szeregowania zadań zależnych z mieszanymi czasami wykonywania

Rozprawa dotyczy trzech rodzin jednomaszynowych problemów szeregowania, w których zadania mają różne postaci czasów wykonywania, między którymi występują niepuste ograniczenia kolejnościowe, a jakość uszeregowań oceniana jest za pomocą kryterium maksymalnego kosztu. Dla pierwszej rodziny problemów, w których zadania mają zmienne mieszane czasy wykonywania opisane funkcjami zależnymi od czasu rozpoczęcia wykonywania danego zadania lub jego pozycji w uszeregowaniu, między którymi istnieją dowolne niepuste ograniczenia kolejnościowe zaproponowano wielomianowe algorytmy konstruujące optymalne uszeregowania o najmniejszym maksymalnym koszcie. Dla drugiej rodziny problemów, w których zadania mają zmienne mieszane czasy wykonywania opisane funkcjami zależnymi od czasu rozpoczęcia wykonywania danego zadania lub jego pozycji w uszeregowaniu, między którymi istnieją k-dzielne ograniczenia kolejnościowe zaproponowano wielomianowy algorytm konstruujący optymalne uszeregowania o najmniejszym maksymalnym koszcie. Dla trzeciej rodziny problemów, w których zadania mają zmienne mieszane czasy wykonywania opisane funkcjami zależnymi od czasu rozpoczęcia wykonywania danego zadania, między którymi istnieją dowolne niepuste ograniczenia kolejnościowe zaproponowano algorytmy dokładne, konstrukcyjne algorytmy heurystyczne i hybrydowy algorytm heurystyczny wraz z wynikami ich analizy eksperymentalnej.

Author dc:creator

• Dębczyński, Marek

Advisor dc:contributor.advisor

• Gawiejnowicz, Stanisław. Promotor

• szeregowanie zadań
• scheduling
• ograniczenia kolejnościowe
• precedence constraints
• maksymalny koszt
• maximum cost
• wielomianowe algorytmy
• polynomial algorithms

Language dc:language.iso

pl

Identifier

hdl:10593/6302

OAI record oai:identifier

https://repozytorium.amu.edu.pl/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Arepozytorium.amu.edu.pl%3A10593%2F6302