机器调度问题
机器调度问题
提问于 2010-07-27 17:51:56
我有一个这样的组合问题：
给你N个测试者。
每个测试仪都是M种不同类型中的一种。
可以将每个测试仪配置为使用P个不同配置中的一个。。
你有很多产品要测试，
每个产品只能在特定类型的测试仪上进行测试。
每个产品只能由配置了特定配置的测试仪进行测试。某些配置可以应用于多个产品。任何测试人员都可以在生产过程中更改其配置，但每次更改测试人员配置都会产生额外的时间U。每个批次都有一个确定其测试时间Q的批量大小。
现在我需要提出一个批量调度算法，以便完成所有批量测试的时间是最少的。
解决这类问题的最佳方法是什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2010-07-27 18:19:47
当任务大小为1时，可以将其建模为具有安装时间的Job-Shop问题。不幸的是，当任务数大于10时，很难找到最优解。
有许多免费的求解器实现包含Job-Shop作为示例问题:如果您使用的是C++，Gecode是很好的。如果您可以自由选择，JSP包含ECLiPSe的源代码。
如果您可以选择一个好的解决方案(而不是最优的解决方案)，我建议使用贪婪算法(对于JSP，贪心算法给出的解决方案通常在最优解的10%以内-我在这方面有一些经验)。我将考虑一个，然后回到这里(问题是所谓的“设置时间约束”，即来自更改测试器配置的约束)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3342401
复制相关文章
相似问题
腾讯云开发者
