This thesis considers a new type of precedence constraint defined as s-precedence constraints. For s-precedence constraints, job i cannot start processing until all jobs that precede i start. This is different from the standard definition of a precedence relation where i cannot start until all prior jobs complete. While not discussed in the scheduling literature, s-precedence constraints have wide applicability in real world settings. Examples of hese types of constraints include most queueing systems where earlier arriving jobs start rocessing first. Applications occur in many production and service industries, including telecommunications, health care, and food processing and distribution.
This thesis considers three deterministic scheduling problems where jobs with precedence relations are processed by multiple parallel machines. The first problem is scheduling s-precedence constrained jobs on identical parallel machines with the objective of minimizing the total completion time. The problem is shown to be NPhard, and some basic properties of the problem are analyzed. An LP-based heuristic procedure is derived for the problem. Numerical experiments are conducted to show that the derived heuristic provides good solutions within a short time.
The second problem is scheduling s-precedence constrained jobs on machines in parallel with different speeds (referred to as uniform parallel machines). The objective is to minimize the weighted total completion time. An LP-based heuristic procedure is derived for the problem. Numerical experiments are conducted to show that the derived heuristic provides good solutions within a short time.
The third problem is scheduling s-precedence constrained jobs on identical parallel machines. The objective is to find the minimum makespan (the completion time of the last job). The problem is shown to be strongly NP-hard. A heuristic procedure is developed and tight worst case bounds on the relative error are derived. Numerical experiments are conducted to show that the derived heuristic provides good solutions within a short time.
본 논문은 시작점 선행제약이라 정의되는 새로운 개념의 선행제약을 다룬다. 시작점 선행제약은 한 작업을 시작하기 위해서는 그 작업을 선행하는 모든 작업들이 시작되어야 함을 가정하며, 이는 한 작업을 시작하기 위해서 그 작업을 선행하는 모든 작업이 끝나야 함을 가정하는 전통적 개념의 선행제약과는 뚜렷한 차이점을 가진다. 이러한 개념의 시작점 선행제약은 매우 광범위하게 활용될 수 있다. 그 예로, 우선권을 가진 고객을 먼저 처리해야 하는 환경을 모형화하는데 유용하게 쓰일 수 있으며, 통신(telecommunication), 의료(health care), 식료품 가공 및 분배(food processing and distribution) 등과 같은 대부분의 생산 및 서비스 산업에 적용 가능하다.
본 논문은 시작점 선행제약을 고려한 세 가지 일정계획 수립문제를 다루고 있다. 먼저, 시작점 선행제약을 고려하는 동종 병렬 시스템에서 총 작업완료 시간(total completion time)을 최소화하는 일정계획 문제를 다루었다. 동종 병렬 시스템이라 함은 동일한 작업을 서로 다른 기계에서 수행하더라도, 동종의 기계이기 때문에 동일한 작업수행시간이 소요되는 것을 의미한다. 먼저, 제안된 문제가 비다항문제(NP-hard)임을 증명하였고, 이는 최적해(optimal solution)를 찾기 위해 기존의 개발된 해법들을 이용할 경우 해법에 소요되는 시간이 지수적으로 증가(exponentially increase)하여 원하는 시간 안에 최적해를 구하기가 불가능하다는 것을 의미한다. 따라서, 최적해가 가지는 특성을 규명하고, 이를 기초로 선형계획법에 기반한 발견적 해법(heuristic)을 제안하였다. 마지막으로, 다양한 수치 실험을 통하여 제안된 해법이 우수한 성능을 가짐을 확인할 수 있었다.
다음으로, 이종 병렬 시스템에서 총 가중 작업완료시간(weighted total completion time)을 최소화하는 일정계획 문제를 다루었다. 이종 병렬 시스템이라 함은 동일한 작업을 수행할 수 있는 병렬 기계라고 하더라도 서로간의 작업속도가 상이하여 같은 작업을 수행하더라도 서로 다른 기계에서는 상이한 작업수행시간을 갖는 것을 의미한다. 앞서 다룬 동종 병렬 시스템에서의 일정계획 문제는 이종 병렬 시스템의 특수한 경우라고 볼 수 있다. 따라서, 제안된 문제가 비다항문제임을 쉽게 보일 수 있었으며, 선형계획법에 기반한 발견적 해법을 제안하였다. 또한, 다양한 수치 실험을 통하여 제안된 해법이 우수한 성능을 가짐을 확인할 수 있었다.
마지막으로, 동종 병렬 시스템에서 마지막 작업의 완료시간(Makesapn)을 최소화하는 일정계획 문제를 다루었다. 마찬가지로 제안된 문제가 비다항문제임을 보이고, 이에 대한 발견적 해법을 제안하였다. 제안된 발견적 해법의 성능 평가를 위해 선행제약 구조에 따른 한계분석(worst case analysis)을 하였다. 한계분석이란 제안된 해법으로부터 얻어진 근사해와 최적해의 비율에 대한 최대값을 규명하는 것을 말한다. 이와 더불어, 다양한 수치 실험을 통하여 제안된 해법이 우수한 성능을 가짐을 확인할 수 있었다.
본 논문은 시작점 선행제약을 정의하고, 이를 고려한 복합 시스템의 운용을 위한 최초의 논문이다. 본 논문을 계기로, 시작점 선행제약을 고려한 다양한 모형들이 개발되고 이에 대한 후속 연구가 지속적으로 이루어질 것으로 예상된다.
