Dissertation > Excellent graduate degree dissertation topics show

Genetic Algorithm-Ant Colony Algorithm in Job-Shop Scheduling Research

Author: WuTongWei
Tutor: HuangMing
School: Dalian Jiaotong University
Course: Applied Computer Technology
Keywords: Genetic Algorithm-Ant Colony Algorithm Single Breed Dynamic Fusion Job-Shop Scheduling
CLC: TP301.6
Type: Master's thesis
Year: 2010
Downloads: 123
Quote: 3
Read: Download Dissertation

Abstract


With the rapid development of market economy, the old production mode cannot satisfy the requirements of modern production, every enterprise has been improving production and operations management solutions in order to enhance their competitive advantage. In actual production process, enterprise needs reasonable production scheduling arrangements to enhance the production efficiency. So shop scheduling problem is of great theoretical and practical value, and thus people pay more and more attention to it. Shop scheduling problem is to solve how to allocate resources in correct time order to complete various production tasks in order to reach the intended objective optimization. Job-Shop scheduling problem is a simplified model of many practical shop scheduling problems, is a typical NP-hard problem.Based on genetic algorithm and ant colony algorithm, this paper designs a new genetic algorithm-ant colony algorithm for solving the Job-Shop scheduling problem. For Job-Shop scheduling problem character, in this paper we use the encoding method based on job number sequence and try to dynamically integrate the two algorithms to solve the Job-Shop scheduling problem. As the encoding method based on job number sequence is not suitable for cross-breeding, we design a new single breeding method, and in reproduction and variation operations, use the dynamic control mechanism and local search mechanism to avoid inefficient, useless breeding and variation, quickly generate good chromosomes; once genetic algorithm become redundant and inefficient, then transfer to ant colony algorithm immediately, choose the best chromosomes group and converts them to the initial distribution pheromone for ant colony algorithm, use ant colony algorithm’s distributed, parallel, positive feedback ability to efficiently solve shop scheduling problem;when ant colony algorithm performance reduced, use algorithms callback strategy, transfer part of the current optimal values to initial population for genetic algorithm, use genetic algorithm to re-search in this optimal set;if the two algorithms can produce a new optimal solution in callback operation, the callback operation will not stop, until the two algorithms are completely degraded and have no progress, the whole algorithm will end and output the optimal solution. Algorithm callback strategy ensures that the genetic algorithm-ant colony can fully search in the solution space.Finally, GA-ACA is applied to realize a shop scheduling simulation system, the classic instance of Job-Shop problem is used to assess the efficiency of the algorithm, and the algorithm is applied to solve Job-Shop scheduling problem, results show that the convergence of GA-ACA is more efficient, faster and the new algorithm is practical and efficient in solving Job-Shop scheduling problem.

Related Dissertations

  1. Research and Improvement of Tabu Search Algorithm for Job Shop Scheduling Problem,TP391.3
  2. Research of Improved Hopfield Neural Network Algorithm on Single Dynamic Scheduling Problem,F224
  3. The research and development of the job shop scheduling and management system based on MRP and OPT,TP315
  4. Multi-Objective Shop Scheduling Algorithm Based on Particle Swarm Optimization,F224
  5. Sea Test Location Problem Based on Hybrid Particle Swarm Optimization,TP301.6
  6. Research of Scheduling Methods Based on Swarm Intelligence for Uncertainty Production Processes,TP273
  7. On Job-shop Scheduling by Improved Quantum Genetic Algorithm,TP18
  8. For single and small batch production of MES Job Shop Scheduling,F224
  9. The Optimization and Simulation on Shop Scheduling Problem Based on Improved Genetic Algorithm,F273
  10. Enterprise Production & Sale Management System and Design & Implementation of Production Scheduling Algorithm,TP311.52
  11. Research on Gene Expression Programming and Its Application on Scheduling Problems,TP311.11
  12. Job Shop Shedule Management System Research Based on Samll Lot Production Enterprises,TH164
  13. Hybrid ant colony algorithm - based job-shop scheduling problem solving,TP301.6
  14. The Research on Job Shop Schedule System Based on Simulation and Its Application,TH164
  15. Research of Ant Colony Algorithms Hybrid Genetic Algorithms to Solve VRP in Physical Distribution,TP18
  16. Study on Job Shop Scheduling Problem with Function-Same Machines,TP399-C2
  17. Research on Multiprocessors Scheduling Algorithm in Distributed System,TB115
  18. A Hybrid Ant Colony Optimization for the Job Shop Scheduling Problem,F273
  19. Ant colony algorithm parameter optimization and its application,TP301.6
  20. Characteristic Analysis and Improved Tactic Research of Traditional Optimization Methods in Solving Job-shop Scheduling Problem,O224

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile