TY - GEN
T1 - Online linear optimization for job scheduling under precedence constraints
AU - Fujita, Takahiro
AU - Hatano, Kohei
AU - Kijima, Shuji
AU - Takimoto, Eiji
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.
PY - 2015
Y1 - 2015
N2 - We consider an online job scheduling problem on a single machine with precedence constraints under uncertainty. In this problem, for each trial t = 1,..., T, the player chooses a total order (permutation) of n fixed jobs satisfying some prefixed precedence constraints. Then, the adversary determines the processing time for each job, 9 and the player incurs as loss the sum of the processing time and the waiting time. The goal of the player is to perform as well as the best fixed total order of jobs in hindsight. We formulate the problem as an online linear optimization problem over the permutahedron (the convex hull of permutation vectors) with specific linear constraints, in which the underlying decision space is written with exponentially many linear constraints. We propose a polynomial time online linear optimization algorithm; it predicts almost as well as the state-of-the-art offline approximation algorithms do in hindsight.
AB - We consider an online job scheduling problem on a single machine with precedence constraints under uncertainty. In this problem, for each trial t = 1,..., T, the player chooses a total order (permutation) of n fixed jobs satisfying some prefixed precedence constraints. Then, the adversary determines the processing time for each job, 9 and the player incurs as loss the sum of the processing time and the waiting time. The goal of the player is to perform as well as the best fixed total order of jobs in hindsight. We formulate the problem as an online linear optimization problem over the permutahedron (the convex hull of permutation vectors) with specific linear constraints, in which the underlying decision space is written with exponentially many linear constraints. We propose a polynomial time online linear optimization algorithm; it predicts almost as well as the state-of-the-art offline approximation algorithms do in hindsight.
UR - http://www.scopus.com/inward/record.url?scp=84945963233&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84945963233&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-24486-0_22
DO - 10.1007/978-3-319-24486-0_22
M3 - Conference contribution
AN - SCOPUS:84945963233
SN - 9783319244853
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 332
EP - 346
BT - Algorithmic Learning Theory - 26th International Conference, ALT 2015
A2 - Gentile, Claudio
A2 - Zilles, Sandra
A2 - Chaudhuri, Kamalika
PB - Springer Verlag
T2 - 26th International Conference on Algorithmic Learning Theory, ALT 2015
Y2 - 4 October 2015 through 6 October 2015
ER -