Minimizing total tardiness on parallel machines with job splitting property

Abstract

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.