2026-07-23T07:58:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21119 2024-09-23T09:13:17Z ddc:004 open_access

Scheduling with Obligatory Tests Dogeas, Konstantinos Erlebach, Thomas Liang, Ya-Chun Competitive ratio Online algorithm Scheduling with testing Sum of completion times Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations, a test and a processing part. The time required to execute the test is known in advance while the time required to execute the processing part becomes known only upon completion of the test. We use competitive analysis to study algorithms for minimizing the sum of completion times for n given jobs on a single machine. As our main result, we prove using a novel analysis technique that the natural 1-SORT algorithm has competitive ratio at most 1.861. For the special case of uniform test times, we show that a simple threshold-based algorithm has competitive ratio at most 1.585. We also prove a lower bound that shows that no deterministic algorithm can be better than √2-competitive even in the case of uniform test times. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konstantinos Dogeas and Thomas Erlebach and Ya-Chun Liang 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.48 urn:nbn:de:0030-drops-211194 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.48 eng https://creativecommons.org/licenses/by/4.0/legalcode