采用NEH启发式算法最小化最大完工时间。
时间: 2023-07-30 19:08:04 浏览: 130
启发式算法的优化
NEH启发式算法是一种用于解决排列问题的启发式算法。在最小化最大完工时间问题中,NEH算法可以用于求解n个作业在m台机器上完成的最小化最大完工时间问题。
具体地,NEH算法的步骤如下:
1. 计算每个作业在每台机器上的处理时间,并按照处理时间从大到小排序。
2. 初始化一个包含一个作业的排列。
3. 将下一个作业插入到排列中,使得插入后的排列的最大完工时间最小。
4. 重复步骤3,直到将所有作业都插入到排列中。
5. 返回最小化的最大完工时间。
NEH算法的关键在于如何选择插入作业的顺序以最小化最大完工时间。一般来说,可以采用贪心策略,即每次选择处理时间最长的作业插入到排列中。
但是,NEH算法并不保证能够找到最优解。因此,在实际应用中,需要根据具体问题的特点选择合适的算法。
阅读全文