Scheduling Algorithms for Multi-Stage Flow Shops with Reworks under Overlapped Queue Time Limits

Abstract

This study addresses a multi-stage flow shop scheduling problem in which a job is reworked on the corresponding stages when the queue time of the job between two stages exceeds an upper limit. In particular, overlapped queue time limits, i.e. the stages with queue time limits for a job may be overlapped, are considered. The problem is to determine the start times of jobs and rework setups if incurred for the objective of minimizing makespan. A mixed integer programming model is developed and its performance is reported for small sizes test instances. Then, due to the limited applications of the optimal approach, a basic variable neighborhood search (VNS) algorithm is proposed that generates an initial solution by the NEH heuristic and improves it using a shaking and a local search improvement methods. Also, the basic algorithm is modified into general variable neighborhood search (GVNS) algorithms with variable neighborhood descent methods in the local search improvement step. Computational results show that the GVNS algorithms outperform the basic algorithm significantly and also give near optimal solutions for small sized test instances within a reasonable amount of computation times.|본 연구에서는 중첩 대기시간 제약 하에서 대기시간 제약을 초 과한 작업물에 대해 재작업 준비 공정에서 재작업을 고려하는 흐 름 공정 시스템에서의 스케줄링 문제를 다루었다. 이전 연구와 달리, 본 연구는 대기시간 제약을 중첩으로 고려하였으며, 대기시 간 제약을 초과하지 않은 작업물에 대해서만 고려하는 것이 아닌, 대기시간 제약을 초과한 작업물을 재작업까지 고려하는 문제를 제시한다. 본 문제의 결정 변수로는 각 공정에서 작업물의 작업 시간과 재작업 준비 공정에서 대기시간 제약을 초과한 작업물의 작업시간을 결정하는 것이며 목적함수로는 최대 완료 시간 (makespan) 최소화를 고려하였다. 해법으로는 대상 시스템을 혼 합정수계획 모형으로 제시하였으며 문제의 복잡도로 인해 빠른 계산에 적절한 해를 제공하는 발견적 기법들을 제시하였다. 먼저 NEH 알고리즘으로 초기해를 구하였으며, 이를 개선하기 위해 가 변 이웃 탐색 알고리즘들을 제시하였다. 끝으로 제안하는 수리적 모형 및 다양한 알고리즘들의 성능을 비교하기 위하여 실험을 수 행하였고, 그에 대한 실험결과를 제시하였다.