This thesis focuses on a scheduling problem in a hybrid flow shop, in which here are serial stages, each with identical parallel machines. We suggest heuristic algorithms for the problem with the objective of minimizing total tardiness of a given set of orders. Each order is composed of multiple lots and each lot is processed on any one of parallel machines at each stage. In this shop, there are reentrant flows, since products for certain orders should visit the processing stages twice. The suggested heuristic algorithms are composed of three phases. In the first phase, an initial sequence is made 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. To evaluate performance of the suggested algorithms, computational experiments are performed on randomly generated test problems. Results show that the suggested algorithms perform better than existing algorithms and an algorithm that is used in practice.
본 논문은 재투입이 있는 혼합 병렬 흐름에서 주문의 납기 지연을 최소화 하는 일정 계획을 구하는 것이다. 본 문제에서 각 주문은 정수 개의 동일한 가공 단위의 로트들을 포함하며, 각 가공 단위의 로트들은 혼합 병렬 흐름에서 독립적으로 가공된다. 어떤 주문의 로트들은 혼합 병렬 흐름에 재투입이 되어 두 번의 가공을 해야 하며, 그러한 주문을 재가공 주문이라고 부른다. 본 문제를 풀기 위해서 3 단계의 휴리스틱 방법론을 제안하였다. 제안된 방법론을 기존의 알고리듬과 무작위적으로 발생시킨 문제로 비교해 본 결과, 본 연구에서 제시한 알고리듬이 더 좋은 결과를 보였다.
