Mathematical modelling and heuristics approaches to operation scheduling problems in a flexible manufacturing systems environment

This paper addresses an operation scheduling problem with the objective of minimizing total tardiness in a flexible manufacturing system with setup time consideration. The addressed problem is first described as a 0–1 integer programming model, and is then solved optimally. Subsequently, a heuristic is proposed to solve the problem in an acceptable running time. The heuristic begins on a schedule generator called ESCH to obtain an initial solution; then two procedures are designed to improve the solution quality. One is a sequence-improving procedure for determining a better performance schedule from a certain routing plan; the other is a routing-exchanging procedure for selecting a good routing plan. Both procedures are achieved by simulated annealing. Computational experiments show that the proposed simulated annealing based heuristic performs well with respect to solution accuracy and efficiency.