Parallel machine scheduling considering a job-splitting property

Abstract

This paper focuses on the problem of scheduling jobs on parallel machines considering a job-splitting property. In this problem, it is assumed that a job can be split into a discrete number of subjobs and they are processed on parallel machines independently. A two-phase heuristic algorithm is suggested for the problem with the objective of minimizing total tardiness. In the first phase, an initial sequence is constructed by an existing heuristic method for the parallel-machine scheduling problem. In the second phase, each job is split into subjobs considering possible results of the split, and then jobs and subjobs are rescheduled on the machines using a certain method. To evaluate performance of the suggested algorithm, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested algorithm performs better than an existing one.