유전 알고리즘 스케줄링

Genetic algorithm scheduling

유전자 알고리즘은 생산계획의 스케줄링 문제를 해결하는 데 사용될 수 있는 운영연구 방법이다.null

생산 스케줄링의 중요성

경쟁력을 갖추기 위해서는 비효율성을 최소화하고 생산성을 극대화해야 한다.제조업에서 생산성은 본질적으로 기업이 가용 자원을 얼마나 잘 최적화하고, 낭비를 줄이고, 효율성을 높일 수 있는가에 연결되어 있다.제조 공정에서 효율성을 극대화하는 최선의 방법을 찾는 것은 매우 복잡할 수 있다.간단한 프로젝트에서도 여러 입력, 여러 단계, 많은 제약과 제한된 자원이 있다.일반적으로 자원 제약 스케줄링 문제는 다음과 같이 구성된다.

  • 실행해야 하는 작업 집합
  • 각 작업을 완료하는 데 사용할 수 있는 제한된 리소스 집합
  • 충족해야 하는 제약 조건 집합
    • 시간 제약 – 작업을 완료하기 위한 시간 간격
    • 절차적 제약 – 각 작업을 완료해야 하는 순서
    • 리소스 제약 – 사용 가능한 리소스
  • 스케줄링 성능을 평가하기 위한 일련의 목표

어떤 기계, 어떤 직원이 어떤 순서로, 어떤 시간에 어떤 일을 완료해야 하는지 일정을 잡아야 하는 전형적인 공장 바닥 설정이 좋은 예다.null

스케줄링에 알고리즘 사용

스케줄링과 같은 매우 복잡한 문제에서는 최종 답을 얻을 수 있는 방법을 알 수 없기 때문에, 우리는 "좋은" 답을 찾기 위해 그것을 찾는데 의지한다.스케줄링 문제들은 종종 최적의 해결책을 찾기 위해 경험적 경험적 알고리즘을 사용한다.경험적 접근법은 입력이 복잡하고 다양해지면서 어려움을 겪는다.이러한 유형의 문제는 컴퓨터 공학에서 NP-하드 문제로 알려져 있다.다항식 시간에 최적의 솔루션을 찾기 위한 알고리즘이 없다는 뜻이다.null

그림 1. 스케줄링의 우선 순위

유전 알고리즘은 경험적 접근법과는 달리 유전 알고리즘은 단일 솔루션이 아닌 다수의 솔루션에서 작동하기 때문에 생산 스케줄링 문제를 해결하는 데 매우 적합하다.생산 스케줄에서 이 해결책의 집단은 때때로 상충되는 목표를 가질 수 있는 많은 대답으로 구성된다.예를 들어, 한 솔루션에서는 최소의 시간 내에 완료되도록 생산 프로세스를 최적화할 수 있다.또 다른 해결책에서는 최소한의 결함에 대해 최적화하고 있을 수 있다.우리가 생산하는 속도를 높임으로써 최종 제품의 결함의 증가에 직면할 수도 있다.null

우리가 달성하고자 하는 목표의 수를 증가시키면서 우리는 또한 문제에 대한 제약의 수를 증가시키고 마찬가지로 복잡성을 증가시킨다.유전자 알고리즘은 검색 공간이 크고 실행 가능한 해결책의 수가 적은 이러한 유형의 문제에 이상적이다.null

유전자 알고리즘 적용

그림 2 A. 일람표 게놈 예

스케줄링 문제에 유전 알고리즘을 적용하려면 먼저 게놈으로 표현해야 한다.스케줄링 게놈을 나타내는 한 가지 방법은 작업 순서 및 작업 시작 시간을 서로 상대적으로 정의하는 것이다.각각의 과제와 그에 상응하는 시작 시간은 유전자를 나타낸다.null

작업 및 시작 시간(gen)의 특정 순서는 우리 모집단에서 하나의 게놈을 나타낸다.우리의 게놈을 실현 가능한 해결책임을 확실히 하기 위해서 우리는 게놈이 우리의 우선적 제약을 준수하도록 주의를 기울여야 한다.우리는 우선 순위 제약 내에서 무작위 시작 시간을 사용하여 초기 인구를 생성한다.유전 알고리즘을 통해 우리는 이 초기 집단을 가지고 게놈과 소량의 무작위성을 결합하여 교차시킨다.이 조합의 자손은 시간을 최소화하고 결함을 최소화하는 것과 같은 우리의 제약조건 중 하나 또는 많은 것을 포함하는 피트니스 기능에 기초하여 선택된다.우리는 사전 지정된 시간 동안 또는 우리의 최소 기준에 맞는 해결책을 찾을 때까지 이 과정을 계속하도록 한다.전반적으로 연속적인 각 세대는 이전 세대보다 더 높은 품질로 더 적은 시간을 보내는 등 평균적인 체력을 갖게 될 것이다.다른 유전 알고리즘 솔루션과 마찬가지로 문제를 스케줄링할 때, 우리는 우선 순위 제약 조건을 위반하는 자손과 같이 실행 불가능한 자손들을 선택하지 않도록 해야 한다.물론 우리는 비용을 최소화하는 것과 같은 추가적인 피트니스 가치를 추가해야 할 수도 있지만, 각각의 제약조건이 추가될 때마다 검색 공간이 크게 늘어나고, 잘 맞는 해결책의 수가 줄어들게 된다.null

참고 항목

참고 문헌 목록

  • Wall, M., A Genetic Algorithm for Resource-Constrained Scheduling (PDF)
  • Lim, C.; Sim, E., Production Planning in Manufacturing/Remanufacturing Environment using Genetic Algorithm


외부 링크