Abstract
This study focuses on the problem of scheduling jobs on identical parallel machines with job-splitting property. In this problem, it assumed that a job can be split into several sub-jobs, and these sub-jobs can be processed on different machines simultaneously. Each job has a processing time, a ready date and a due date. If a sub-job of a job is assigned after a sub-job of another job on a machine, a sequence-dependent setup time is incurred. A two-phase heuristic algorithm is proposed to minimize the total tardiness. In phase 1, five efficient heuristic methods are proposed. In phase 2, the sub-job of tardy jobs in the schedule provided by phase 1 are further split, and the split sub-jobs are rescheduled on the machines to reduce the total tardiness. Computer experiments show that the proposed algorithm outperforms a previously suggested algorithm.