논문 요약 - Minimizing makespan in a blocking flowshop using genetic algorithm

소개

< blocking이 있는 흐름공정에서 유전 알고리즘을 이용한 스케줄링 문제 >

논문 제목: Minimizing makespan in a blocking flowshop using genetic algorithm

목차

Abstract
1. Introduction
2. No-wait flowshops and the slowing down concept
2.1 Computing the idle times in a no-wait flowshop
2.2 Procedure idle time
2.3 Definition: The "decision point" of a job

본문내용

m개의 기계로 이루어져 있으며 버퍼가 존재하지 않는 flowshop에서 n개의 작업에 대한 makespan을 최소화하기 위한 blocking flowshop문제를 다루고 있다. 버퍼가 존재하지 않기 때문에 작업물은 다음순서의 기계가 유휴상태가 될 때까지 전 기계에 머물러 있어야 한다. Abadi는 blocking flowshop문제와 no-wait flowshop사이의 관계를 확립하였다. blocking flowshop문제는 no-wait flowshop문제에서 특정 작업에 대해 slowing down을 추가시킨 것이다. 본 논문은 이 문제를 유전 알고리즘을 사용하여 makespan을 구하고, Abadi 휴리스틱과 비교, 분석하였다.
2. No-wait flowshops and the slowing down concept
섹션 2에서는 blocking flowshop(BLF)문제에서 주어진 작업순서에 대한 최적의 스케줄을 획득하는 문제가 고려된다. 즉 작업물의 순서는 정해져 있고, 이들을 어떻게 스케줄링해야 하는지에 대한 문제이다. BLF는 no-wait flowshop(NWF)문제와 매우 밀접한 관계를 가지고 있다. NWF는 작업물이 투입되면 종료까지 어떤 중지도 허용되지 않는다. 화학, 철강산업을 예로 들 수 있다. NWF는 주어진 작업시간이 끝나면 바로 다음 기계로 옮겨가야하는 반면에 BLF는 다음 기계가 작업중이면 전 기계에서 잔류할 수 있다. NWF문제의 feasible solution은 BLF문제에서도 feasible solution이다.
Abadi는 BLF와 NWF사이의 관계와 BLF문제를 푸는 기본 전략을 제안하였다. 처음에 NWF문제의 훌륭한 휴리스틱 스케줄을 개발하였고, 이를 변형시켜 BLF문제에 적용하였다.
현실세계에서는 항상 무제한으로 slowing down할 수 없다. 즉 slowing down 제한 시간이 존재하게 된다. 다음 아래에 부호설명이 있다.

참고자료

· 없음