This thesis analyzes a scheduling problem of a two-machine no-wait, flow shop incorporating both criteria of makespan and maximum tardiness. For the problem, several dominant solution properties are characterized and used to exploit a branch-and-bound algorithm and a heuristic algorithm. And two special cases of the problem are also investigated; one case where each job has the equal processing time on both machines and the other case where the first machine dominates the other one. Various numerical examples are presented to illustrate the solution procedures, respectively.
본 논문에서는 공정간 대기가 허락되지 않고, 총완료시간(Makespan)과 최대지연시간(Maximum Tardiness)의 최소화를 동시에 추구하는 연속공정일정계획에 관한 문제를 다루었다.
해법으로 우월성질들(Dominant Properties)을 이용한 분지한계기법과 발견적 해법을 제시하였다. 그리고 두 가지 특별한 경우에 대해서 살펴보았다. 첫번째, 첫번째 기계에서 각 작업들의 가공시간과 두 번째 기계의 각 작업들의 가공시간이 같을 경우에 대해서 문제를 다루었다. 두 번째, 첫 번째 기계에서 각 작업들의 가공시간이 두번째 기계에서 각 작업들의 가공시간보다 항상 크거나 같다는 가정하에서 문제를 다루었다. 또한 빠른 시간에 근사해를 구할 수 있는 발견적 기법을 제시했다. 성능 평가를 통하여 제시된 발견적 기법이 우수한 근사해를 구해냄을 알 수 있었다.
