en
0.25
0.5
0.75
1.25
1.5
1.75
2
Open Problems in Throughput Scheduling
Published on Oct 02, 20122754 Views
In this talk we survey the area of scheduling with the objective to maximize the throughput, i.e., the (weighted) number of completed jobs. We focus on several open problems.
Related categories
Chapter list
Open problems in throughput scheduling00:00
A puzzle (1)00:31
A puzzle (2)00:43
A puzzle (3)00:54
A puzzle (4)01:01
A puzzle (5)01:20
Throughput scheduling (1)02:21
Throughput scheduling (2)03:35
Throughput scheduling (3)03:48
Online scheduling (1)04:14
Online scheduling (2)04:58
Online scheduling (3)05:34
Other scheduling problems (1)06:08
Other scheduling problems (2)07:21
Jobs of equal length (1)09:44
Jobs of equal length (2)10:27
Greedy algorithms (1)11:37
Greedy algorithms (2)12:22
Greedy algorithms (3)12:58
Greedy algorithms (4)13:05
Lower bounds (1)14:03
Lower bounds (2)14:11
Lower bounds (3)14:34
Lower bounds (4)15:01
A barely random algorithm I (1)16:03
A barely random algorithm I (2)17:21
A barely random algorithm I (3)17:29
A barely random algorithm II (1)19:14
A barely random algorithm II (2)19:36
A barely random algorithm II (3)20:00
A barely random algorithm II (4)20:23
A barely random algorithm II (5)20:41
A barely random algorithm II (6)20:46
A barely random algorithm II (7)20:47
A barely random algorithm II (8)21:07
A barely random algorithm III (1)21:20
A barely random algorithm III (2)22:27
A barely random algorithm III (3)22:37
More machines (1)23:07
More machines (2)24:02
More machines (3)24:43
Jobs with fi xed start times (1)25:00
Jobs with fi xed start times (2)26:15
Machines with speeds (1)27:08
Machines with speeds (2)28:31
Machines with speeds (3)29:11
Unit time jobs with weights (1)30:42
Unit time jobs with weights (2)31:44
Motivation and variants (1)32:31
Motivation and variants (2)33:25
Greedy algorithm (5)36:16
Greedy algorithm (6)36:51
Greedy algorithm (7)37:00
A randomized algorithm38:06
A potential function (1)40:54
A potential function (2)43:33
A potential function (3)43:45
A potential function (4)44:11
Analysis45:07
Deterministic algorithms I (1)46:21
Deterministic algorithms I (2)46:59
Deterministic algorithms II (1)47:05
Deterministic algorithms II (2)48:04
Lower bounds (1)48:33
Lower bounds (2)48:35
Offline scheduling (1)49:42
Offline scheduling (2)50:15
A linear program (1)51:09
A linear program (2)53:04
A linear program (3)53:31
A linear program (4)53:36
A linear program (5)54:07
Offline scheduling - open problems (1)54:10
Offline scheduling - open problems (2)54:12
Offline scheduling - open problems (3) - Thank you!55:54