Mathematical modelling and heuristic approaches to operation scheduling problems in an FMS environment

This paper addresses an operation scheduling problem with the objective of minimizing total tardiness in a flexible manufacturing system with setup ti me 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 heuris tic begins on a schedule generator called ESCH to obtain an initial solutio n; then two procedures are designed to improve the solution quality. One is a sequence-improving procedure (SIP) for determining a better performance schedule from a certain routing plan; the other is a routing-exchanging pro cedure (REP) for selecting a good routing plan. Both procedures are achieve d by simulated annealing. Computational experiments show that the proposed simulated annealing based heuristic performs well with respect to solution accuracy and efficiency.