Integrating Scheduling with Optimal Sublot for Parallel Machine with Job Splitting and Dependent Setup Times

Abstract This paper addresses a novel problem of the parallel capacitated machines with job splitting and dependent setup times (PCMS), Pmc|split, pj, sjp|Cmax. A mixed integer programming (MIP) model is developed to find an optimal schedule with minimum makespan. Since the problem is NP-hard, metaheuristics are required to find a near optimal solution for larger, more practical problems. Therefore, this paper presents the first applications of two effective metaheuristics, Particle Swarm Optimization (PSO) and Differential Evolution (DE) with a solution representation scheme for solving the problem. To evaluate the metaheuristics’ performances, the lower bound is also firstly developed. Experimental results reveal that, in the small-size problems, there are no distinctive differences between the two algorithms’ performances, since both algorithms are able to find the optimal solutions. However, for medium to large size problems, the DE outperforms the PSO by providing significantly superior results of makespan for 22 out of 27 instances.