预约分配算法

Question

我正在寻找分配资源预留的算法。这可能是与可用客房相匹配的酒店预订-与可用会议室相匹配的会议预订-与餐桌匹配的餐厅预订。

他们的共同点是：

• 每个预订都有一个特定的不可更改的开始和结束时间。
• 在开始时间之前，每个预约都不会绑定到特定的资源。
• 可以有可变数量的资源。
• 每次出现新的预约时，该算法至少应该能够检查是否可能匹配某个资源。

到目前为止，我主要是研究遗传算法来解决这个问题，但是我很难将问题编码到染色体上。

任何关于算法的想法都是受欢迎的，而且算法只能找到“好”的解决方案，而不是最优的解决方案。

Answer 1

此文章包括各种时间操作，以检查是否有空闲、重叠和相交的时间段。您可以轻松地将这些类与业务对象组合在一起：

// ----------------------------------------------------------------------
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

Answer 2

看看禁忌搜索和模拟退火作为遗传算法的替代品。

这与滴水规划师 (java，开放源码)中的PAS示例非常相似，后者是关于在各种约束条件下将患者安排在医院病床上的。请参阅滑梯和下一张幻灯片。

Answer 3

使用稀疏矩阵。

就酒店客房而言，预订

1. 斧头，你有房间
2. 斧头，你有日期
3. 您有时间间隔，指向预订数据对象。

所有这些(1,2,3)都可以表示为一个列表或3个哈希表。

示例：

x = room 10
y = date 2021/4/3
z = time from 10am till 9pm

然后添加所有用于插入、删除、冲突等保留逻辑的方法。

可以证明，通过这种结构，您可以轻松地通过遍历矩阵来管理任何预订。