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

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

0.00 Avg rating0 Votes
Article ID: iaor20062617
Country: Netherlands
Volume: 12
Issue: 5/6
Start Page Number: 535
End Page Number: 552
Publication Date: Oct 2001
Journal: Journal of Intelligent Manufacturing
Authors: , ,
Keywords: manufacturing industries
Abstract:

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 tabu 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.

Reviews

Required fields are marked *. Your email address will not be published.