This thesis considers a problem of minimizing total tardiness on a two parallel batch-and-single machines system which consists of a batch-processing machine and a single machine. The batch-processing machine can process several jobs together according to its capacity, and all these jobs have the same completion time. The jobs are grouped in incompatible job families, where all jobs of the same family have identical processing times and jobs from other job families cannot be processed together on the batch-processing machine. Some solution properties and a SPT (shortest processing time) based lower bound are derived, and then applied in a Branch-and-Bound algorithm. Numerical experiments showed that solution properties and the lower bound contribute a lot to the performance of the algorithm.
본 논문에서는 두 대의 기계로 구성된 병렬 시스템의 스케줄링 문제를 다루고 있다. 그 두 대의 기계중 하나는 뱃치 기계이고, 하나는 단독 기계이다. 뱃치 기계는 그의 용량에 따라 여러개의 job들을 동시에 처리할 수 있고, 단독 기계는 job을 하나씩 처리할 수밖에 없다. Job들은 incompatible job 패밀리로 분류되고, 뱃치 기계가 같은 job 패밀리의 job들만을 동시에 처리할 수 있다. 목적함수는 total tardiness를 최소화하는 것이다. Solution property 들을 제안하면서 SPT rule 에 기반한 Lower bound를 이용한 Branch-and-Bound algorithm을 구현되었다. 이 알고리즘을 다양한 문제에 대하여 실험하고 평가한 결과, 제안된 알고리즘이 효율적으로 최적해를 도출함을 보여주었다.
