机器调度问题

Question

我有一个组合问题:

你有N个测试人员.

每个测试仪是M种不同类型之一.

每个测试仪都可以配置为使用P个不同配置中的一个..

你有很多产品需要测试,

每个产品只能在特定测试仪类型上测试,

每个产品只能由配置了特定配置的测试仪进行测试.一些配置可以应用于多个产品.任何测试人员都可以在生产过程中更改其配置,但测试人员配置上的每次更改都会产生额外的时间.每个批次的批量大小决定了它的测试时间Q.

现在我需要提出很多调度算法,以便完成所有批次测试的时间最短.

解决此类问题的最佳方法是什么？

Answer 1

它可以建模为作业车间问题 (JSP)，其设置时间为作业大小为 1。不幸的是，当作业数量 > 10 时，很难找到最佳值。

有许多免费的求解器实现，其中包含 Job-Shop 作为示例问题：如果您使用 C++，Gecode很好。如果您可以自由选择，ECLiPSe Prolog 包含 JSP 的源代码。

如果您可以找到一个好的解决方案（而不是最优解决方案），我建议使用贪婪算法（对于 JSP，贪婪算法给出的解决方案通常在最优解的 10% 以内 - 我对此有一些经验）。我要考虑一个并回到这里（问题是所谓的“设置时间限制”，即来自更改测试仪配置的限制）。