This research considers a single machine scheduling problem in which the machine is supposed to be stopped periodically to perform maintenance. The objective is to minimize total tardiness of all jobs which are non-resumable. To deal with the problem, a mathematical formulation is developed to find optimal solutions. In addition, two-phase heuristic algorithms which are based on Tabu Search and Simulated Annealing are derived to obtain near optimal solutions. In the heuristics, multi initialization strategy (MI) to enhance the search effectiveness is used. Computational experiments are performed to evaluate the efficiency of the formulation and the heuristics.
본 연구에서는 주기적인 정비로 인한 작업중단이 있는 단일머신 스케쥴링 문제를 해결하고자 한다. 목적은 재개시가 불가능한 작업들의 총지연시간을 최소화하는 것으로 한다. 수학적인 수식을 활용하여 작은 크기의 문제에 대하여 최적해를 구하였으며 추가적으로 큰 크기의 문제를 풀기 위하여 두 단계 휴리스틱 알고리듬을 개발하였다. 휴리스틱 알고리듬은 타부서치와 시뮬레이티드 어닐링 기법을 사용하였으며 최적해에 근사한 값을 주었다. 본 알고리듬에서는 해를 찾는 효율성을 높이기 위하여 다중 최초해 발견 기법이 적용되었다. 수식의 효율성과 휴리스틱 알고리듬의 성능을 보이기 위한 실험을 실시하였다.
