找到無資源插槽的算法

我正在爲一家工廠設計一個項目管理應用程序。該應用程序預計將生成草案項目計劃。要計劃任務，應用程序應該檢查三個條件：找到無資源插槽的算法

任務相關性 - 不要啓動前，
機器的可用性，並
輪班工作小時

我跟蹤機訂婚machine_allocations表格：

machine_allocations 
+------------+--------------+-----------------+---------------+ 
| machine_id | operation_id | start_timestamp | end_timestamp | 
+------------+--------------+-----------------+---------------+

班次按照模式。

現在，找到最早可能日期時間的操作我想到一個功能：

function earliest_slot($machine_id, $for_duration, $no_sooner_than) { 
    // pseudo code 
    1. get records for the machine in question for after $no_sooner_than 
    2. put start and end timestamps into $unavailable array 
    3. add non-working times as new elements to the array 
    4. in a loop find timeslots which are not in the array 
    5. if a timeslot is found which is equal to or bigger than $for_duration, return that 
}

我的問題是，這是一個好的方法嗎？有沒有簡單的方法來做到這一點？

來源

2011-08-27 Majid Fouladpour

一次找到一個操作的最早日期時間可能不會給你最好的結果。考慮操作A長時間使用機器1的示例，操作B短時間使用機器1並且操作C短時間使用機器2，但操作C必須在B後完成。

在這種情況下，最好在機器1的A之前安排B，但是你的方法不會達到這個目的。當然，編寫和使用軟件來管理這些將比您建議的更困難，所以您需要決定是否值得付出額外的努力。

看一看Scheduling,Job Shop Scheduling和Scheduling algorithm。

首先，您需要考慮您可以收集哪些關於任務的信息（例如依賴關係，優先級，截止日期），然後決定如何最好地將它們放在一起。

你可能會發現，像你提出的方法在你的情況下足夠好。我對你提出的算法的補充是對現有機器操作列表進行排序，以便更快地搜索它們，也就是說，只要找到適合操作的時間，就可以停下來，因爲它保證了最早的時間。

一個相對簡單的擴展將是一個優先級系統，它允許您向前推進優先級較低的任務（也可能需要調整其依賴關係），但更復雜的算法會一次考慮多個任務並嘗試優化結果。最後，它歸結爲適合您的具體問題。

來源

2011-08-28 01:50:04 Artelius

謝謝你的建議。我知道這樣制定的計劃不會是最佳的，這就是爲什麼我稱之爲「草案計劃」。我不向客戶承諾，它可以讓他們擺脫手工調整時間表的需要。所以我正在接近它的方式來保持複雜性。因此，對於我計劃提供的*有限效用值*，您是否發現該算法是最簡單的？ –

我認爲這個算法很簡單*對它沒有任何影響。如果你有一個簡單的解決方案，不要浪費時間尋找最簡單的解決方案，尤其是如果你的需求可能會改變...... – Artelius

*非常好的建議*。你是對的 - 我最好去實施它！ - 我會記得最後一個（我保證;））。 –

這取決於您何時計劃工作。如果在開始工作之前，機器可能會通過Branch & Bound算法或類似的東西（mayby動態編程）。如果在機器工作時必須計劃工作，並且您無法確定將執行哪些工作，那麼爲了獲得最佳解決方案您無法計數（以及我無法考慮它）。 Mayby將最近一次的工作放在機器上最小時間？ Mayby是Ford-Bellmas alg的一個動態版本（如果你有幾層生產）。很難說。我會做幾個認識，並確定女巫是最好的。你可以寫一篇關於這方面的文章:)

來源

2011-08-27 23:26:05

我想你沒有正確地閱讀這個問題。問題很具體 - 如何最好地實現'early_slot'函數。 – svick

@neosatan謝謝。每項任務將在第一時間計劃;和*可能*在這裏意味着我們應該滿足三個條件：（i）在購買之前不要吃冰激凌，（ii）我們需要的機器在任務期間應該是免費的，（iii）不要將任務設置爲非工作時間。 –

@svick我正確地閱讀它，但是當它發揮作用時，所有可以獲得的信息都非常重要。問題在我看來是不準確的，所以我在這裏給出了一個普遍的答案。 Artelius提出了非常好的答案，我想獲得更多信息。 –

找到無資源插槽的算法

回答

相關問題