Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Scheduling under uncertainty : A Query-based Approach. / Arantes, Luciana; Bampis, Evripidis; Kononov, Alexander et al.
Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018. Vol. 2018-July International Joint Conferences on Artificial Intelligence, 2018. p. 4646-4652 (IJCAI International Joint Conference on Artificial Intelligence; Vol. 2018-July).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Scheduling under uncertainty
T2 - 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
AU - Arantes, Luciana
AU - Bampis, Evripidis
AU - Kononov, Alexander
AU - Letsios, Manthos
AU - Lucarelli, Giorgio
AU - Sens, Pierre
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We consider a single machine, a set of unit-time jobs, and a set of unit-time errors. We assume that the time-slot at which each error will occur is not known in advance but, for every error, there exists an uncertainty area during which the error will take place. In order to find if the error occurs in a specific time-slot, it is necessary to issue a query to it. In this work, we study two problems: (i) the error-query scheduling problem, whose aim is to reveal enough error-free slots with the minimum number of queries, and (ii) the lexicographic error-query scheduling problem where we seek the earliest error-free slots with the minimum number of queries. We consider both the off-line and the online versions of the above problems. In the former, the whole instance and its characteristics are known in advance and we give a polynomial-time algorithm for the error-query scheduling problem. In the latter, the adversary has the power to decide, in an on-line way, the time-slot of appearance for each error. We propose then both lower bounds and algorithms whose competitive ratios asymptotically match these lower bounds.
AB - We consider a single machine, a set of unit-time jobs, and a set of unit-time errors. We assume that the time-slot at which each error will occur is not known in advance but, for every error, there exists an uncertainty area during which the error will take place. In order to find if the error occurs in a specific time-slot, it is necessary to issue a query to it. In this work, we study two problems: (i) the error-query scheduling problem, whose aim is to reveal enough error-free slots with the minimum number of queries, and (ii) the lexicographic error-query scheduling problem where we seek the earliest error-free slots with the minimum number of queries. We consider both the off-line and the online versions of the above problems. In the former, the whole instance and its characteristics are known in advance and we give a polynomial-time algorithm for the error-query scheduling problem. In the latter, the adversary has the power to decide, in an on-line way, the time-slot of appearance for each error. We propose then both lower bounds and algorithms whose competitive ratios asymptotically match these lower bounds.
UR - http://www.scopus.com/inward/record.url?scp=85055715148&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/804e9941-95fa-3e9c-b0b1-831aaf2cb1ef/
U2 - 10.24963/ijcai.2018/646
DO - 10.24963/ijcai.2018/646
M3 - Conference contribution
AN - SCOPUS:85055715148
SN - 9780999241127
VL - 2018-July
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 4646
EP - 4652
BT - Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
PB - International Joint Conferences on Artificial Intelligence
Y2 - 13 July 2018 through 19 July 2018
ER -
ID: 17250823