A new heuristic for job shops with no-wait and blocking constraints

Traditional job shop scheduling problems assume that there are buffers with infinite capacity available, which is not always true in the real world. We consider job shop scheduling problems with operations that have to start immediately after their predecessor operation is completed (no-wait precedence constraint) or the resource of the completed operation is not released until the resource of the next operation is released (blocking precedence constraint). An application is the planning of shunting movements in a railway system. A new heuristic and an integer programming formulation for a job shop with precedence constraints that are blocking or no-wait are presented. The heuristics known in literature have the main disadvantage that they do not always find a feasible solution. The heuristic presented here always finds one and tests show that the solutions found are of a good quality