Scheduling under uncertainty: A Query-based Approach

Luciana Arantes, Evripidis Bampis, Alexander Kononov, Manthos Letsios, Giorgio Lucarelli, Pierre Sens

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

1 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
ИздательInternational Joint Conferences on Artificial Intelligence
Страницы4646-4652
Число страниц7
Том2018-July
ISBN (электронное издание)9780999241127
DOI
СостояниеОпубликовано - 1 янв 2018
Событие27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Швеция
Продолжительность: 13 июл 201819 июл 2018

Конференция

Конференция27th International Joint Conference on Artificial Intelligence, IJCAI 2018
СтранаШвеция
ГородStockholm
Период13.07.201819.07.2018

Fingerprint Подробные сведения о темах исследования «Scheduling under uncertainty: A Query-based Approach». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать