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

This paper addresses the scheduling problem of a class of automated manufac turing 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 oper ations. Each operation may need more than one resource. Upon the completion of an operation, resources needed in the next operation of the same job ca nnot be released and the remaining resources cannot be released until the s tart of the next operation. The scheduling problem consists in sequencing t he 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 us ing an original neighborhood structure defined by two basic moves: the perm utation of disjunctive arcs of critical paths and a deadlock recovery move if the former fails. Numerical results presented in the paper show the effi ciency of the proposed algorithm.