Minimizing the total completion time for parallel machine scheduling with job splitting and learning

• A parallel machine scheduling problem with job splitting and learning is proposed.
• A branch-and-bound algorithm is proposed to solve small sized problems.
• Several heuristics are proposed to solve the large-sized problems.
• The greedy search which utilizes analytical property outperforms other heuristics.

This paper examines parallel machine scheduling with the objective of minimizing total completion time considering job splitting and learning. This study is motivated by real situations in labor-intensive industry, where learning effects take place and managers need to make decisions to split and assign orders to parallel production teams. Firstly, some analytical properties which are efficient at reducing complexity of the problem are presented. Utilizing the analytical property of the problem, a branch-and-bound algorithm which is efficient at solving small-sized problems is proposed. For the large-sized problems, several constructive heuristics and meta-heuristics are presented. Among them, the greedy search, which can take both the current profit and future cost after splitting a job into consideration, obtains a near-optimal solution for the small sized problems and performs best in all proposed heuristics for the large sized problems. Finally, extensive numerical experiments are conducted to test the performance of the proposed methods.