堆叠事件/项目的算法

Question

我正在寻找构建一个伪甘特图,除了事件可以在同一条线上,只要它们不重叠,就像这样:

               M T W R F S U M T W R F S U M T W R F S U
Category 1:   |Event 1|     |Event 2| |------Event 3--|
                |---------Event 4-----------| |-Event 5-|

我正在寻找一种算法来有效地打包这些事件.我知道我可以使用事件的长度和开始日期来确定重叠,但我想有一些起点.

对于好奇,我正在考虑克服SharePoint 2007中的甘特图日历视图的限制.我们的用户喜欢该视图,但不希望每行一个任务.

Answer 1

我的第一次尝试是按开始时间/日期对任务进行排序.然后我会在他们的开始时间尚未被占用的第一行一次放置一个.我(根本)不确定是否会给出最佳结果(即,总是使用尽可能少的行数),但它至少应该是合理的一半.

然而,我越是想到它,我认为它实际上可能是最佳的.优化问题通常很困难,因为与项目数量相比,组合的数量增加得非常快.然而,在这种情况下,你并没有真正得到这样的组合爆炸,因为你不能重新排列项目 - 至少我假设它们的开始时间都是预设的,所以它们不能重新排列.

编辑:只是为了清楚:这里我假设这个问题仅涉及显示已经知道开始时间和持续时间的事件计划,因此优化只意味着将数据显示为"紧凑".我不是在谈论尝试创建计划本身(即,试图找出要安排的事件).根据所涉及的限制,这通常是一个更加困难的问题.只要您的唯一约束是任务间依赖关系,但是当您添加最大人力使用和受限资源(例如,任务X只能由人A,B或C执行,任务Y由B执行)时,这相当容易. ,C或D等),情况变得非常困难很快.