Jednomaszynowe problemy szeregowania zadań zależnych z mieszanymi czasami wykonywania
Loading...
Date
2013-05-24
Authors
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Single machine problems of scheduling dependent jobs with variable mixed processing times.
Abstract
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.
This thesis concerns three families of single-machine scheduling problems, in which set of jobs consists jobs with different job processing times, between the jobs exist non-empty job precedence constraints and the quality of schedules is measured by maximum cost criterion. The main aim of the dissertation is to construct polynomial algorithms finding optimal or suboptimal schedules for these three families of single-machine scheduling problems. For the first family of scheduling problems with mixed job processing times, which depend on starting time and position of the job in the schedule, arbitrary job precedence constraints and the maximum cost criterion, we present polynomial algorithms constructing optimal schedules with minimal cost. For the second family of scheduling problems with mixed variable job processing times, which depend on starting time and position of the job in the schedule, k-partite job precedence constraints and the maximum cost criterion, we present a polynomial algorithm constructing optimal schedules with minimal cost. For the third family of scheduling problems with mixed job processing times, which depend on starting time of the job, arbitrary job precedence constraints and the maximum cost criterion, we present exact algorithms, heuristic algorithms and hybrid heuristic algorithm and the results of numerical experiment.
This thesis concerns three families of single-machine scheduling problems, in which set of jobs consists jobs with different job processing times, between the jobs exist non-empty job precedence constraints and the quality of schedules is measured by maximum cost criterion. The main aim of the dissertation is to construct polynomial algorithms finding optimal or suboptimal schedules for these three families of single-machine scheduling problems. For the first family of scheduling problems with mixed job processing times, which depend on starting time and position of the job in the schedule, arbitrary job precedence constraints and the maximum cost criterion, we present polynomial algorithms constructing optimal schedules with minimal cost. For the second family of scheduling problems with mixed variable job processing times, which depend on starting time and position of the job in the schedule, k-partite job precedence constraints and the maximum cost criterion, we present a polynomial algorithm constructing optimal schedules with minimal cost. For the third family of scheduling problems with mixed job processing times, which depend on starting time of the job, arbitrary job precedence constraints and the maximum cost criterion, we present exact algorithms, heuristic algorithms and hybrid heuristic algorithm and the results of numerical experiment.
Description
Wydział Matematyki i Informatyki: Zakład Algorytmiki i Programowania
Sponsor
Keywords
szeregowanie zadań, scheduling, ograniczenia kolejnościowe, precedence constraints, maksymalny koszt, maximum cost, wielomianowe algorytmy, polynomial algorithms