This dissertation focuses on scheduling problems with machine availability constraints. Under the machine availability constraints, machines are not continuously available for processing jobs during the scheduling horizon. In many manufacturing systems, these constraints are considered when machines require preventive maintenance tasks, during which the machines are not available. In other words, while a maintenance task is being performed, the machine should be stopped and it cannot process any job. In this thesis, we consider three scheduling problems with different machine availability constraints, and develop algorithms for the problems.
First, we consider a problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. In the problem, the time interval between two consecutive maintenance tasks is given and each maintenance task should be started exactly at the planned time specified by the interval. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore’s algorithm for the problem without maintenance and then the solution is improved in the second phase.
Secondly, we consider a problem of scheduling jobs on two identical parallel machines that are not continuously available with the objective of minimizing the total tardiness. After processing a given number of jobs, each machine requires a preventive maintenance task, during which the machine cannot process jobs. We present dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as an upper bound obtained from a heuristic algorithm.
Finally, we consider a problem of scheduling jobs on identical parallel machines that require flexible maintenance with the objective of minimizing the total tardiness. Each machine requires preventive maintenance tasks which have to be started within a given cumulative working time limit after the previous maintenance. The starting time of a maintenance task is not fixed but flexible, that is, a maintenance task can be started at any time unless the cumulative working time after the end of the previous maintenance exceeds the given limit. We develop dominance properties and lower bounds, and present a branch and bound algorithm in which these properties and lower bounds are used.
Performance of the suggested algorithms are evaluated through a series of computational experiments on instances which are obtained from real data or generated randomly but in such a way that resulting problems reflect the real situations relatively well. Results of the experiments show that the algorithms developed in this research give very good solutions in a reasonable amount of computation time. Also, the suggested algorithms are expected to be used for operations scheduling problems in real manufacturing systems if they are modified to cope with the practical situations.
본 논문에서는 가용성 제약이 있는 생산 공정에서의 작업 일정계획 문제를 다루고 있다. 가용성 제약이란 고려하는 일정계획 기간에 공정 설비를 가동시킬 수 없는 기간이 존재하는 것으로, 이 기간 동안 작업을 중단해야 하는 제약을 말한다. 실제 많은 생산 시스템에 있는 공정들에서는 다양한 이유로 가용성 제약이 발생하는데, 설비의 예방보전(preventive maintenance)을 수행하기 위한 작업중단이 대표적인 예이다. 가용성 제약은 설비의 생산성 및 제품의 품질과 밀접한 관련이 있기 때문에, 일정계획 단계에서 이를 반드시 고려하여 작업 순서에 대한 의사결정을 내려야 한다. 본 논문에서는 설비의 예방보전에 의한, 각각 다른 특징을 갖는 세 가지의 가용성 제약이 있는 일정계획 문제들을 고려하였고, 주어진 작업들의 납기지연을 최소화하는 것을 목적으로 하여 작업들의 순서를 결정해주는 일정계획 방법론을 개발하였다.
첫 번째로, 논문의 2장에서는 주기적으로 예방보전(periodic maintenance)이 요구되는 단일 설비(single machine) 공정에서 주어진 납기를 넘겨 완료된 작업의 수(number of tardy jobs)를 최소화하는 일정계획 문제를 다루었다. 즉, 예방보전을 수행한 후 일정한 시간이 지나면 다시 예방보전을 수행해야 하는 설비로, 이로 인해 작업을 중단해야 하는 가용성 제약을 고려하였다. 이 문제에 대한 혼합 정수 모형(mixed integer programming model)을 제시하였고, 2단계(two-phase)로 이루어진 휴리스틱 알고리듬(heuristic algorithm)을 개발하였다.
다음으로, 논문의 3장에서는 일정한 수의 작업을 완료한 뒤 예방보전이 요구되는 동종 병렬 설비(identical parallel machines)로 이루어진 공정에서 주어진 작업들의 총 납기지연(total tardiness)을 최소화하는 일정계획 문제를 다루었다. 동종 병렬 설비라 함은 동일한 작업을 서로 다른 설비에서 수행하더라도 동종의 설비이기 때문에 같은 작업수행시간이 소요되는 것을 의미한다. 본 일정계획 문제에 대한 혼합 정수 모형을 제시하였다. 그리고 최적해의 우월 성질(dominance property), 하한(lower bound) 계산 방법을 개발하였고, 이를 이용하여 최적해를 구해내는 분지 한계 방법(branch and bound algorithm)을 제시하였다. 뿐만 아니라, 새로운 상한 (upper bound) 계산을 위한 휴리스틱 알고리듬을 개발하였다.
마지막으로, 논문의 4장에서는 연속적으로 작업을 수행할 수 있는 시간의 한계(cumulative working time limit)가 있는 동종 병렬 설비로 이루어진 공정에서 주어진 작업들의 총 납기지연을 최소화하는 일정계획 문제를 다루었다. 즉, 이전 예방보전을 수행한 뒤 연속적으로 가동시킬 수 있는 최대시간까지만 설비를 가동시킬 수 있고, 이 최대시간을 넘기기 전에 예방보전을 수행해야 하는 설비로, 이로 인해 작업을 중단해야 하는 가용성 제약을 고려하였다. 2장과 3장에서 고려했던 문제들과 달리, 예방보전의 시작시간 또한 의사결정 변수인 문제이다. 3장에서와 마찬가지로 혼합 정수 모형을 제시하였고, 최적해의 우월 성질, 하한 및 상한계산 방법을 개발하여 이를 이용하는 분지 한계 방법을 제시하였다.
본 논문에서 제안된 일정계획 문제들에 대한 알고리듬들의 성능은 실제 현장의 상황을 잘 반영할 수 있도록 생성된 문제들을 이용하여 많은 계산 실험을 통해 평가되었다. 또한 기존에 알려진 방법론들과의 비교실험을 통해 그 성능이 평가되었다. 실험 결과를 통해, 제안된 알고리듬들은 논문에서 다루고 있는 다양한 가용성 제약을 고려한 일정계획 문제들에 대해 현실적인 시간 내에 최적해 혹은 우수한 해를 찾아낼 수 있음을 확인하였다.
