Study on job-shop scheduling with multi-objectives based on genetic algorithms

摘要

Job-shop scheduling is a difficult type of production planning problem, of which the primary characteristic is that the processing route of each job is different. Job shop scheduling belongs to the special class of NP-hard problems. Most of the algorithms used to optimize this class of problems have an exponential time; that is, the computation time increases exponentially with problem size. In most studies on job-shop scheduling problems, the objective is usually to determine the sequence of jobs to minimize the makespan. The due date request of the key jobs, the availability of key machine, the average wait-time of the jobs and the similarities between jobs and so on are also the objectives to be considered synthetically in real manufacturing process. In this paper, the job shop scheduling problem with multi-objectives is analyzed and studied by using genetic algorithms based on the mechanics of genetics and natural selection. First, the description of this problem is given with its model. Then, the tactics of the coding and decoding and the design of the genetic operators, along with the description of the mathematic model of the multi-objective functions, are presented. Finally an illustrative example is given to testify the validity of this algorithm.