Podzielne szeregowanie zadań z pozycyjno-zależnymi czasami wykonywania na dwóch równoległych identycznych maszynach
Loading...
Date
2019
Authors
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Preemptive scheduling of jobs with position-dependent processing times on two parallel identical machines
Abstract
W rozprawie rozważamy podzielne szeregowanie zadań z pozycyjno-zależnymi czasami wykonywania na dwóch równoległych identycznych maszynach z długością uszeregowania jako kryterium optymalności. Przedstawiamy przegląd literatury na temat modeli podzielności zadań. Proponujemy nowy model podzielności, w którym tylko jedno pozycyjno-zależne zadanie może być przerywane. Przedstawiamy kilka własności badanego problemu. Prezentujemy dwa algorytmy dokładne i dwa algorytmy heurystyczne rozwiązujące badany problem. Omawiamy wyniki eksperymentów numerycznych, przeprowadzonych w celu porównania zaproponowanych algorytmów.
In the thesis, we consider preemptive scheduling of jobs with position-dependent processing times on two parallel identical machines with the maximum completion time criterion. We present a review of the literature of the main models of job preemption. We propose a new model of position-dependent job preemption in which jobs may be preempted but only restricted preemption of a single job is allowed. We present several properties of this problem. We present two exact algorithms and two heuristic algorithm for its solution. We discuss the results of numerical experiments conducted to compare the proposed algorithms.
In the thesis, we consider preemptive scheduling of jobs with position-dependent processing times on two parallel identical machines with the maximum completion time criterion. We present a review of the literature of the main models of job preemption. We propose a new model of position-dependent job preemption in which jobs may be preempted but only restricted preemption of a single job is allowed. We present several properties of this problem. We present two exact algorithms and two heuristic algorithm for its solution. We discuss the results of numerical experiments conducted to compare the proposed algorithms.
Description
Wydział Matematyki i Informatyki
Sponsor
Keywords
szeregowanie, równoległe maszyny, efekt uczenia się, podzielność zadań, długość uszeregowania, scheduling, parallel machines, learning effect, job preemption, the maximum completion time