기계 가용성 제약을 고려한 Flowshop상황하에서 Makespan을 최소화하기 위한 휴리스틱에 대한 연구

Abstract

전통적인 flowshop문제는 기계가 언제나 가용함을 가정하지만 현실 상황에서는 기계가 가용하지 않을 때가 존재한다. 본 연구에서는 개의 작업이 m대의 기계를 모두 거쳐야 하는 flowshop공정에서 대의 기계 모두에 정확히 두 개의 기계 비가용구간이 존재하는 문제를 다룬다. 이 문제는 잘 알려진 NP-hard 문제이고, makespan을 최소화하는 non-permutation스케줄을 찾는 것이 목적이다. 본 연구에서는 유전 알고리듬을 기반으로 하여 기존의 알고리듬보다 향상된 새로운 알고리듬을 제안하는 것을 목적으로 한다. 기존의 유전 알고리듬보다 제안하는 알고리듬이 flowshop상황하에서 기계가용성 제약을 고려하는 일정계획문제를 해결하는데 보다 효과적임을 실험을 통해 입증하였다.; Classical flowshop scheduling problem assume that machines are simultaneously operating during the whole planning horizon, However, this assumption may not be realistic some situations. In this paper, we study the flowshop scheduling problem with availability constraints. In such a problem, n jobs have to be scheduled on m machines under assumption that the machines are not available during the whole planning horizon. The objective is to find a non-permutation schedule which minimizes the makespan; this is a well-known NP-hard problem. We propose a heuristic algorithm, which can find good solutions within a reasonable amount of computation time. Computational experiments are performed on instances to show that proposed genetic algorithm outperforms the existing genetic algorithm.