通过并行分组最小化的作业调度

Question

我有一个扭曲的工作计划问题-最小化约束。任务是-我有很多工作，每个工作对其他工作都有各种依赖性，没有周期。这些作业也具有类别，如果它们属于同一类别，则可以免费并行运行。因此，我想对作业进行排序，以使每个作业都依赖于其依赖项，但要按照它们按类别分组的方式进行排列（以并行运行许多作业），以最大程度地减少我运行的串行作业的数量。也就是说，相同类别的相邻作业被计为单个串行作业。

我知道我可以进行拓扑排序以处理依赖关系排序。我曾尝试在包含每个作业类别的子图中使用图形着色，但是遇到类别间依赖冲突的问题。更具体地说，当我必须决定要对两个或更多对作业中的哪个进行分组时。我可以蛮力地尝试，并且可以尝试在搜索空间中随机漫步，但我希望有一些更聪明的东西。前者在最坏的情况下呈指数爆炸，不能保证后者是最优的。

要使事情成规模，一次可以安排多达几十万个工作，也许有几百种工作。

我偶然发现了许多优化方法，例如创建依赖关系图，拆分为连接的组件以及独立解决每个子问题并合并。我还意识到，为每种类别上色的颜色数量有一个下限，但不确定在提前退出条件之外如何使用该颜色。

是否有更好的方法来查找订单或职位，以最大化类别的此“分组”，以最大程度地减少连续职位的总数？

Answer 1

不确定这是否有帮助，但是除了瞄准算法之外，还可以开发优化模型并让求解器完成工作。

混合整数编程模型可能看起来像：

这个想法是，我们使总的制造时间或最新工作的完成时间最小化。这将自动尝试将相同类别的作业分组在一起（以允许并行处理）。

我为50个工作和5个类别创建了一些随机数据。数据集包括一些到期日和一些优先约束。

----     28 SET j  jobs

job1 ,    job2 ,    job3 ,    job4 ,    job5 ,    job6 ,    job7 ,    job8 ,    job9 ,    job10,    job11,    job12
job13,    job14,    job15,    job16,    job17,    job18,    job19,    job20,    job21,    job22,    job23,    job24
job25,    job26,    job27,    job28,    job29,    job30,    job31,    job32,    job33,    job34,    job35,    job36
job37,    job38,    job39,    job40,    job41,    job42,    job43,    job44,    job45,    job46,    job47,    job48
job49,    job50


----     28 SET c  category

cat1,    cat2,    cat3,    cat4,    cat5


----     28 SET jc  job-category mapping

             cat1        cat2        cat3        cat4        cat5

job1          YES
job2                                                          YES
job3                                  YES
job4                      YES
job5                      YES
job6                      YES
job7                      YES
job8                                                          YES
job9          YES
job10                                 YES
job11                                                         YES
job12                                 YES
job13                                                         YES
job14                                             YES
job15         YES
job16                                             YES
job17         YES
job18                     YES
job19                                             YES
job20                                 YES
job21                     YES
job22                     YES
job23         YES
job24         YES
job25                                 YES
job26                                                         YES
job27                     YES
job28                                             YES
job29                                             YES
job30                     YES
job31         YES
job32                                 YES
job33         YES
job34                                                         YES
job35                     YES
job36                     YES
job37                                 YES
job38                                             YES
job39                                             YES
job40                                 YES
job41                                 YES
job42         YES
job43                     YES
job44         YES
job45                     YES
job46         YES
job47                                             YES
job48                                 YES
job49                                             YES
job50                     YES


----     28 PARAMETER length  job duration

job1  11.611,    job2  12.558,    job3  11.274,    job4   7.839,    job5   5.864,    job6   6.025,    job7  11.413
job8  10.453,    job9   5.315,    job10 12.924,    job11  5.728,    job12  6.757,    job13 10.256,    job14 12.502
job15  6.781,    job16  5.341,    job17 10.851,    job18 11.212,    job19  8.894,    job20  8.587,    job21  7.430
job22  7.464,    job23  6.305,    job24 14.334,    job25  8.799,    job26 12.834,    job27  8.000,    job28  6.255
job29 12.489,    job30  5.692,    job31  7.020,    job32  5.051,    job33  7.696,    job34  9.999,    job35  6.513
job36  6.742,    job37  8.306,    job38  8.169,    job39  8.221,    job40 14.640,    job41 14.936,    job42  8.699
job43  8.729,    job44 12.720,    job45  8.967,    job46 14.131,    job47  6.196,    job48 12.355,    job49  5.554
job50 10.763


----     28 SET before  dependencies

             job3        job9       job13       job21       job23       job27       job32       job41       job42

job1          YES
job3                      YES
job4                                  YES
job8                                                                      YES
job9                                              YES         YES
job12                                                         YES
job14                                                                                             YES
job21                                                                     YES
job26                                                                                                         YES
job31                                                                                 YES

    +       job43       job46       job48

job10                     YES         YES
job11         YES


----     28 PARAMETER due  some jobs have a due date

job16 50.756,    job19 57.757,    job20 58.797,    job25 74.443,    job29 65.605,    job32 55.928,    job50 58.012

解决方案看起来像：

此模型（具有这个特定的数据集）在大约30秒内（使用Cplex）解决了。当然，应该指出的是，通常，这些模型可能难以求解为最优。