From theory to practice: optimizing makespan in no-wait jobshops with no-passing constraints

This paper addresses the hitherto unexplored NP-complete problem of minimizing the makespan in no-wait jobshops with no-passing constraints. Motivated by the significant gap in the scheduling literature and practical applications, our study aims to design an efficient and effective matheuristic algorithm that can overcome computational barriers to the optimal solution of this problem. Extensive computational experiments on four benchmark datasets demonstrate that the proposed algorithm consistently yields optimal solutions for problems containing up to 1000 jobs, and efficiently solves ultra-large instances with up to 2000 jobs and 20 machines within a time limit of four hours. These promising results not only validate the effectiveness of the algorithm but also underscore its potential for addressing intricate scheduling challenges with practical relevance. The contributions of this work include the development of a theoretically sound and computationally efficient matheuristic paradigm tailored to a highly challenging scheduling problem, and the advancement of both theoretical understanding and practical applications in industrial settings.