Single-machine scheduling is the process of determining the order of tasks to be performed in a single machine. Typically, process times are assumed to be deterministic in scheduling problems. However, in real life problems, processing times can be uncertain and in such cases, using deterministic model often gives solutions that are highly volatile in performance.
In this study, method of obtaining robust solution which minimizes total tardiness under process time uncertainty is proposed. A solution is considered a robust solution when total tardiness of a schedule is within a given value although the processing times vary as specified in an uncertainty set. The problem is formulated as a mixed integer programming model. Computational experiments show that the solutions obtained through this method successfully provides robust schedules.
We also propose methods to identify meaningful range of the parameter for robustness of the solu
tions. Algorithms to obtain them are illustrated and computational experiments are conducted to test the algorithms.
단일 기계 스케줄링 문제는 하나의 기계와 여러 개의 처리해야 할 일들이 주어졌을 때 일들의 처리
순서를 결정하는 문제이다. 일반적으로 스케줄링 문제에서 일들의 처리 시간은 예측 가능하고 고정되어
있다고 가정한다. 하지만 실제로는 처리 시간이 불확실한 경우가 대다수이며 이 때 처리 시간을 평균값이나 중앙값으로 두고 스케줄링 문제를 풀 경우 목표 값의 변동성이 큰 스케줄을 얻기 쉽다.
본 연구에서는 총 지체된 시간을 최소화하는 단일 스케줄링 문제에서 처리 시간이 불확실성을 가질 때
강건한 스케줄을 얻는 방법을 제시한다. 스케줄링 문제에서 처리 시간이 불확실성을 가질 때 총 지체 시간이 특정 값을 넘지 않는 스케줄을 강건한 스케줄이라고 정의한다. 본 연구에서는 강건한 스케줄을 얻는 문제를 혼합 정수계획법으로 수식화 하고 풀게 된다. 그리고 실험을 통해 이러한 방법으로 얻어진 해법들이 강건한 스케줄을 제공해줌을 보인다.
또한 강건한 스케줄을 얻는 문제에서 쓰이는 매개 변수들의 유의미한 범위를 분석하고, 이 범위를 구
하는 알고리즘을 제시하며, 실험을 통해 제시된 알고리즘이 비교적 빠른 시간 안에 필요한 값들을 구함을 보인다.
