A genetic algorithm approach to job shop scheduling.

摘要

Scheduling problems have been studied during the last fifty years by theoreticians and practitioners in all fields, especially Operations Research, Industrial Engineering, and Computer Science. These problems are generally described to be NP-complete1 and any method to solve a scheduling problem will probably fail to search the total solution space. This research is focused on the application of Genetic Algorithms to job shop scheduling problems (JSP).; The four main components of a genetic algorithm are choosing a chromosome syntax, interpretation of a chromosome, evaluation of a chromosome, and the operators on chromosomes. In this research, a new three-dimensional chromosome syntax and some new and modified operators are introduced to solve job shop scheduling problems. This research will show that once a feasible schedule population is created, due to the three-dimensional chromosome syntax and operators introduced in this research, each subsequent population will consists of all feasible schedules.; The new algorithm is tested by solving benchmark problems from the literature, including two well-known problems by Fisher and Thompson (1963). The results obtained on these problems are comparable to the other solution methods and show the appropriateness of the new genetic algorithm for job shop scheduling problems (JSP). Also, a new set of problems with precedence relations (relations between operations of jobs on the same machine), non-zero ready times of jobs, and resource constraints with a limited amount of resources are created randomly and solved by the new genetic algorithm.; Although minimizing makespan is the objective function used in this research to be able to compare the results with other solution methods, the algorithm can easily be adopted to use any other objective function, e.g. number of tardy jobs, average tardiness, mean flowtime, average completion time, etc.; 1The time to compute a solution as a function of the number of data inputs cannot be defined as a polynomial, hence the name nonpolynomial, or NP-complete. See reference 59, Lenstra, Khan and Brucker for a complete discussion.