最適合的調度算法

Question

我正在寫一個編程難度很大的調度程序。有幾個事件，每個都有多個會議時間。我需要找到一個安排會議時間，使每個時間表包含任何給定的事件一次，使用每個事件的多個會議時間之一。

顯然我可以使用蠻力，但這很少是最好的解決方案。我猜這是一個相對基本的計算機科學問題，一旦我能夠開始參加計算機科學課程，我將會了解到這個問題。與此同時，我更喜歡任何可以閱讀的鏈接，甚至只是一個可以讓Google知名的鏈接。

Answer 1

我認爲你應該使用遺傳算法，因爲：

• 它是最適合於大問題的情況。
• 它產生於
• 您可以通過調整適應的懲罰不能滿足那些喜好&輕鬆指定約束不準確答案的價格（不是最終的最好的）降低時間複雜度。
• 您可以指定程序執行的時間限制。

• 溶液的質量取決於你打算多少時間花在解決方案..

  Genetic Algorithms Definition

  Genetic Algorithms Tutorial

  Class scheduling project with GA

Answer 2

您的問題描述並不完全清楚，但如果您所要做的只是找到一個沒有重疊事件的計劃，那麼這是一個直接的bipartite matching問題。

您有兩組節點：事件和時間。從每個事件到每個可能的會議時間畫一條邊。然後，您可以使用augmented paths有效地構建匹配（節點之間最大可能的一組邊）。這是有效的，因爲你總是可以將二部圖轉換爲等價的流圖。

這樣做的代碼示例是BIM。標準圖形庫，如GOBLIN和NetworkX也有雙邊匹配的實現。

Answer 3

這聽起來像這可能是一個dynamic programming解決方案，特別是類似於interval scheduling問題的一個很好的候選人。

對於區間調度問題，有一些視覺here具體，這可能會使概念更清晰。 Here是一個關於整體動態編程的好教程。

Answer 4

有幾種方法可以做到這

一種方法是做約束編程。這是feanor建議的動態編程的特例。使用可以爲你做邊界和分支的專門庫是很有幫助的。 （谷歌的「gecode」或「彗星在線」來找到庫）

如果你是數學上的傾向，那麼你也可以使用整數編程來解決這個問題。這裏的基本思想是將你的問題轉化爲一組線性不等式。 （谷歌的「整數編程調度」，以找到許多現實生活中的例子和谷歌「算盤COIN-OR」爲一個有用的庫）

我的猜測是約束編程是最簡單的方法，但整數編程是有用的，如果你想要在某個時候在你的問題中包含實際變量。