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

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.

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

Citation

ISBN

DOI

Title Alternative

Rights Creative Commons

Creative Commons License

Uniwersytet im. Adama Mickiewicza w Poznaniu
Biblioteka Uniwersytetu im. Adama Mickiewicza w Poznaniu
Ministerstwo Nauki i Szkolnictwa Wyższego