This thesis considers a nonpreemptive single machine scheduling problem in which all jobs are partitioned into several job sets each having its corresponding common due date and are subject to penalties due to early or late completions. The objective of the problem is to minimize the weighted mean absolute deviation of job completion times about such common due dates under the assumption that each job has a different weight, and to exploit dominant solution properties based upon which three heuristic solution methods are derived. It is also shown that the problem of minimizing the mean squared deviation of job completion times about a common due date is equivalent to the problem of minimizing the completion time variance. The mean absolute deviation problem with a single common due date is first investigated and then extended to the case with two common due dates, and suggests a solution method. Numerical examples are presented.
본 논문은, 작업들이 공통의 납기를 갖는 경우에 조기 또는 지연 달성에 따른 작업에 대해 벌과를 부여하는 상황 아래에서 총 벌과의 합을 최소화하는 작업 일정 계획의 문제 두 가지 모형에 대해 다루었다.
첫 번째 모형은 한 집단(class)의 작업들이 각각 다른 가중치를 갖는 경우에 총 가중 벌과의 합을 최소화하는 작업 일정 계획의 모형으로써, 이모형에 대한 최적해의 성질을 분석 하였으며, 이에 따른 세 가지의 발견적 기법을 제시하여 비교 하였다.
두 번째 모형은 두 개의 집단(class)이 각각 공통의 납기를 갖는 (즉, 공통의 납기가 두개 존재) 경우를 취급하여 기존의 연구를 연장 시켰으며, 여러 개의 공통 납기를 갖는 일반적인 모형 연구의 시발점이 되는 모형이라 생각되어 진다. 이 모형에 대한 최적해의 성질을 규명 하였으며, 이에 따른 발견적 기법을 제시하였다. 두 모형에 대한 알고리즘들이 예제를 통해 설명되었다.