针对小规模问题，neh与ig运行结果的差异

NEH（最近邻交换法）和IG（插入法）都是解决排列问题的贪心算法，它们的主要不同点在于选择候选解的方式不同。

NEH算法是通过将每个任务依次插入到已有序的解中，并计算插入后的目标函数值，选择使目标函数值最小的插入位置进行插入。因此NEH算法的时间复杂度为O(n^3)。

而IG算法是通过随机选择一个位置，将一个任务插入到该位置，并计算插入后的目标函数值，选择使目标函数值最小的插入位置进行插入。因此IG算法的时间复杂度为O(n^2)。

由于NEH算法需要比IG算法更多的计算，因此在小规模问题中，NEH算法可能会比IG算法更慢。但是在大规模问题中，NEH算法的时间复杂度增长更慢，因此可能比IG算法更快。

相关问题

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

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

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

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

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