算法:使用 GA 优化生产计划

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'](按此顺序在机器 1 上使用 EKM，在机器 2 上使用 IFB，等等)

我在测量适应度方面没有困难(我的目标是最小化完工时间)但是当涉及到交叉时，这就复杂得多(看起来这是遗传算法的难点)。

如果我有两个 parent :['EKM', 'IFB', 'GLD', 'HAJC'] 和 ['ICFM', 'HLK', 'DJE', 'BGA']制造产品的机器(例如，对于 A，两者都是 M3)并随机选择要选择的机器。我用同样的方法选择它的制作顺序(对于 A，它将是父级 1 的位置 2 和父级 2 的位置 3)并随机选择。

我非常确信我在这里犯了一个错误，但找不到找到好的染色体编码/交叉策略的方法(我的糟糕结果表明如此)。

有比我更了解 GA 的人可以提供建议吗？

非常感谢!