在固定時間窗口上受固定時間窗限制的可移動時間窗

作業是由客戶提出要求。客戶限定時間（例如：「你可以在8:00，終點爲13:00開始）內部算法會產生一個估計的執行時間，這項工作（即使這個職位有5個小時，這傢伙。這意味着傢伙可以從8:00到10:00或從10:30到12:30完成這項工作。

在一個工作日的時間窗口（8 ：00至17:00），我們會嘗試將工作分配給一個清單，然後將這個清單分配給一個工作人員，這裏有多個清單和工作人員

清單上唯一的約束就是我們可以'同時執行兩個任務（但是，例如，您可以有一個J1（8:00至12:00，執行時間1小時）和J2（8:00至12:00，執行時間2小時）這是可行的。由於J1可從8:00進行到9:00，然後J2可從9:00進行到11:00）

在JavaScript中，我的對象有一個開始時間，結束時間，估計持續時間（使用有用和強大的moment.js）。

名單是簡單地用是否可以添加任務，則返回true專門推一個數組。

exemple 這裏是一個例子，我們有他們的紅色預計執行時間的棕色作業，他們在一天的時間窗口（黑色）。最上面的工作是最後一個插入，要做的事情是試圖知道作業列表是否仍然可行。所以這裏需要做的是在稍後的兩個其他任務之間滑動（綠色箭頭）執行時間。首先，我試圖找到一種方法來了解是否可以在作業列表中插入作業。

然後我做了一個算法，其中執行時間總是ASAP在作業窗口時間，但我想我可以改善這一點。

是否有滿足約束條件，並允許在列表中插入一個最大的就業有道什麼建議嗎？

來源

2016-02-02 charlitoti

我建議你嘗試想一些解決方案第一，在紙上或什麼的，以後，如果你找不到任何，嘗試一些研究。

提示：嘗試對事物進行排序，看看它是否有助於做出決定。

這是一個經典算法問題，您應該查找Scheduling Algorithms，並查看一些方法。檢查了這一點。 http://www.ctl.ua.edu/math103/scheduling/scheduling_algorithms.htm

來源

2016-02-02 15:26:27 UlyssesR

下面是一個遞歸示例（可以迭代爲堆棧），其中時間軸的位表示和半小時的持續時間。它耗盡了所有的可能性，如果沒有合適的話就會提前退出（當然，如果有合適的話，你可以輸出第一個並退出，而不是像示例中那樣全部返回）。

function toBin(start,duration){ 
    return ((1 << duration) - 1) << (start - 8) * 2 
} 

function f(i,list,timeline,jobs){ 
    if (i == jobs.length){ 
    console.log(list); 
    } else { 
    for (var j=jobs[i].start; j+jobs[i].exec/2<=jobs[i].end; j+=0.5){ 
     var bin = toBin(j,jobs[i].exec) 
     if (!(bin & timeline)){ 
     var _list = list.slice(); 
     _list.push("("+i+","+j+")"); 
     f(i + 1,_list,timeline | bin,jobs); 
     } 
    } 
    } 
}

輸出：

var example = [{start:8, end:12, exec:2}, {start:8, end:12, exec:4}] 

f(0,[],0,example); 

/* 
(job index, start time) 
(0,8),(1,9) 
(0,8),(1,9.5) 
(0,8),(1,10) 
(0,8.5),(1,9.5) 
(0,8.5),(1,10) 
(0,9),(1,10) 
(0,10),(1,8) 
(0,10.5),(1,8) 
(0,10.5),(1,8.5) 
(0,11),(1,8) 
(0,11),(1,8.5) 
(0,11),(1,9) 
*/

來源

2016-02-03 04:13:49

在固定時間窗口上受固定時間窗限制的可移動時間窗

回答

相關問題