講    題：Scheduling with Obligatory Tests

主 講 人：梁雅鈞 助理教授  清華大學資訊工程學系

主辦單位：陽明交通大學工業工程與管理系

時    間：114年12月1日(星期一) 13:20 ~ 15:20  

地    點：管理二館MB520教室

演講摘要：

Motivated by applications such as medical treatments and aircraft maintenance, we study a scheduling problem in which each job consists of two operations: a test and a processing step. The test time of each job is known in advance, whereas the processing time becomes known only after the test has been completed. Using competitive analysis, we investigate algorithms that aim to minimize the total completion time of 𝑛 jobs on a single machine.

Our main result is a novel analysis showing that the natural 1-SORT algorithm achieves a competitive ratio of at most 1.861. For the special case where all test times are identical, we further show that a simple threshold-based algorithm has a competitive ratio of at most 1.585. We also establish a lower bound: no deterministic algorithm can have a competitive ratio better than $\sqrt{2}$, even when test times are uniform.

This is joint work with Konstantinos Dogeas and Thomas Erlebach.

演講性質：學術研究專題

歡迎聽講