Scheduling with Obligatory Tests

Dogeas, Konstantinos; Erlebach, Thomas; Liang, Ya-Chun

Abstract

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.

Citation

Dogeas, K., Erlebach, T., & Liang, Y.-C. (2024, September). Scheduling with Obligatory Tests. Presented at 32nd Annual European Symposium on Algorithms (ESA 2024), Egham, United Kingdom

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 32nd Annual European Symposium on Algorithms (ESA 2024)
• Start Date: Sep 2, 2024
• End Date: Sep 4, 2024
• Acceptance Date: Jun 1, 2024
• Online Publication Date: Sep 23, 2024
• Publication Date: Sep 23, 2024
• Deposit Date: Jul 16, 2024
• Publicly Available Date: Sep 26, 2024
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Peer Reviewed: Peer Reviewed
• Volume: 308
• Pages: 48:1-48:14
• Series Title: LIPIcs
• Series ISSN: 1868-8969
• Book Title: Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024)
• DOI: https://doi.org/10.4230/LIPIcs.ESA.2024.41
• Public URL: https://durham-repository.worktribe.com/output/2600568