時間表問題

ealin relation Timetablin

時間表問題(Time Table Problem,簡稱TTP)是運籌學領域中組合最佳化問題之一。它有廣泛的套用背景。如護士工作時間表、各種體育賽事安排時間表、火車時刻表、各類院校每學期的考試時間表、課程表等等。Wren [1] 將時間表定義為滿足約束條件的安排方案,即將關於所研究對象的特定資源安排到一定時空中,並使其儘可能多的滿足一系列目標約束。Burke [2] 稱TTP 簡單地說就是將一系列的事件安排到特定的時域點上,使得同一空間(容量充足)、同一時間只允許一個事件占用。在簡化情況下如果有m 個事件安排到n 個時域點上,則共有n的m次方種安排方案;因在約束條件下每一種方案都有其適用的約束範圍,故只有極少數方案可以滿足全部約束條件。求解TTP 就是尋找滿足全部約束條件的最優安排方案。 最初人們是通過手工方式編排TTP,但這種方式費時、費力,而且隨著時代的進步關於各類TTP 的信息量大幅度增加,手工制表已經很難找到滿意的結果,Even [3] 等人已證明TTP 是一個具有NP 難度的問題。因此求解TTP引起了各領域專家的極大興趣,並對其進行了深入的研究,不斷的將一些現代最佳化算法用於求解該類問題,如神經網路技術(Neural Networks,簡稱NN)、專家系統(Expert System,簡稱ES)、模擬退火算法(Simulated Annealing,簡稱SA)、進化計算(Evolutionary Computation,簡稱EC)等等。
參考文獻:
1. Wren A. Scheduling, timetabling and roster a special relationship [J],Proceeding of the Practice and Theory of Automated Timetabling,Springer-Verlag LNCS, 1996, 1153: 46-76.
2. Burke E, Elliman D and WeAre R. Specialized recombination operators fortimetabling problems [J], T. C. Fogarty, Evolutionary Computing, AISBWorkshop Leed, UK. Selected Papers, Springer-Verlag, Berlin: 1995, 75-85.
3. Even S, Itai A and shamir A. On the complexity of timetable andmulti-commodity flow problems [J], SIAM Journal on Computing, 1976, 5(4):691-703.

相關詞條

熱門詞條

聯絡我們