Abstract:An identical parallel machine scheduling problem with job splitting to minimize makespan is studied to decrease the completion time of the job. In this problem, each job can be split into sections, which can be processed in parallel on different machines. There is at most one part of each job on a machine. Different from researches in the scheduling literatures, there is a restriction for the split, i.e. the size of each split section cannot be smaller than a given value and the splitting actions should be kept as less as possible in the number of times. For this NP-hard problem, a heuristic algorithm is developed based on the LPT algorithm. Using the algorithm, job is split and assigned automatically. The performance of the algorithm is evaluated through a number of numerical instances. The results show that the algorithm is feasible and fine in stability. This algorithm can be applied to solving parallel machine scheduling problem,in which the split has the similar restriction.