A taboo search approach for deadlock-free scheduling of automated manufacturing systems

This paper addresses the scheduling problem of a class of automated manufacturing systems. A new manufacturing system model is proposed. In this model, a set of jobs is to be processed and each job requires a sequence of operations. Each operation may need more than one resource. Upon the completion of an operation, resources needed in the next operation of the same job cannot be released and the remaining resources cannot be released until the start of the next operation. The scheduling problem consists in sequencing the operations on the resources in order to avoid deadlocks and to minimize the makespan. The classical disjunctive graph representation is extended to model the scheduling problem. A taboo search algorithm is then proposed using an original neighborhood structure defined by two basic moves: the permutation of disjunctive arcs of critical paths and a deadlock recovery move if the former fails. Numerical results presented in the paper show the efficiency of the proposed algorithm.