유전자 워크숍 기획

잡 샵 스케줄링은 수학 프로그래밍에서 어려운 문제입니다. 그러나 해당되는 경우 운영에 미치는 영향은 클 수 있습니다. 오늘의 블로그 게시물에서는 유전자 작업 스케줄링을 다루는 기술적인 예를 통해 이 주제에 기여할 것입니다.

간단한 작업장 기계 작업 스케줄링 문제

내가 제안하는 예는 3개의 머신(M1, M2, M3)과 5개의 작업(T1, T2, T3, T4, T5)으로 구성됩니다. 작업은 작업장에서 처리되어야 합니다. 각 작업은 모든 컴퓨터에서 처리할 수 있지만 각 컴퓨터에서 가능한 작업 순서를 제한하는 특정 제약 조건이 있습니다.

예를 들어 제약 조건은 다음과 같을 수 있습니다.

T1은 M1에서 T2보다 먼저 처리되어야 합니다.
T4는 M2의 T5보다 먼저 처리되어야 합니다.
T2와 T3는 같은 기계에서 처리할 수 없습니다.

이제 모든 작업의 총 처리 시간을 최소화하는 각 컴퓨터의 작업 일정을 찾고 싶습니다.

유전자 알고리즘을 사용한 작업장 작업 스케줄링

유전자 알고리즘을 사용하여 이 문제를 해결하기 위해 일정을 정수 시퀀스로 나타냅니다. 각 정수는 다음에 처리할 작업을 나타냅니다. 예를 들어 일정 [1, 2, 3, 4, 5]는 컴퓨터 1에서 작업 1을 처리한 다음 컴퓨터 2에서 작업 2를 처리한 다음 컴퓨터 3에서 작업 3을 처리한다는 의미입니다.

제약 조건을 고려하여 주어진 일정에 대한 총 처리 시간을 계산하는 간단한 피트니스 함수를 사용할 수 있습니다. 예를 들어 다음과 같이 처리 시간을 계산할 수 있습니다.

각 시스템에 대해 해당 시스템에 할당된 모든 작업의 처리 시간 합계로 처리 시간을 계산합니다.
제약 조건 위반이 있는 경우(예: T2와 T3가 동일한 시스템에 할당된 경우) 처리 시간에 페널티를 추가합니다.
일정의 적합성은 처리 시간의 음수입니다.

그런 다음 유전자 알고리즘을 사용하여 좋은 일정을 찾을 때까지 일정을 생성하고 발전시킬 수 있습니다.

유전자 스케줄링 알고리즘 예제

다음은 알고리즘 작동 방식의 예입니다.

일정의 초기 모집단을 생성합니다. 각각은 기계에 할당된 임의의 작업 순서로 구성됩니다.
피트니스 기능을 사용하여 각 일정의 피트니스를 계산합니다.
토너먼트 선택과 같은 선택 방법을 사용하여 차세대 일정을 번식시키기 위해 모집단의 하위 집합을 선택합니다.
교차 및 변형 연산자를 사용하여 새 일정을 생성합니다.
이전 인구를 새 인구로 교체하고 특정 세대 수에 대해 2-4단계를 반복합니다.
찾은 최상의 일정은 피트니스 값이 가장 높은 일정입니다.

Job Shop 일정 문제는 NP-hard로 알려져 있으며, 이는 대규모 문제 인스턴스에 대해 최적의 솔루션을 찾는 것이 계산적으로 다루기 어렵다는 것을 의미합니다. 결과적으로 유전자 알고리즘은 수렴하는 데 오랜 시간이 걸리거나 최적의 솔루션을 전혀 찾지 못할 수 있습니다.

최종 발언 및 관련 직업 상점 일정 콘텐츠

Job Shop 일정은 도전적인 주제입니다. 수학적 프로그래밍, 그리고 이 경우 유전 알고리즘은 경우에 따라 효과적일 수 있습니다. 다른 경우에는 합리적인 노력으로 분석적으로 해결하기에는 문제가 너무 복잡할 수 있습니다. 이 경우 이산 사건 시뮬레이션은 수학적 프로그래밍 응용 프로그램의 일부 문제를 극복하는 데 도움이 될 수 있습니다. 다음 SCDA 블로그 게시물은 작업장 일정의 문제를 설명합니다.