Podzielne szeregowanie zadań z pozycyjno-zależnymi czasami wykonywania na dwóch równoległych identycznych maszynach

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.