This thesis considers the criterion of minimizing total job tardiness in a flowshop system in which no queues are allowed at any intermediate storage. Several models such as tow-machine flowshop problem, three-machine flowshop problem with the first machine dominating the second machine, and multiple-machine flowshop problem with machines dominated in either increasing or decreasing order are investigated. Some necessary conditions to determine the sequential order between a pair of adjacent jobs are derived. For all the models except for the model with all machines dominated in increasing order, branch and bound solution procedures are exploited. For the model with all machines dominated in increasing order, a heuristic solution procedure is derived. Various numerical examples are presented to illustrate the solution procedures.
본 논문에서는 공정간 대기가 허락되지 않고, 전체지연시간의 최소화를 위한 연속공정작업들의 일정계획에 관한 세가지 문제를 다루었다.
첫번째, 기계가 두대인 문제에 대해서 다루었다. 이 문제는 일반적으로 NP-Complete 문제로 알려져있다. 해법으로는 우월성질(Dominant Property)을이용한 분지한계기법을 제시하였다. 두번째, 기계가 세대이고, 첫번째 기계에서 각 작업들의 가공시간이 두번째 기계에서 각 작업들의 가공시간보다 항상 크거나 같다는 가정하에서의 문제를 다루었다. 해법으로는 우월성질을 이용한 분지한계기법을 제시하였다. 세번째, 기계가 여러대이고, 기계들사이에 각 작업들의 가공시간의 크기의 순서가 연속적으로 정해진 두가지 문제를 다루었다. 첫번째, 첫번째 기계에서 각 작업들의 가공시간이 두번째 기계에서 각 작업들의 가공시간보다 항상 크거나 같고, 두번째 기계에서 각 작업들의 가공시간이 세번째 기계에서 각 작업들의 가공시간보다 항상 크거나 같고 등등 이러한 관계가 마지막 기계까지 연속적으로 이루어진 문제에 대해 우월성질을 이용한 분지한계기법을 제시하였다. 두번째, 위의 문제와는 반대의 연속적관계를 갖는 문제를 다루었다. 분석결과가 단일기계인 문제와 유사하여, 이를 근거로 발견적 해법을 제시하였다. 또한, 이러한 발견적 해법의 성능평가를 한 결과 비교적 빨리 최적해와 유사한 근사해를 얻을 수 있었다.
