Laboratoire de Génie Informatique et d’Automatique de l’Artois

Scheduling deals with the allocation of tasks requiring processing to limited resources over time in areas including product manufacturing, computer processing and transportation. In this thesis we review the properties of both the general scheduling and cyclic scheduling problems with a focus on the cyclic version of the problem. The NP-Hard complexity of the cyclic scheduling problem has motivated this research work in developing an efficient neural network approach to solving this problem. This thesis focuses specifically on the cyclic job shop and cyclic flexible manufacturing system problems. Hence, models that will solve the minimum cycle time or work in progress of the problems are developed. Here, we develop and study three variations of the recurrent neural network approach. These are the Recurrent Neural Network (RNN), the Lagrangian Relaxation Recurrent Neural Network (LRRNN) and the Advanced Hopfield network approaches. Several algorithms are combined with these neural networks to ensure that feasible solutions are generated and to reduce the search effort for the optimum solutions. We also extend the review to include the cyclic job shop problem with linear precedence constraints. A delinearization algorithm is developed to solve this problem; an approach based on transforming the linear constraints of the problem into its uniform constraints as proven in existing cyclic scheduling literature. Through computational and comparative testing, we are able to demonstrate the suitability and applicability of the RNN, LRRNN and Advanced Hopfield network approaches as attractive alternatives to traditional heuristics in solving these cyclic scheduling problems.