預約分配算法

我正在尋找分配預留資源的算法。這可能是酒店預訂與可用客房相匹配 - 會議預訂與可用會議室相匹配 - 與餐桌相匹配的餐廳預訂。預約分配算法

他們有什麼共同之處：

每個預約有一個特定的不可改變的開始和結束時間。
每個預留在開始時間之前未綁定到特定資源。
可以有可變數量的資源。
每次有新的預約時，算法至少應該能夠檢查是否可以匹配資源。

到目前爲止，我主要着眼於解決問題的遺傳算法方法，但是我在編碼問題時遇到了麻煩。

對此算法的任何想法都是值得歡迎的，也是隻有找到一個「好」解決方案而不是最優解決方案的算法。

來源

2011-01-14 Lemmedaskeren

這是一個在線問題（您一次只能收到一個請求），還是在所有預留之前？ – EmeryBerger 2011-01-14 12:54:54

這將是當時的一個要求。但是保留在開始時間之前不必與資源綁定。因此，在添加新預訂時，會有捆綁預訂並且不會捆綁預訂。 – Lemmedaskeren 2011-01-14 12:58:51

看看禁忌搜索和模擬退火作爲遺傳算法的替代品。

這與Drools Planner（java，開放源代碼）中的PAS示例非常相似，該示例將患者安排到各種約束條件下的醫院病牀中。請參閱the slide和下一張幻燈片。

來源

2011-03-09 11:53:04

這article包括各種時間操作來檢查自由，重疊和相交時間段。您可以輕鬆地將此類與您的業務對象結合起來：

// ---------------------------------------------------------------------- 
public void TimeRangeSample() 
{ 
    // --- time range 1 --- 
    TimeRange timeRange1 = new TimeRange(
    new DateTime(2011, 2, 22, 14, 0, 0), 
    new DateTime(2011, 2, 22, 18, 0, 0)); 
    Console.WriteLine("TimeRange1: " + timeRange1); 
    // > TimeRange1: 22.02.2011 14:00:00 - 18:00:00 | 04:00:00 

    // --- time range 2 --- 
    TimeRange timeRange2 = new TimeRange(
    new DateTime(2011, 2, 22, 15, 0, 0), 
    new TimeSpan(2, 0, 0)); 
    Console.WriteLine("TimeRange2: " + timeRange2); 
    // > TimeRange2: 22.02.2011 15:00:00 - 17:00:00 | 02:00:00 

    // --- time range 3 --- 
    TimeRange timeRange3 = new TimeRange(
    new DateTime(2011, 2, 22, 16, 0, 0), 
    new DateTime(2011, 2, 22, 21, 0, 0)); 
    Console.WriteLine("TimeRange3: " + timeRange3); 
    // > TimeRange3: 22.02.2011 16:00:00 - 21:00:00 | 05:00:00 

    // --- relation --- 
    Console.WriteLine("TimeRange1.GetRelation(TimeRange2): " + 
        timeRange1.GetRelation(timeRange2)); 
    // > TimeRange1.GetRelation(TimeRange2): Enclosing 
    Console.WriteLine("TimeRange1.GetRelation(TimeRange3): " + 
        timeRange1.GetRelation(timeRange3)); 
    // > TimeRange1.GetRelation(TimeRange3): EndInside 
    Console.WriteLine("TimeRange3.GetRelation(TimeRange2): " + 
        timeRange3.GetRelation(timeRange2)); 
    // > TimeRange3.GetRelation(TimeRange2): StartInside 

    // --- intersection --- 
    Console.WriteLine("TimeRange1.GetIntersection(TimeRange2): " + 
        timeRange1.GetIntersection(timeRange2)); 
    // > TimeRange1.GetIntersection(TimeRange2): 
    //    22.02.2011 15:00:00 - 17:00:00 | 02:00:00 
    Console.WriteLine("TimeRange1.GetIntersection(TimeRange3): " + 
        timeRange1.GetIntersection(timeRange3)); 
    // > TimeRange1.GetIntersection(TimeRange3): 
    //    22.02.2011 16:00:00 - 18:00:00 | 02:00:00 
    Console.WriteLine("TimeRange3.GetIntersection(TimeRange2): " + 
        timeRange3.GetIntersection(timeRange2)); 
    // > TimeRange3.GetIntersection(TimeRange2): 
    //    22.02.2011 16:00:00 - 17:00:00 | 01:00:00 
} // TimeRangeSample

來源

2011-04-06 06:37:37 Jani

預約分配算法

回答

相關問題