調度應用程序中的約束圖轉換

我正在開發一個交互式作業調度應用程序。給定一組具有相應容量/可用性配置文件的資源，一組要在這些資源上執行的作業以及一組確定作業順序的約束條件以及我想讓用戶手動移動的作業的最早/最近開始/結束時間周圍的工作。本質上，我希望用戶能夠「抓取」作業網絡的一個節點，並及時拖拽該作業網絡，而不會違反任何約束條件。調度應用程序中的約束圖轉換

該圖顯示了一個簡單的示例配置。最後的三角形工作表示所有工作的最後完成時間，工作之間的連接線對工作施加一個訂單，灰色/綠色條表示資源的可用性和負載。

您可以拖動任何作業來壓縮計劃。請注意，由於容量配置文件不同，作業的長度會發生變化。

我已經實現了一個ad-hock算法，它可以工作。但是，仍然會有失敗並違反一些限制的情況。然而，由於作業車間調度是一個經過深入研究的領域，有很多算法和啓發式方法來尋找一般NP難題的最佳（或較好）解決方案 - 我認爲解決方案應該適用於我的更容易的子集。我研究了約束編程主題，甚至基於物理學的解決方案（通過靜態關節連接的剛體），但到目前爲止找不到合適的東西。任何指針/提示/提示/搜索關鍵詞對我來說？

來源

2009-11-20 BuschnicK

我完全不明白這個問題，對不起。爲什麼工作的長度會改變？當你說搶和移動節點時，你是什麼意思？工作是一個節點嗎？謝謝。 – 2010-01-04 01:14:56

上面顯示的網絡可以通過交互式拖放操作進行修改。點擊一個作業（圖中標記爲「作業」的節點）並將其移動到別處。由於作業持續時間取決於可用容量（灰色/綠色條），因此作業長度在移動時會發生變化。 – BuschnicK 2010-01-04 09:47:38

我也不明白。是否需要其他工作來滿足特定的工作運動 - 比如說，如果您將job032左移，job029和job031以某種方式重新安排自己，以便job031在job032啓動之前仍然完成？如果是這樣，你需要告訴我們我們可以做的其他工作 - 及時移動，改變資源等？是否簡單地分享資源（即，在同一資源上運行的兩個單元工作作業需要2個單位時間才能完成）？ – 2010-01-05 06:21:59

您可能可以改變Waltz約束傳播算法來處理變化的約束，以快速找出給定的解決方案是否有效。我沒有一個參考出手，但是這可能意味着你在正確的方向： http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-41C30BN-5&_user=809099&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1102030809&_rerunOrigin=google&_acct=C000043939&_version=1&_urlVersion=0&_userid=809099&md5=696143716f0d363581a1805b34ae32d9

來源

2009-11-20 10:56:15

我強烈建議你看看Mozart Oz，如果您的問題只涉及整數。 Oz對約束規範，推理和優化有限域有極好的支持。你的情況通常你會做以下幾點：

指定聲明方式的限制。在這裏，你可以指定所有的變量和它們的域（比如說V1：1＃100，意思是 V1變量可以取1--100範圍內的值）。一些變量可能直接具有值，例如V1：99。此外，您可以指定變量的所有約束。
向系統詢問解決方案：要麼滿足約束條件的任何解決方案，要麼尋求最佳解決方案。然後你會在用戶界面上顯示這個解決方案。
假設用戶更改變量的值，可能是任務的開始時間。現在，您可以轉到步驟1將問題發佈到 Oz求解器。這一次，解決問題的可能性不會像早些時候那麼多，因爲所有的變量都已經實例化了。

可能是用戶選擇了不一致的值。在那個的情況下，求解器返回null。然後，您可以將UI帶到早期的解決方案。

如果奧茲適合您的需要和你喜歡的語言，那麼你可能要寫約束求解器作爲監聽套接字上的服務器。這樣，您可以將約束求解器與您的其他代碼（包括UI）分開。

希望這會有所幫助。

來源

2009-12-31 10:23:24 prp

感謝您的指針。我做了一個快速掃描，我對此有點懷疑：1）學習一門新的語言，要求我重申/重新構造問題2）Mozart Oz東西看起來像尋找最佳工作時間表的啓發式優化框架。我只是在尋找能夠在手動編輯網絡時滿足所有約束條件的人。3）實時交互式性能？ – BuschnicK 2010-01-04 10:00:26

1）我想，這是一個有效的擔憂。 2）你可以做「約束滿足」。只有您想要，您纔可以進行優化。請看一下「發送更多錢」的例子。 3）對於約束滿足（不是優化），交互性能應該不成問題。 – prp 2010-01-05 09:21:16

你有沒有考慮過使用整數線性規劃引擎（如lp_solve）？這非常適合調度應用程序。

來源

2010-01-26 16:55:49 vicatcu

我會贊成約束規劃的投票有以下幾個原因：

1）CP會迅速告訴你，如果沒有時間表，satifies您的約束

2）這樣看來，你想給你使用一個可行的解決方案開始，但允許他們操縱工作，以改善解決方案。 CP也擅長這一點。

3）一個MILP方法通常很複雜，很難制定，你必須人爲地創建一個目標函數。

4）對於有經驗的程序員來說，CP並不是那麼難學，相比運營研究人員（比如我），它確實來自計算機科學界更多。

祝你好運。

來源

2010-02-02 16:32:42 Grembo

調度應用程序中的約束圖轉換

回答

相關問題