This thesis considers four different cases of single machine deterministic scheduling problems with common due date.
First, a non-preemptive scheduling problem is considered for dynamically arriving jobs with a given common due date to find the optimal schedule which minimizes the sum of earliness/tardiness and starting-time penalties.
Second, a scheduling problem is considered for all jobs available at time zero with a given common due date to find the optimal schedule which minimizes the sum of earliness/tardiness and flow times (instead of starting-time penalty).
Third, a scheduling problem is considered for all jobs available at time zero to find the optimal schedule (batching and sequencing) which minimizes mean flow time subject to no tardy jobs and restrictions on batch size.
Finally, a scheduling problem is considered for all jobs available at time zero to find the optimal batching and sequencing which minimizes weighted mean flow time under restrictions on batch size.
In each of the above cases, the optimal solution properties are characterized and then used in developing solution algorithms.
In the first and second cases, it is assumed that any job splitting is not allowed and hence batching decision is not necessary. For those problems, the optimal schedule is characterized to form a V-shape type of sequencing, based upon which effective heuristic algorithms are suggested.
In both the third and fourth cases, batching decision is additionally considered under the assumptions that the job splittings into smaller batches are allowed and each batch is restricted to have an integral size allowed within the given lower and upper bounds and also to have some batch setup time for process initiation. The optimal batching and sequencing are characterized to give the rule of processing the lager batch the earlier. This solution property is used to develop dynamic programming solution algorithms.
본 논문은 공통 납기를 가지는 작업들을 단일 설비로 수행하는 상황에서 각 작업들의 수행 시작시간 및 순서를 관련 총 비용이 최소화 되게 정하는 문제들을 다룬다. 각 작업의 수행은 여러개로 나누어서 수행할 수 있는 경우와 나눌 수 없는 문제로 구분할 수 있는데, 본 논문에서는 먼저 각 작업을 나눌 수 없는 경우에 대해 두 유형의 문제를 다루고, 또한 여러개로 나누어서 수행할 수 있는 경우에 대해서도 두 가지 유형의 다른 문제를 다룬다.
첫째로, 주어진 공통 납기를 가지는 각 작업들이 서로 다른 시점에 도착하는 경우, 총 조기/지연달성 비용 및 시작시간 벌과 비용을 최소화하기 위한 일정 계획 수립 문제를 다룬다. 최적 일정 계획을 위한 여러가지 우월 성질을 이 문제에 대해 규명하였고 이를 이용하여 분지한계법을 개발한다. 또한 효율적인 일정계획 수립을 위한 발견적 해법도 제시한다.
둘째로, 주어진 공통 납기를 가지고 있는 모든 작업들이 현 시점에 모두 도착해 있는 경우, 총 조기/지연달성 비용 및 공정시간을 최소화하기 위한 문제를 다룬다. 이를 위해 여러 우월 성질을 유도하였는바, 이는 V-형태 유형의 구조를 가진다는 것이 규명된다. 이 사실을 이용하여 효율적인 일정 계획 수립을 위한 발견적 해법을 수치 테스트를 통해 제시한다.
세째로, 현재 시점에 도착해 있는 개별 주문에 의한 작업 및 기획생산 작업의 두 종류 작업에 대해, 개별 주문 작업은 그에 대한 주어진 납기 내에 모든 작업을 완료하여 인도하고, 기획 품목은 여러개로 나눠서 수행 가능한 경우, 총 공정시간이 최소가 되게 작업을 나누는 방법(배칭) 및 일정계획 수립 문제를 다룬다. 먼저, 가능해가 존재하기 위한 두 가지 충분 조건을 규명하고, 작업을 나눠서 수행함에 있어서 추가적인 준비시간이 없는 경우에 대해 최적해를 구하기 위한 간단한 해법을 개발하며, 준비시간이 있는 경우에 대해서는 최적해를 위한 동적계획법을 개발한다.
네째로, 현재 시점에 도착해 있는 여러 종류의 작업을 나눠서 수행할 수 있는 경우에 총 공정시간이 최소가 되는 일정 계획 수립 문제를 다룬다. 여기서 각 작업의 납기는 생산 주기에 비해 매우 큰 상황을 고려하며, 세번째 문제의 경우와 마찬가지로 각 나눠지는 배치의 크기에 제약이 있고 각 배치의 수행에 준비 시간이 필요한 경우에 대해 최적 배칭 방안 및 일정 계획의 수립이 목적이다. 또한 각 작업의 공정시간은 그 작업의 수행이 완료되는 시점(단위-흐름 문제) 및 그 작업을 포함하고 있는 배치의 수행이 완료되는 시점(배치-흐름 문제)으로 각각 측정할 수 있는데, 이 두 측정 방법에 대해 각각 최적 일정 계획 수립을 위한 성질을 규명하고 이를 이용하는 동적계획법을 제시한다. 또한 각 작업을 나눠서 수행하는 경우에는 큰 배치를 작은 배치보다 먼저 수행하는 것이 최적임을 규명한다.
