Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/6302
Title: Jednomaszynowe problemy szeregowania zadań zależnych z mieszanymi czasami wykonywania
Other Titles: Single machine problems of scheduling dependent jobs with variable mixed processing times.
Authors: Dębczyński, Marek
Advisor: Gawiejnowicz, Stanisław. Promotor
Keywords: szeregowanie zadań
scheduling
ograniczenia kolejnościowe
precedence constraints
maksymalny koszt
maximum cost
wielomianowe algorytmy
polynomial algorithms
Issue Date: 24-May-2013
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.
Description: Wydział Matematyki i Informatyki: Zakład Algorytmiki i Programowania
URI: http://hdl.handle.net/10593/6302
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2021 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
PHD_Marek_Debczynski.pdf533.54 kBAdobe PDFView/Open
Show full item record



Items in AMUR are protected by copyright, with all rights reserved, unless otherwise indicated.