python - 使用 Python 实现利润最大化作业调度

Question

我有一个调度方案，其中每个时间段都有成本。我需要选择在 24 小时内成本最低的时间段。请参阅下面的日期设置示例。

开始时间 |结束时间 |费用

• 00:00 | 01:00 | $30
• 01:00 | 05:00 | $50
• 02:00 | 08:00 | $70
• 04:00 | 12:00 | 100 美元
• 08:00 | 11:00 | $60
• 10:00 | 14:00 | $50
• 13:00 | 17:00 | $90
• 13:00 | 20:00 | $120
• 16:00 | 23:00 | $80
• 18:00 | 22:00 | $60
• 19:00 | 20:00 | $50
• 21:00 | 23:00 | 20 美元

我想要的是一个 Python 解决方案，用于导出成本最低的时间段集，每个时间段不得重叠，并且它们的总和必须为 24 小时。

Answer 1

下面是一个示例，说明如何使用 MIP(混合整数规划)模型将其实现为集合分区问题。

我生成了以下随机数据:

----     14 PARAMETER data  input data

          start      length        cost

i1            2           5          47
i2           19           5          20
i3           11           2          38
i4            5           2          14
i5            5           8          40
i6            3          10          26
i7            6           3          68
i8           19           5          61
i9                       10          80
i10          10           4          37
i11          22           2          70
i12          12           7          78
i13          22           2          67
i14          17           7          35
i15           1           4          17
i16          13           4          19
i17           1           8          68
i18           4           9          59
i19          14           8          12
i20           8           6          82

根据这些数据，我们可以构建一个 bool 覆盖矩阵，指示项目 i 是否覆盖了时间 t。

----     14 PARAMETER cover  coverage of hours by items

            h00         h01         h02         h03         h04         h05         h06         h07         h08

i1                                    1           1           1           1           1
i4                                                                        1           1
i5                                                                        1           1           1           1
i6                                                1           1           1           1           1           1
i7                                                                                    1           1           1
i9            1           1           1           1           1           1           1           1           1
i15                       1           1           1           1
i17                       1           1           1           1           1           1           1           1
i18                                                           1           1           1           1           1
i20                                                                                                           1

  +         h09         h10         h11         h12         h13         h14         h15         h16         h17

i3                                    1           1
i5            1           1           1           1
i6            1           1           1           1
i9            1
i10                       1           1           1           1
i12                                               1           1           1           1           1           1
i14                                                                                                           1
i16                                                           1           1           1           1
i18           1           1           1           1
i19                                                                       1           1           1           1
i20           1           1           1           1           1

  +         h18         h19         h20         h21         h22         h23

i2                        1           1           1           1           1
i8                        1           1           1           1           1
i11                                                           1           1
i12           1
i13                                                           1           1
i14           1           1           1           1           1           1
i19           1           1           1           1

(注意:不打印零)

现在我们可以制定一个 MIP 模型:

当我们使用标准 MIP 求解器解决这个问题时，我们得到以下解决方案:

----     29 VARIABLE x.L  selected items

i9  1,    i10 1,    i13 1,    i19 1


----     29 VARIABLE cost.L                =          196  total cost

请注意，问题很可能是不可行的:我们不能用恰好一个项目覆盖每个小时。对于实际应用，保护我们自己免受这种情况的影响可能是有益的。例如。通过允许在解决方案中插入非常昂贵的“紧急项目”(假设我们有 24 个，每小时一个，成本非常高)。这将始终提供解决方案，您可以看到我们遇到问题的时间段。