講    題：具有強制測試的排程問題

(Scheduling with Obligatory Tests)

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

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

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

地    點：管理二館MB520教室

演講摘要：

受到醫療處置與飛機維修等應用的啟發，我們研究一類排程問題，其中每個工作由兩道作業組成：測試與處理。每個工作的測試時間已知，但處理時間必須在測試完成後才會得知。透過競爭分析，我們探討在單機環境下，旨在最小化 𝑛個工作的總完工時間的演算法。

我們的主要成果是一項新的分析，顯示自然的 1-SORT 演算法可達到至多 1.861 的競爭比。在所有測試時間相同的特殊情形下，我們進一步證明一個簡單的閾值式演算法可達到至多 1.585 的競爭比。我們也建立了一項下界：即便在測試時間一致的情況下，任何決定性演算法的競爭比都不可能優於。 本研究為Konstantinos Dogeas 和 Thomas Erlebach 的合作成果。

演講性質：學術研究專題

歡迎聽講