재투입이 존재하는 유연흐름공정에서 주문의 총 흐름시간을 최소화하기 위한 일정계획 방법론

Scheduling Algorithm for Reentrant Flexible Flow Shop with the Objective Function of Minimizing Orders’ Total Flow Time

본 논문은 재투입이 존재하는 유연흐름공정에서 주문의 총 흐름시간을 최소화 하는 일정계획 문제를 다룬다. 유연흐름공정의 각 공정에는 동일한 성능의 병렬기계들이 존재한다. 본 일정계획 문제에서 각 주문은 복수의 동일한 로트들로 구성되며, 임의의 주문에 속한 로트들은 독립적으로 가공되며 물류의 최소 단위이다. 어떤 주문의 로트들은 해당 유연흐름공정구간에 재투입이 되어 두 번의 공정을 거쳐야 한다. 본 일정계획 문제를 위해 제안 된 주요 알고리듬들은 각각의 로트에우선순위를 할당하여 일정계획을 수립하는 방법론들과 주문 자체에 우선순위를 결정한 뒤 주문에 포함된 로트들에 주문의우선순위를 할당하는 방법론들을 제시하였다. 제안된 알고리듬들과 기존의 일정계획 방법론의 성능평가를 위해 무작위로발생시킨 문제를 대상으로 시뮬레이션 테스트를 수행하였다. 결론적으로 주문 자체에 우선순위 결정 후 각 주문에 포함된로트들의 우선순위를 할당하는 방법이 좋은 결과를 보였다.

This study focuses on a scheduling problem in a flexible flow shop, where there are serial stages, each with identical parallel machines. We suggest heuristic algorithms for the problem to minimize the total flow time of a given set of orders. Each order is composed of multiple lots and is processed on any parallel machines at each stage. This shop has reentrant flows since products for specific orders should visit the processing stages twice. We suggest algorithms of two types. The algorithms of the first type are three-phase algorithms, and the second type's algorithm is one-phase. In the first phase of three-phase algorithms, an initial sequence is obtained using priority dispatching rules, and then a construction algorithm is used to obtain sequences for each stage in the second phase. Finally, in the third phase, lots that visit the stages for the second time are scheduled using priority dispatching rules. Computational experiments are performed on randomly generated test problems to evaluate the performance of the suggested algorithms. Results show that the order-based algorithms perform better than the lot-based algorithms and an algorithm used in practice.