A disjunctive graph for the Job Shop Problem with Transport and blocking no wait constraints

This paper addresses the scheduling problem of job shop with transport and Blocking no wait constraints. This NP-Hard problem is an extension of the classical job shop problem that take into account transport operations by several robots and the absence of storage space between machines.. The objective is to determine a schedule of machine and transport operations as well as an assignment of robots to transport operations with minimal makespan. The problem can be efficiently modeled by a disjunctive graph and any solution can be fully defined by an orientation of the graph. We formulate the problem by means of a new disjunctive graph. We present a solution representation based on two vectors. We modelized blocking situations and described properties of partial schedule that lead to deadlock situations. The new disjunctive graph and deadlock situations properties served us to develop a greedy heuristics based on priority and avoiding blocking cycle rules. Computational results are reported. This paper is a step forward definition of an efficient approach for the resolution of the job shop problem with several robots and blocking no wait constraints.