In this thesis, we focus on a scheduling problem on parallel machines considering a job splitting property with the objective of minimizing total tardiness. In this problem, a job can be split into a discrete number of sub jobs and they are processed on the parallel machines independently. Although the job splitting reduces tardiness of the job, it also increases setup frequency. We suggest a two-phase heuristic algorithm for this problem. In the first phase, an initial sequence is constructed by an existing heuristic method for the parallel machine scheduling problem. Then, an appropriate number of sub jobs is determined and these sub-jobs are sequenced on each machine. To evaluate performance of the proposed algorithm, computational experiments are performed on randomly generated problems. Results of the tests show that the suggested method performs better than a method modified from an existing method.
본 논문은 작업 분할이 있는 병렬기계에서의 일정계획 문제를 다루고 있다. 본 문제의 목적은 납기 지연을 최소화 하는 일정계획을 구하는 것이다. 본 문제에서 각 작업은 정수 개의 하위 작업으로 분할되며, 분할된 하위 작업들은 서로 다른 기계에서 독립적으로 가공 될 수 있다. 각 작업이 여러 개의 하위 작업들로 분할 될수록 작업의 납기 지연이 줄어드는 반면, 작업 준비 횟수는 늘어나게 된다. 본 문제를 풀기 위해서 2 단계의 휴리스틱 방법론을 제안하였다. 첫 번째 단계에서는 기존의 방법론을 이용하여 병렬 기계에 대한 초기 일정계획을 구한다. 두 번째 단계에서는 각 작업의 분할 횟수와 분할된 하위 작업의 일정계획을 수립한다. 제안된 방법론을 기존의 알고리듬과 무작위적으로 발생시킨 문제로 비교해 본 결과, 본 연구에서 제시한 알고리듬이 더 좋은 결과를 보였다.
