algorithm - 尝试获得工作调度贪心算法的直觉

Question

我有以下场景:(因为我不知道显示 LaTeX 的方法，这里是屏幕截图)

我在概念化这里发生的事情时遇到了一些麻烦。如果我要对此进行编程，我可能会尝试将其构建为某种堆，其中每个节点代表一个工作人员，从最早到最新，然后在其上运行 Prim 的/Kruskal 的算法。我不知道我的想法是否正确，但我需要充实我对这个问题的理解，以便我可以执行以下操作:

• 详细描述贪婪的选择
• 表明如果存在未做出贪心选择的最优解，则可以进行交换以符合贪心选择
• 了解如何实现贪心算法及其运行时间

那么我应该把这个想法带到哪里去呢？

Answer 1

这个问题在本质上与“Roster Scheduling problems”非常相似。将委员会想象成一组“主管”，只要有 worker 在场，您就希望有一个主管在场。在这种情况下，主管与 worker 来自同一组。

这里有一些建模想法和一个整数规划公式。

时间切片的想法

起初这听起来像是个坏主意，但在实践中效果非常好。我们将创建很多“时刻”T _i，从第一个类次的开始时间到最后一个类次的结束时间。有时想想会有所帮助 T1, T2, T3....TN 作为时间瞬间(比方说)相隔五分钟。对于每个 Ti，至少有一个 worker 正在轮类工作。因此，该时间点已被覆盖(覆盖意味着至少有一名委员会成员也在 Ti 时间工作。)

我们真的只需要担心 2n 时刻:每个 n worker 的开始和结束时间。

覆盖属性要求

对于每个时间点 Ti，我们都需要委员会的一名工作人员在场。

令 w1, w2...wn 为 worker ，按他们的开始时间 s_i 排序。 ( worker w1 开始最早的类次， worker wn 开始最后一个类次。)

引入一个新的 Indicator 变量( bool 值):

Y_i = 1 if worker i is part of the committeee
Y_i = 0 otherwise.

可视化

现在想想一个 0-1 矩阵，其中行是 SORTED workers，列是时间点...

构建时间- worker 矩阵 (0/1)

    t1 t2 t3 t4 t5 t6 ...          tN
------------------------------------------- 
w1   1  1
w2   1  1
w3      1  1  1
w4         1  1  1  
...
...
wn                               1 1 1 1
------------------------------------------- 
Total 2 4 3 ...              ... 1 2 4 5

所以问题是要确保对于每个列，至少选择 1 名 worker 成为委员会的一员。总数显示每个时间点委员会的候选人人数。

基于整数规划的公式

Objective: Minimize Sum(Y_i)

Subject to:

Y1 + Y2       >= 1 # coverage for time t1
Y1 + Y2 + Y3  >= 1 # coverage for time t2
...

更一般地，约束是:

# Set Covering constraint for time T_i
Sum over all worker i's that are working at time t_i (Y_i) >= 1 

Y_i Binary for all i's

预处理

这个整数程序，如果在没有预处理的情况下尝试，可能会非常困难，最终会使求解器窒息。但在实践中，有相当多的预处理想法可以提供极大的帮助。

1. 进行任何强制分配。 (如果有一个时刻只有一个 工作人员工作，该工作人员必须加入委员会 ∈ C)
2. 分解成好的子问题。看看时间 worker 矩阵。如果里面有漂亮的“矩形”可以不用 影响任何其他时间瞬间，那么这是一个完全独立的 要解决的子问题。使求解器运行得更快。
3. 相同的类次 - 如果许多员工的开始和结束时间完全相同，那么您可以简单地选择其中的任何一个(例如， 字典顺序第一个 worker ，WLOG)并从中删除所有其他 worker 考虑。 (在现实生活中产生很大的不同。)
4. 主导轮类:如果一名 worker 比其他任何 worker 先开始并晚于其他任何 worker ，则“主导” worker 可以留下来，所有 可以从 C 的考虑中删除“受支配”的 worker 。
5. 可以融合时间 worker 矩阵中所有相同的行(和列)。您只需要保留其中一个。 (重复数据删除)

您可以将其放入 IP 求解器(CPLEX、Excel、lp_solve 等)中，如果问题大小不是问题，您将得到一个解决方案。

希望其中一些想法有所帮助。