This thesis considers a nonpreemptive single-machine clustered job scheduling problem where the objective is to minimize maximum lateness subject to ready times and due dates. Problems with lateness minimization measure are known NP-complete. However, polynomial time algorithms are possible if jobs are clustered. Thus, a polynomial time algorithm is derived for the problem by use of dominant solution properties. And a heuristic approach is tried for jobs which are not clustered. Numerical examples are tested for the algorithm illustration.
본 논문에서는 작업들이 각 각 공정시간, 납기일과 도착시간을 갖고 다수의 군집으로 이루어져 있을때 단일설비에서의 최대지연시간 최소화를 위한 일정계획을 다루었다.
일반적으로 작업들이 군집되어있지 않은 경우에는 그러한 납기지연을 최소화 하는 일정계획은 NP-complete 임이 알려져있다. 그러나 군집된 작업들의 경우에는 우월성질 (Dominance Properties) 을 이용하여 최적해를 쉽게 구할수 있었다. 이러한 우월성질은 군집내에서 존재하는 것과 군집들을 연결할때 존재하는 것으로 나누어져 최적해를 쉽게 찾는
데 기여했다. 최종적으로 작업의 갯수와 같은 갯수의 작업순서들을 고려하여 최소의 납기지연을 보장하는 최적의 작업순서를 결정했다.
작업들이 군집되어있지 않은 경우에 앞서 고려했던 접근방법을 적용하여 발견적 기법을 제시했다. 또한, 이러한 발견적 기법의 성능평가를 한 결과 각 작업들의 공정소요시간이 길거나 작업들의 도착시간간격이 짧을때 많은 횟수의 최적해를 구해냄을 알수있었다.
