算法:用遗传算法优化生产调度

Question

我被困在一个超出我的智商能力的问题中，因此我在这里写信寻求一些建议。基本上，这似乎是一个相当简单的案例。

我有一系列的产品：

​

​

我有4台并行机器，可以制作每个产品(产品之间没有依赖关系)：

M1

M2

M3

M4

每台机器都可以运行24/7 ，但需要员工在场才能启动每一种新产品的生产。

例如，一个简单的问题是避免在晚上(而没有员工重新启动生产)或周末停止生产。

如果C产品的生产持续时间为2天，我不应该在周四下午开始生产，因为生产将在周六上午结束，而且在员工周一早上返回之前，机器不会开始新的生产。

首先，我尝试了一种蛮力方法(不是很微妙)，尝试了所有可能的组合，但我很快发现处理时间正在爆炸:)

然后我决定做一个线性规划的解决方案，首先把最紧迫的工作放在第一次，每次都选择最好的机器，然后对每一个产品都这样做。

我得到了一些结果，但显然不是最好的。因此，我为我的研究寻求好的建议。我试着看“蚁群”优化或“遗传算法”，但我面临的问题是，我有可变的空闲时间取决于我的任务结束时间。

Answer 1

多亏了@tobias_k，我一直在为我的调度问题探索遗传算法。

我认为他们很有前途，开始写我的染色体测序:给定的产品(A，B，C，D，E，F，G，H，I，J，K，M)和机器(M1，M2，M3，M4)可能的编码是'EKM', 'IFB', 'GLD', 'HAJC'。

我没有困难衡量适合度(我的目标是最小化制造)，但当涉及到交叉，这是更复杂的事情(看起来，这是遗传算法的困难部分)。

如果我有两个父母：“EKM”、“IFB”、“GLD”、“HAJC”和“ICFM”、“HLK”、“DJE”、“BGA”，我实际上是在查看制造产品的机器(例如，A在这两种机器上都是M3 )，并随机选择选择哪一台。我也是这样做的，选择它的顺序(对于A，它将是位置2在父母1和位置3在父母2)和随机选择。

我很确信我在这里犯了一个错误，但我无法找到一个很好的染色体编码/交叉策略(我的坏结果表明了这一点)。

有比我更多的GA知识的人能帮上忙吗？

非常感谢！