The Research Of Job Shop Scheduling Problem Based On Intelligence Computation

The job shop scheduling problem (JSP) is a very important practicalproblem in both fields of production management and combinatorialoptimization. Efficient methods for arranging production and schedulingare very important for increasing production efficiency, reducing cost andimproving product quality. JSP is among the worst members of class ofNP-complete, the study of it started from the year 1954, so far, there havebeen many methods for solving it, such as branch and bound, dynamicprogramming, shifting bottleneck, Lagrangian relaxation and tabu search.In this paper, we propose three intelligence computations,they areGenetic Algorithm, Ant Colony Algorithm,Particle SwarmOptimization, to solve the job shop scheduling problem.The first, A genetic algorithm to solve Job-shop SchedulingProblem(JSP) is presented,its coding based on preference list. Throughanalyzing the mathematical model of JSP, we put forward: (1) deadlockproblem and its solve method; (2) an algorithm of making the feasiblescheduling; (3) an algorithm of computing the fitness function; (4) threegenetic operator and the assist operator--modify operator. There are anumber of unfeasible scheduling solutions in the Job-shop Scheduling Problem(JSP), it strongly affects the quality of Genetic Algorithms(GA)searching for the best solution. In this paper, we put forward the graphicaltheory model of JSP, and analysis the cause of unfeasible scheduling andits characteristic, then educe the sufficient and necessary condition that afeasible scheduling solution requires. So we improve on the encodingschema base on operation of GA to solve JSP, it reasonably reducesoccurrence of the unfeasible scheduling solution, then greatly enhance thequality of GA.The second, a special ant colony algorithm(ACA) applied to the JSP ispromoted. In the ant colony algorithm, the earliest allowed processingtime(EAPT) is considered as the heuristic information, the process of theant colony algorithm is promoted, several binds of benchmarks based onACA are simulated.The last, A common flow procedure of particle swarm optimizationfor the job shop scheduling problem is introduced, and the key problem ofthe design for the particle representation is analyzed. In the particle swarmsystem, a novel concept for the distance and velocity of particles isexpanded to pave the way for the JSP.