In this thesis, a two-machine flow-shop scheduling problem with two kinds(renewable and non-renewable) of additional resources is considered. The objective of the problem is to determine the sequence of jobs on each machine and the amount of resources to be allotted for each operation in order to minimize the makespan. It is assumed that the processing time of each operation is a linearly decreasing function about allotted amounts of renewable and non-renewable resources. And the amount of each type of resource is restricted to an upper limit. Some dominance properties are characterized for the our problem, based upon which a branch and bound algorithm is exploited to find the optimum. Heuristic algorithms are also proposed and some computational experiences are discussed.
본 논문에서는 반복사용자원과 소모자원을 추가로 필요로하는 두 기계에서의 규칙적 연속공정작업들의 일정계획을 다루었다. 문제의 목적은 총 완성시간(Makespan)을 최소화하는 각 기계에서의 작업순서와 각 작업에 할당되는 추가자원의 양을 결정하는 것이다. 각 작업의 작업시간은 할당된 추가자원의 선형 감소 함수(A Linearly Decreasing Function)로 나타내지며 추가자원들은 일정한 양이상은 사용할 수가 없다는 것이 가정되었다.
일반적으로 자원 제약하의 일정계획 문제는 하나의 추가자원만을 고려한 경우에도 NP-complete로 알려져 있다. 이러한 자원 제약하의 일정계획 문제에 대하여 구해진 우월 성질(Dominance Properties)을 이용하여 최적해를 구하는 분지 한계기법이 제시되었고, 또한 빠른 시간에 근사해를 구할 수있는 발견적 기법을 제시했다. 성능 평가를 통하여 제시된 발견적 기법이 우수한 근사해를 구해냄을 알 수 있었다.