Szeregowanie uogólnionych zadań jednostkowych na maszynach równoległych
Loading...
Date
2019
Authors
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Parallel-machine scheduling of generalized unit-time jobs
Abstract
W rozprawie rozważa się dwa modele szeregowania zadań z ograniczeniami kolejnościowymi i zmiennymi czasami wykonywania na wielu równoległych maszynach. W przypadku pierwszego modelu, w którym zadania jednostkowe mają pozycyjno-zależne czasy wykonywania, udowodniono własności pewnej transformacji oraz podano warunki, przy których transformacja ta pozwala uzyskać w czasie liniowym uszeregowanie optymalne dla uogólnionych zadań jednostkowych, o ile dane jest odpowiednie uszeregowanie optymalne dla zadań o stałych czasach wykonywania. Na tej podstawie pokazano, w jaki sposób można rozwiązać w wielomianowym czasie wybrane problemy rozważanego typu. Zaprezentowano także niezależne od tej transformacji wielomianowe algorytmy dla dwumaszynowych problemów szeregowania uogólnionych zadań jednostkowych z ograniczeniami kolejnościowymi w postaci łańcucha. W przypadku drugiego modelu, czasy wykonywania zadań opisane są całkami Riemanna o granicach zależnych od sumy podstawowych czasów wykonania wcześniejszych zadań. Skonstruowano i opisano własności transformacji związanej z tym modelem, a następnie wykorzystano ją do pokazania pseudowielomianowych rozwiązań problemów z czasami wykonywania zadań opartymi na całkach. Wyniki i pojęcia dotyczące obu modeli zilustrowano przykładami. Pokazano także przykłady otwartych problemów i wskazano na trudności związane z ich rozwiązaniem.
In this dissertation, we consider two models of parallel-machine scheduling of precedence-constrained jobs with variable processing times. In case of the first model, in which unit jobs have position-dependent processing times, we introduce a certain transformation and prove its properties. We also show the conditions under which this transformation generates, in linear time, an optimal schedule for generalized unit-time jobs, provided that an optimal schedule for jobs with fixed processing times is known. Based on these results, we show how to solve several of the considered problems in polynomial time. We also present polynomial algorithms for two-machine scheduling problems with generalized unit-time jobs and with precedence constraints in a form of a chain. In case of the second model, job processing times are described by proper Riemann integrals with limits depending on the sum of processing times of jobs executed earlier. We introduce a transformation related to this model and present its properties. This transformation is used to present pseudo-polynomial algorithms for several problems with integral-based processing times. The results and notions concerning both the above models are illustrated with examples. We also present some open problems and point out the difficulties associated with their solution.
In this dissertation, we consider two models of parallel-machine scheduling of precedence-constrained jobs with variable processing times. In case of the first model, in which unit jobs have position-dependent processing times, we introduce a certain transformation and prove its properties. We also show the conditions under which this transformation generates, in linear time, an optimal schedule for generalized unit-time jobs, provided that an optimal schedule for jobs with fixed processing times is known. Based on these results, we show how to solve several of the considered problems in polynomial time. We also present polynomial algorithms for two-machine scheduling problems with generalized unit-time jobs and with precedence constraints in a form of a chain. In case of the second model, job processing times are described by proper Riemann integrals with limits depending on the sum of processing times of jobs executed earlier. We introduce a transformation related to this model and present its properties. This transformation is used to present pseudo-polynomial algorithms for several problems with integral-based processing times. The results and notions concerning both the above models are illustrated with examples. We also present some open problems and point out the difficulties associated with their solution.
Description
Wydział Matematyki i Informatyki
Sponsor
Keywords
szeregowanie zadań, scheduling, maszyny równoległe, parallel machines, ograniczenia kolejnościowe, precedence constraints, zmienne czasy wykonywania, variable processing times