A TUTORIAL SURVEY OF JOB-SHOP SCHEDULING PROBLEMS USING GENETIC ALGORITHMS .1. REPRESENTATION

Job-shop scheduling problem (abbreviated to JSP) is one of the well-kn own hardest combinatorial optimization problems. During the last three decades, the problem has captured the interest of a significant numbe r of researchers and a lot of literature has been published, but no ef ficient solution algorithm has been found yet for solving it to optima lity in polynomial time. This has led to recent interest in using gene tic algorithms (GAs) to address it. The purpose of this paper and its companion (Part II: Hybrid Genetic Search Strategies) is to give a tut orial survey of recent works on solving classical JSP using genetic al gorithms. In Part I, we devote our attention to the representation sch emes proposed for JSP. In Part II, we will discuss various hybrid appr oaches of genetic algorithms and conventional heuristics. The research works on GA/JSP provide very rich experiences for the constrained com binatorial optimization problems. All of the techniques developed for JSP may be useful for other scheduling problems in modern flexible man ufacturing systems and other combinatorial optimization problems. Copy right (C) 1996 Elsevier Science Ltd