什么是NEH启发式方法

NEH启发式方法是一种用于解决作业车间调度问题的算法。它通过将作业按照它们的处理时间进行排序，然后将它们插入到不同的机器上，以最小化完成所有作业所需的时间。这种方法已经被证明是一种有效的解决方案，可以在实践中得到广泛应用。

相关问题

详细讲解一下NEH启发式方法

NEH启发式方法是一种用于解决作业车间调度问题的算法。该算法的主要思想是将所有作业按照它们的加工时间之和进行排序，然后将它们依次插入到每个机器上，以获得最短的调度时间。

具体来说，NEH启发式方法的步骤如下：

1. 将所有作业按照它们的加工时间之和进行排序，从大到小排列。

2. 将前两个作业插入到每个机器上，计算出每个机器的调度时间。

3. 将第三个作业插入到每个机器上，计算出每个机器的调度时间。选择使得调度时间最短的插入位置。

4. 依次将剩余的作业插入到每个机器上，选择使得调度时间最短的插入位置。

NEH启发式方法的优点是简单易懂，能够快速得到一个较优的解。但是，它并不能保证得到最优解，因此在实际应用中需要结合其他算法进行优化。

采用NEH启发式算法最小化最大完工时间。

NEH启发式算法是一种用于解决排列问题的启发式算法。在最小化最大完工时间问题中，NEH算法可以用于求解n个作业在m台机器上完成的最小化最大完工时间问题。

具体地，NEH算法的步骤如下：

1. 计算每个作业在每台机器上的处理时间，并按照处理时间从大到小排序。

2. 初始化一个包含一个作业的排列。

3. 将下一个作业插入到排列中，使得插入后的排列的最大完工时间最小。

4. 重复步骤3，直到将所有作业都插入到排列中。

5. 返回最小化的最大完工时间。

NEH算法的关键在于如何选择插入作业的顺序以最小化最大完工时间。一般来说，可以采用贪心策略，即每次选择处理时间最长的作业插入到排列中。

但是，NEH算法并不保证能够找到最优解。因此，在实际应用中，需要根据具体问题的特点选择合适的算法。