時間表問題

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.