打包时隙的算法

Question

我有一组带有开始时间和结束时间的事件。我想将它们呈现为一系列没有重叠的行中的长框，就像这样

00:00    01:00    02:00    03:00    04:00    05:00    06:00    07:00    08:00
--|--------|--------|--------|--------|--------|--------|--------|--------|--
      AAAAAAAAAAAA  BBBBBB        CCCCCCCCCCCCCCCCCCCC       DDDDDDDDDDDD
--|--------|--------|--------|--------|--------|--------|--------|--------|--
         EEEEEEEEEEEEEE      FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
--|--------|--------|--------|--------|--------|--------|--------|--------|--
            GGGGGGGGGGGGGGGGGGG           HHHHHHHH        IIIIIIIIIIIII
--|--------|--------|--------|--------|--------|--------|--------|--------|--

将任何特定框分配给任何特定行并不重要。我想要的是一种将这些框打包成最少行数的算法。

是否有已知的算法？

Answer 1

The International Timetabling Competition 2007 had a lesson scheduling track and exam scheduling track. Many researchers participated in that competition. Lots of heuristics and metaheuristics were tried, but in the end the local search metaheuristics (such as Tabu Search and Simulated Annealing) clearly beat other algorithms (such as genetic algorithms).

Take a look at the 2 open source frameworks used by some of the finalists:

JBoss OptaPlanner (Java, open source) Unitime (Java, open source) - more for universities

-- 杰弗里德斯梅特:Algorithm for creating a school timetable

引用:

• http://en.wikipedia.org/wiki/Simulated_annealing
• http://en.wikipedia.org/wiki/Tabu_search