Constraint programming and biased random-key genetic algorithm for the single-machine coupled task scheduling problem minimizing makespan

In this paper, we consider a single-machine coupled task scheduling problem to minimize the makespan. In this problem, a set of jobs has to be scheduled, each composed of two tasks interspersed by an exact delay. No preemption is allowed and the goal consists of minimizing the completion time of the last scheduled task. We propose a constraint programming model and a biased random-key genetic algorithm (BRKGA) for the problem. Preliminary results show that the constraint programming model can achieve high-quality solutions and strong dual bounds within the provided time limit. Moreover, it can find a solution that at least matches the best-known available in the literature for all the instances but one in our preliminary set. The obtained solutions are strictly better than the best known ones for more than 70% of the tested instances. Additionally, the BRKGA can find solutions with reasonably low gaps within short computational times.