Research Of The Genetic Algorithms And Ant Colony Algorithm For Bi-direction Job Shop Scheduling

Job shop scheduling problem is a kind of most typical combinatorial optimization problems about resource distribution in which produce task is given. Lots of practical problems can transform with it. Bi-direction scheduling problem belongs to classical scheduling problem, however, its scheduling aim is not only makespan, but also taking deadline of the critical jobs into account, that is, under precondition of ensuring critical jobs to satisfy deadline, to reduce makespan as much as possible, so that in practical production we can decrease losses and increase profits efficiently. This sort of problem is more complex than common classical scheduling problems, but it is closer to real environment, therefore, there is significant academic and economic value in the research on it.First of all, this paper generally introduces some basic conceptions, definitions, classifications, and algorithms to get the solution and summarizes the research status quo and results about the relevant aspects.Secondly, this paper combines genetic algorithm with bi-direction scheduling problem, providing a feasible solution to bi-direction scheduling problem. Then this paper proves its feasibility by emulational experiment.Thirdly, this paper combines an ant colony algorithm with bi-direction scheduling algorithm to solve the job shop scheduling problem with the optimization aim of the makespan and deadline of critical jobs. Based on the traditional ant colony algorithm, we adjust the evaporation coefficientρadaptively, adopt new heuristic rules to define the visibility functionη_ij (t ) and update table allowed in a different way. Besides, the adaptive ant algorithm is proved to be better than genetic algorithm which is widely used nowadays in bi-direction scheduling.Last but not the least, I sum up the whole paper and present some proposals and prospects to future research.