c# - 分配公式

Question

我有汽车维修服务店，有很多服务（诊断，发动机维修。电气维修......）序列守恒无关紧要

然后我知道一辆当前的汽车需要多少时间进行单一服务，例如：

1. 福特 - 诊断 120 分钟，发动机 360 分钟，电动维修 80 分钟
2. BMW - 诊断时间 90 分钟，发动机 480 分钟，电动维修 140 分钟
3. 梅赛德斯 - 诊断 90 分钟，发动机 42 分钟，电动维修 160 分钟

等等，还有很多汽车。

那么是否有任何好的算法或数学公式可以将汽车最佳地分配到服务箱中，这样就不会浪费箱子的时间并以最少的汽车等待获得最佳结果。

Answer 1

这是所谓的“开放式商店”问题的一个例子。与 Job Shop Scheduling 的区别在于，在后者中，在机器上执行作业的顺序是相关的，而在您的示例中并非如此。

不幸的是，对于您的情况，问题是 NP 困难。（对于两台机器可以在多项式时间内解决。）不必绝望，因为有许多算法可能对您的问题大小适用。

Wikipedia 在“Open-Shop Scheduling”下有几个很好的起点，参考了该领域的一篇经典论文。

Answer 2

您的问题称为“作业车间调度”问题，有时也称为“车间调度”。它被广泛讨论，因为随着变量数量的增加它变得非常困难（这就是所谓的“NP-Hard”问题）。

没有简单的答案，但是有几种很好的算法可以在计算时间上追求交易准确性。我建议将Dorit Hochbaum 编辑的“ NP-Hard Problems 的近似算法”一书作为资源。