Research On Production Scheduling Based On Genetic Algorithm With Insertion Techniques

Research on production scheduling is improtant for enterprises to improve theirmanagement level and enhance their market competitiveness. Production schedulingis a typical combinatorial optimization problem. Most of them are NP problem. Dueto their complexity, exact mathematical optimization approach to determine anoptimal solution may not be efficient in practice. This has motivated researchers todevelop heuristic algorithms for dealing with these problems. This paper will studythree model of production scheduling: the single machine scheduling problem of jobswith unequal release times and due dates, classic job-shop problem and the job-shopproblem with time-lags. The concrete contents are as follows.First, we study the single machine scheduling problem of jobs with unequalrelease times and due dates. The objective is to minimize the sum of the tardiness. Aheuristic insertion algorithm is established to solve this problem. We also design ahybrid genetic algorithm for solving this problem. The insertion algorithm is used toproduce a part of the initial solution of thegenetic algorithm, and is employed as themutation operator of the genetic algorithm. Numerical experiments show that thegenetic algorithm designed in this paper can get better solutions for this problem.Second，we study the classic job-shop problem and the optimization objectives isto minimize the sum of the tardiness. A heuristic insertion algorithm and a geneticalgorithm are designed to solve the problem. The insert heuristic algorithm is used asthe mutation operator of the genetic algorithm. Experimental results show that theproposed algorithm can derive better solution for these problems.Finally, the job-shop problem with minimal and maximal delays is discussed.The objection is to minimum makespan. According to the network diagram and amixed integer linear algorithm, we present a heuristic insertion algorithm to determinefeasible insertion point of the operation. A genetic algorithm is designed for slovingthe job shop scheduling problem with time lags. The insertion algorithm is used as themutation operator. It is verified that the insertion and genetic algorithm are highefficiency and practicality through the experiment...