neh 算法 英文全写

NEH算法（即the Nawaz, Enscore, and Ham算法）是一种用于解决作业车间调度（Job Shop Scheduling）问题的启发式算法。它由Nawaz, Enscore和Ham于1983年提出。

作业车间调度问题是一个关于如何合理地安排不同作业在工作中心上的执行顺序的优化问题。在这个问题中，有一组作业需要在多个工作中心上完成，每个作业都有不同的加工时间，并且每个作业在不同工作中心上执行所需的时间也可能不同。目标是找到一个最优的作业顺序，以最小化作业的总完成时间或最小化其他特定目标。

NEH算法的主要思想是将问题转化为单机调度问题，并根据作业的加工时间进行排序。算法的步骤如下：

1. 确定所有作业加工时间的总和，将这个总和作为初始目标值。
2. 根据作业的加工时间进行降序排列。
3. 对于每个作业，依次将它插入到当前各个位置，以寻找一个最优的插入位置。在每次插入后，计算新的作业顺序所得到的总完成时间。选择总完成时间最小的插入位置，并将作业插入该位置。
4. 重复步骤3直到所有作业都被插入为止。
5. 所得到的最终作业顺序即为最优的调度方案。

NEH算法的优点是简单高效，能够快速找到一个接近最优解的调度方案。然而，由于其为启发式算法，不能保证一定找到全局最优解。此外，算法对作业加工时间的估计准确度要求较高，对大规模的问题来说，算法的计算复杂度也会增加。

相关问题

NEH算法matlab

NEH算法是一种用于解决排列问题的启发式算法，常用于解决调度问题。下面是一个使用MATLAB实现NEH算法的示例代码：

function [best_order, best_makespan] = NEH_algorithm(jobs)
    n = size(jobs, 1);  % 获取作业数量
    m = size(jobs, 2);  % 获取机器数量
    
    % 根据任务总处理时间排序作业
    [~, order] = sort(sum(jobs, 2), 'descend');
    
    % 初始化最佳顺序和最佳完成时间
    best_order = order;
    best_makespan = calculate_makespan(jobs, order);
    
    % 遍历所有可能的插入位置
    for k = 2:n
        current_job = order(k);
        
        % 尝试将当前作业插入到每个位置，并计算完成时间
        for i = 1:k
            new_order = [order(1:i-1), current_job, order(i:k-1)];
            new_makespan = calculate_makespan(jobs, new_order);
            
            % 如果得到更短的完成时间，则更新最佳顺序和最佳完成时间
            if new_makespan < best_makespan
                best_order = new_order;
                best_makespan = new_makespan;
            end
        end
    end
end

function makespan = calculate_makespan(jobs, order)
    n = size(jobs, 1);  % 获取作业数量
    m = size(jobs, 2);  % 获取机器数量
    
    % 初始化每个机器的完成时间
    machine_times = zeros(1, m);
    
    % 遍历所有作业
    for i = 1:n
        job = order(i);
        
        % 在最早可用的机器上完成作业
        machine_index = find(machine_times == min(machine_times), 1);
        
        % 更新机器完成时间
        machine_times(machine_index) = machine_times(machine_index) + jobs(job, machine_index);
    end
    
    % 完成时间为最后一个机器的完成时间
    makespan = machine_times(end);
end

你可以将你的作业矩阵传递给`NEH_algorithm`函数，它将返回最佳顺序和最短的完成时间。注意，这里假设`jobs`矩阵中的元素表示每个作业在不同机器上的处理时间。

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

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

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

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

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

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

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

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

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

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