Doctoral thesis
Author:
Mgr. Tomáš Ebenelendr, Ph.D.
Topic:
Combinatorial algorithms for online problems: Semi-online scheduling on related machines
Defense:
Prague, 2011
Institute:
Institute of Mathematics of the Academy of Sciences of the Czech Republic
Institute:
Institute for Theoretical Computer Science, Charles University in Prague
Advisor:
Doc. RNDr. Jiří Sgall, DrSc.
Branch:
I4 - Discrete Models and Algorithms
Application for Cena CSKI
Application (přihláška): ebenlendr-application-cski.pdf
Archive: ebenlendr-thesis.zip 1 (11MB)
1 The archive contains this web presentation including all pdf files. It also contains computed overall lower bounds on competitive ratios for up to 210 machines, including input instances witnessing the lower bounds. Source code of used Maple programs is also included. These programs were used to compute the mentioned bounds and to complete the analysis of various semionline cases for up to 5 machines.
Abstract

We construct a framework that gives optimal algorithms for a whole class of scheduling problems. This class covers the most studied semi-online variants of preemptive online scheduling on uniformly related machines with the objective to minimize makespan. The algorithms from our framework are deterministic, yet they are optimal even among all randomized algorithms. In addition, they are optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. We provide a new lower bound of 2.112 for the original online problem. The (deterministic) upper bound is e ≈ 2.718 as there was known e-competitive randomized algorithm before.

Our framework applies to all semi-online variants which are based on some knowledge about the input sequence. I.e., they are restrictions of the set of valid inputs. We use our framework to study the restrictions that were studied before, and we derive some new bounds. Namely we study known sum of processing times, known maximal processing time, sorted (decreasing) jobs, tightly grouped processing times, approximately known optimal makespan and a few combinations. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions.

The framework uses linear programs to compute the optimal competitive ratio for given input environment as our algorithms need to know this value. The environment is described by some parameters (the speeds of the machines), these parameters play a role of constants in the linear programs. We developed a technique to symbolically solve small linear programs. We obtain formulas for the competitive ratio in the special case of up to four machines this way.

The last chapter provides a new lower bound of 2.564 on the competitive ratio of deterministic online nonpreemptive scheduling.

Hlavním výsledkem této práce je konstrukce optimálních algoritmů pro celou třídu rozvrhovacích problémů. Tato třída zahrnuje většinu zkoumaných semi-online variant preemptivního rozvrhování na strojích s různými rychlostmi s cílem minimalizovat délku rozvrhu. Takto zkonstruované algoritmy jsou deterministické, nicméně dosahují optimální kompetitivní poměr i mezi pravděpodobnostními algoritmy. Navíc jsou optimální i pro libovolnou pevnou kombinaci rychlostí strojů, proto lze naši konstrukci uplatnit i na veškeré dříve studované speciální případy. Ukážeme nový dolní odhad 2.112 pro obecné online rozvrhování. Deterministický horní odhad e ≈ 2.718 pak plyne z dřívější existence e-kompetitivního pravděpodobnostního algoritmu.

Zmíněnou konstrukci lze aplikovat ve všech semi-online variantách, které jsou založeny na znalosti o vstupní sekvenci. Ty lze chápat jako omezení množiny platných vstupů. Tuto konstrukci pak použijeme ke studiu dříve zkoumaných omezení, čímž získáme nové odhady kompetitivního poměru. Jmenovitě zkoumáme známou sumu velikostí úloh, známou největší úlohu, (sestupně) setřízené úlohy, úlohy přibližně stejné velikosti, přibližně známou délku rozvrhu a několik jejich kombinací. Na základě analýzy algoritmu z naší konstrukce dostaneme několik obecných vztahů mezi některými semi-online omezeními.

Naše konstrukce používá lineární programy pro výpočet optimálního kompetitivního poměru pro prostředí zadané na vstupu, protože naše algoritmy potřebují znát tuto hodnotu. Prostředí je zadáno parametry (především rychlostmi strojů), tyto parametry mají funkci konstant v řešených lineárních programech. Vyvinuli jsme techniku pro symbolické řešení malých lineárních programů a tou jsme získali vzorce dávající optimální kompetitivní poměr, do kterých stačí dosadit rychlosti pro prostředí s nejvýše čtyřmi stroji.

V poslední kapitole pak dokážeme nový dolní odhad 2.564 pro deterministické online rozvrhování bez preempcí.

Thesis
Extended abstract: extended-abstract.pdf
Thesis: thesis.pdf
Defense
List of citations: citations-1201.pdf 2
Curriculum vitae (english): cv.html
Curriculum vitae (czech): cv-cs.html
Review of Doc. RNDr. Jiří Sgall, DrSc. (advisor): review-sgall.pdf
Review of Prof. Gerhard Woeginger (referee): review-woeginger.pdf
Review of Dr. Leah Epstein (referee): review-epstein.pdf
Review of Doc. RNDr. Roman Barták, Ph.D. (referee): review-bartak.pdf
2 The list of citations has been updated by citations that occured after the defense.
Publications related to the thesis
Authors:
Tomáš Ebenlendr, Wojciech Jawor and Jiří Sgall
Title:
Preemptive online scheduling: Optimal algorithms for all speeds
Journal
(full version):
Algorithmica, 53:504–522, 2009.
Conference
(extended abstract):
In Proc. 14th European Symp. on Algorithms (ESA), volume 4168 of Lecture Notes in Comput. Sci, pages 327–339, Springer, 2006.
Conference
(abstract):
In Proc. 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), Koc University, 2007.
File:
optrel.pdf
Authors:
Tomáš Ebenlendr and Jiří Sgall
Title:
Optimal and online preemptive scheduling on uniformly related machines
Journal
(full version):
Journal of Scheduling, 12:517–527, 2009.
Conference
(extended abstract):
In Proc. 21st Symp. on Theoretical Aspects of Computer Science (STACS), volume 2996 of Lecture Notes in Comput. Sci., pages 199–210, Springer, 2004.
File:
relpm.pdf
Authors:
Tomáš Ebenlendr and Jiří Sgall
Title:
Semi-online preemptive scheduling: One algorithm for all variants
Journal
(full version):
Theory of Computing Systems, 1–37, 2010.
Conference
(extended abstract):
In Proc. 26th Symp. on Theoretical Aspects of Computer Science (STACS), volume 3 of LIPIcs, pages 346–360, Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, Germany, 2009.
Conference
(abstract):
In Proc. 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), volume WP 09-11 of CTIT proceedings, pages 61–64, University of Twente, 2009.
File:
semirel.pdf
Authors:
Tomáš Ebenlendr
Title:
Semi-online Preemptive Scheduling: Study of Special Cases
Conference
(full version):
In Proc. 8th Parallel Processing and Applied Mathematics, volume 6068 of Lecture Notes in Comput. Sci, pages 11–20, Springer, 2010.
File:
srelcase.pdf
Authors:
Tomáš Ebenlendr and Jiří Sgall
Title:
A lower bound on deterministic online algorithms for scheduling on related machines without preemption
Conference
(full version):
To appear in Proc. 9th International Workshop in Approximation and Online Algorithms, volume ? of Lecture Notes in Comput. Sci, Springer, 2012.
Conference
(abstract):
In Proc. 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), volume 2011-525 of ITI Series, pages 82–84, ITI - Charles University, 2011.
File:
rellbdet.pdf
Other publications
Authors:
Tomáš Ebenlendr, John Noga, Jiří Sgall and Gerhard Woeginger
Title:
A note on semi-online machine covering
Conference
(full version):
In Proc. 3rd International Workshop in Approximation and Online Algorithms, volume 3879 of Lecture Notes in Comput. Sci, pages 110–118, Springer, 2006.
File:
mcover.pdf
Authors:
Jihuan Ding, Tomáš Ebenlendr, Jiří Sgall and Guochuan Zhang
Title:
Online scheduling of equal-length jobs on parallel machines
Conference
(full version):
In Proc. 15th European Symp. on Algorithms (ESA), volume 4698 of Lecture Notes in Comput. Sci, pages 427–438, Springer, 2007.
File:
eqpar.pdf
Authors:
Tomáš Ebenlendr and Jiří Sgall
Title:
A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines
Conference
(full version):
In Proc. 6th International Workshop in Approximation and Online Algorithms, volume 5426 of Lecture Notes in Comput. Sci, pages 43–52, Springer, 2009.
Conference
(abstract):
In Proc. 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP), volume WP 09-11 of CTIT proceedings, pages 183–185, University of Twente, 2009.
File:
uparlb.pdf
Authors:
Tomáš Ebenlendr, Marek Krčál and Jiří Sgall
Title:
Graph balancing: a special case of scheduling unrelated parallel machines
Journal
(full version):
To appear in Algorithmica, 2012.
Conference
(extended abstract):
In Proc. 19th Symp. on Discrete Algorithms (SODA), 483–490, ACM/SIAM,, 2008.
File:
grbal.pdf