ABSTRACT
Chapter 8 Solving Job-Shop Scheduling Problems by Means of Genetic Algorithms Ramiro Varela*, Camino R. Vela*, Jorge Puente*, Alberto Gomez** and Ana M. Vidal
*Centro de Inteligencia Artificial. **Dpto. de Admon. de Empresas y Contabilidad Universidad de Oviedo. Campus deViesques. E-33271 Gijón. Spain. Tel. +34-8-5182032. FAX +34-8-5182125. e-mail: *{ramiro, camino, puente}@aic.uniovi.es, **agomez@etsiig.uniovi.es http:\\www.aic.uniovi.es
8.1 Introduction It is well known that sequencing problems are a subclass of combinatorial problems that arise everywhere. We can find problems of this class in many areas of industry, management and science, ranging from production organization to multiprocessor scheduling. This not only justifies the intensive research carried out in this field over the last several years (5, 6, 13, 16), but also the interest in finding new solutions to specific problems. Because sequencing problems are in general NP-hard, the only practical approaches are heuristic strategies (16, 25). Hence, one can find the application of almost every artificial intelligence technique; for instance, logic programming (12, 27), neural nets (1), machine learning (29), space state heuristic search (2, 11, 22), branch and bound (21), local search (25) and genetic algorithms (GAs) (4, 7, 19, 24, 17), among others. Jain and Meeran (13) summarize the main techniques applied to solve a family of these problems, the job-shop scheduling problem, together with the category each technique belongs to. The application of GAs to scheduling problems has interested many researchers because they seem to offer the ability to cope with the huge search spaces involved in optimising schedules. In this work we describe an approach to solve job-shop scheduling problems by means of a GA which is adapted to the problem in various ways. First, a number of adjustments of the evaluation function are suggested, and then we propose a strategy to generate a number of chromosomes of the initial population that allows us to introduce heuristic knowledge from the problem domain. In order to do that, we exploit the variable and value ordering heuristics proposed by Norman Sadeh (22). These are a class of probability-based heuristics which are, in
principle, aimed to guide a backtracking search strategy. We validated all the refinements introduced on well-known benchmarks and report experimental results showing that the introduction of the proposed refinements have an accumulative and positive effect on the performance of the GA. The software we have used in our experiments, as well as further releases, will be public through our Web site. The remainder of this chapter is organized as follows. Section 8.2 introduces the job-shop constraint satisfaction problem. Section 8.3 describes the genetic algorithm used in this work, in particular the codification of chromosomes and the genetic operators; and discusses two possibilities to define the fitness function, as well as the refinements proposed to the evaluation function (i.e., the penalty and scaling techniques) and how these techniques can be adapted to the confronted problem. Section 8.4 reviews the variable and value ordering heuristics proposed by Sadeh. Section 8.5 describes the way we propose to generate the initial population from the probabilistic knowledge provided by these heuristics. Section 8.6 reports the experimental results; here, we consider results about the efficiency and convergence of various versions of the GA, and compare the GA performance against other approaches. And finally, in Section 8.7, we present the main conclusions and some ideas for future work.
