预约分配算法

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

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

这与Drools Planner （java，开源）中的 PAS 示例非常相似，该示例是关于将患者安排到具有各种约束的医院病床上。请参阅幻灯片和下一张幻灯片。