A MILP model to minimize total tardiness in a job shop scheduling problem with blocking and no-wait constraints

¹ LaROMaD Laboratory, Faculty of Mathematics, University of Science and Technology Houari Boumediene, Bab Ezzouar, Algiers, Algeria
² LIST laboratory, Faculty of Technology, University of M’hamed Bougara of Boumerdes, Boumerdes, Algeria

^* Corresponding author: zineb.lissioued@usthb.edu.dz

Received: 23 December 2024
Accepted: 25 July 2025

Abstract

This paper deals with job shop scheduling problem (JSS) where both blocking and no-wait constraints (BNW) are considered. The blocking constraints are linked to storage capacity constraints. They appear when job completed by a machine and must be stored on this machine as long as the next machine that will process it is occupied by another job. The no-wait constraints, for their part, occur when a job must be processed continuously on different machines without any interruption between operations. The objective is to find a feasible order of operations on machines that minimizes total tardiness under blocking and no-wait constraints. To our knowledge, no study has treated this problem in the literature. To tackle this NP-hard problem, we propose, based on the mathematical model given by Lange and Werner [J. Sched. 21 (2018) 191–207], to solve the blocking and no-wait (BNW) job shop scheduling problem. The BNW-JSS problem is formalized as a mixed-integer linear programming model (MILP). Several numerical experiments were performed using the CPLEX solver on the classical benchmark instances of Lawrence. This allowed us to assess the effectiveness of our model on the one hand and to report results for the BNW-JSS problem on the other hand.