生產調度零等待問題

經典的優(yōu)化問題，免疫算法（IA）是求解該問題的常用方法之一。其數(shù)學原理公式如下：

定義問題：生產調度零等待問題可表示為在滿足各種制約條件下，找到最小化某個指標（如總加工時間、平均加工時間等）的調度方案。

定義目標函數(shù)：目標函數(shù)是對待優(yōu)化的調度方案進行評估的函數(shù)，通常為評估調度方案的效果的指標，例如總加工時間、平均加工時間等。

初始化免疫群體：生成一組隨機免疫體，作為初始免疫群體。

計算親和度：對免疫群體中每個免疫體，通過目標函數(shù)計算其適應值，得到其在免疫群體中的親和度。

選擇克隆體：根據(jù)親和度，選擇一定數(shù)量的高親和度免疫體進行克隆，產生一批克隆體。

變異操作：對克隆體進行變異操作，增加群體的多樣性。

競爭操作：將克隆體和原始免疫體進行競爭，篩選出高親和度的免疫體作為下一代免疫群體。

迭代求解：循環(huán)執(zhí)行步驟4-7，直到達到預先設定的停止條件（如迭代次數(shù)或最優(yōu)適應值達到一定程度）。

輸出結果：在最終免疫群體中選擇最優(yōu)免疫體作為最優(yōu)解輸出，得到最優(yōu)的調度方案。

function [fitness] = fitness_function(chromosome, job_times, machine_num)
    % chromosome 為染色體，表示作業(yè)的調度順序
    num_jobs = length(job_times);
    machine_end_time = zeros(1, machine_num); % 每臺機器的結束時間
    job_start_time = zeros(1, num_jobs); % 每個作業(yè)的開始時間
    for i = 1 : num_jobs
        job = chromosome(i);
        time = job_times(job);
        [~, machine_id] = min(machine_end_time);
        start_time = max(machine_end_time(machine_id), job_start_time(job));
        end_time = start_time + time;
        machine_end_time(machine_id) = end_time;
        job_start_time(job) = end_time;
    end
    fitness = sum(machine_end_time); % 目標是最小化總加工時間
end


job_times = [2, 9, 4, 7, 5]; % 每個作業(yè)的耗時
machine_num = 3; % 機器數(shù)量
options = optimoptions('ga', 'MaxGenerations', 100, 'PopulationSize', 50); % 定義GA的參數(shù)
[x, fval] = ga(@(x)fitness_function(x, job_times, machine_num), length(job_times), options); % 調用 ga 函數(shù)求解


% 輸出最優(yōu)解
disp(x);
disp(fval);

以上代碼中，定義了一個適應度函數(shù) fitness_function，該函數(shù)根據(jù)輸入的調度順序和每個作業(yè)的耗時，計算出每臺機器的總加工時間，并將其作為函數(shù)的返回值。在主程序中，使用 MATLAB 中的 ga 函數(shù)進行求解，得到最優(yōu)的調度順序和最小的總加工時間。