유연한 작업장 스케줄링 문제(FJSP)를 다중 목표 라자리 최적화 알고리즘으로 해결하는 방법 (MATLAB 코드) https://mbd.pub/o/bread/mbd-ZZ2Wlp9x

작업장 스케줄링 최적화 분야에서 유연한 작업장 스케줄링 문제(FJSP)는 복잡한 제약 조건 하에 여러 성능 지표를 동시에 최적화해야 하는 도전적인 주제이다. 이 문제는 각 작업이 여러 기계 중에서 선택 가능한 공정 단계를 가지며, 전체 완료 시간과 기계 부하량 같은 다중 목적 함수를 최소화하는 것이 목표이다.

이 글에서는 비지배 정렬 기반의 다중 목적 라자리 최적화 알고리즘을 FJSP에 적용하는 방법과 MATLAB 구현 예제를 살펴본다.

다중 목적 라자리 최적화 알고리즘 개요

비지배 정렬은 다중 목적 최적화에서 해집단을 목적 함수 값에 따라 계층적으로 분류하는 핵심 기법이다. 이 기법은 각 해가 다른 해를 지배하는지 여부를 판단하여, 더 나은 성능을 가진 해를 우선적으로 처리한다.

라자리 최적화 알고리즘은 라자리의 먹이 찾기 및 이동 행동을 모방한 진화적 알고리즘으로, 해 공간에서 상호작용을 통해 최적 해를 탐색한다. 비지배 정렬을 결합하면 여러 목적 간의 균형을 유지하면서 최적 해를 효과적으로 탐색할 수 있다.

MATLAB 코드 구현

초기 설정

% 기계 및 작업 수 정의
machineCount = 5;
jobCount = 3;
% 작업 공정 및 기계 옵션 초기화
processes = cell(jobCount,1);
for i = 1:jobCount
    processNum = randi([3, 5]); % 공정 수 무작위 설정
    machineOptions = cell(processNum,1);
    for j = 1:processNum
        optionNum = randi([1, machineCount]); % 기계 옵션 수 무작위 설정
        machineOptions{j} = randperm(machineCount, optionNum);
    end
    processes{i} = machineOptions;
end

이 코드는 기계와 작업 수를 정의하고, 각 작업의 공정 수와 각 공정에 가능한 기계 옵션을 무작위로 생성하여 FJSP 문제의 초기 환경을 구성한다.

목적 함수 계산

function [completionTime, machineLoad] = evaluateSolution(individual, processes, machineCount)
    % 기계별 작업 완료 시간 추적
    machineTimes = zeros(1, machineCount);
    % 각 공정 순회
    for i = 1:length(individual)
        job = individual(i).jobIdx;
        process = individual(i).procIdx;
        machine = individual(i).machineIdx;
        % 공정 소요 시간 무작위 설정
        duration = randi([1, 10]);
        % 시작 시간 계산
        prevFinish = 0;
        if i > 1
            prevFinish = individual(i-1).finishTime;
        end
        startTime = max(machineTimes(machine), prevFinish);
        finishTime = startTime + duration;
        individual(i).finishTime = finishTime;
        machineTimes(machine) = finishTime;
    end
    completionTime = max(machineTimes);
    % 기계 부하 계산
    machineLoad = sum(machineTimes)/machineCount;
end

이 함수는 개체의 스케줄링 계획을 입력으로 받아, 전체 완료 시간과 기계 평균 부하를 계산한다. 각 공정의 시작 시간을 이전 작업의 완료 시간과 기계 가용 시간을 기준으로 결정하여 정확한 시뮬레이션을 수행한다.

비지배 정렬 구현

function fronts = fastNonDominatedSort(population, processes, machineCount)
    S = cell(1, length(population));
    n = zeros(1, length(population));
    fronts{1} = [];
    for i = 1:length(population)
        S{i} = [];
        n(i) = 0;
        for j = 1:length(population)
            if i ~= j
                [obj1, ~] = evaluateSolution(population{i}, processes, machineCount);
                [obj2, ~] = evaluateSolution(population{j}, processes, machineCount);
                if dominates(obj1, obj2)
                    S{i} = [S{i}, j];
                elseif dominates(obj2, obj1)
                    n(i) = n(i) + 1;
                end
            end
        end
        if n(i) == 0
            fronts{1} = [fronts{1}, i];
        end
    end
    i = 1;
    while ~isempty(fronts{i})
        Q = [];
        for p = fronts{i}
            for q = S{p}
                n(q) = n(q) - 1;
                if n(q) == 0
                    Q = [Q, q];
                end
            end
        end
        i = i + 1;
        fronts{i} = Q;
    end
    fronts(cellfun('isempty', fronts)) = [];
end

function flag = dominates(obj1, obj2)
    flag = (obj1(1) <= obj2(1) && obj1(2) <= obj2(2)) && ...
           (obj1(1) < obj2(1) || obj1(2) < obj2(2));
end

fastNonDominatedSort 함수는 해집단을 비지배 계층으로 분류한다. 각 해의 목적 함수 값을 비교하여 지배 관계를 판단하고, 계층 구조를 형성한다. dominates 함수는 두 해의 목적 함수 값을 비교하여 한 해가 다른 해를 지배하는지 확인한다.

이 코드는 알고리즘의 핵심 로직을 제공하지만, 실제 구현에는 라자리의 이동 및 업데이트 규칙 등 추가적인 요소가 포함되어야 한다. 구체적인 문제에 따라 파라미터와 로직을 조정하여 최적의 스케줄링 결과를 얻을 수 있다.