Dissertation > Excellent graduate degree dissertation topics show

Hybrid Algorithm of CP and BAB for Solving Job-shop Problems

Author: TanYuanYuan
Tutor: LiuShiXin
School: Northeastern University
Course: Systems Engineering
Keywords: comstraint programming BAB algorithm job-shop scheduling constraint propagation integration algorithm
CLC: TP301.6
Type: Master's thesis
Year: 2009
Downloads: 26
Quote: 0
Read: Download Dissertation

Abstract


Along with market economy development, corporations’competition become intense day by day, how better to carry on the job-shop scheduling、optimize resources deployment and raise the production efficiency, become the competicitve dominance whether the production enterprises grow strong. Job-shop scheduling problem belongs to the combination optimization category, with high complexity、multi-constraint and dynamic random, it has been proved as typtical NP-hard problem, its rearch has great theoretical and practical significance. Therefore, it’s become the manufacturers’ and general schorlars’research hot ’spot. Branch-and-bound (branch-and-bound, BAB) algorithm is one of the important accurate algorithms, received great attention from scholars at home and abroad. BAB algorithm can find the optimal solution, but lower pace and more memory space is the bottleneck of the study. In order to improve the performance and quicken the search space, it’s a new challenges to combine constraint programming (constraint programming, CP) and BAB solving the job-shop scheduling problem.The paper gives the definition of the job-shop scheduling problem and the possible direction of research; describes the classification of shop scheduling problem, the main characteristics and the current scheduling algorithm. Introduce the scheduling model and the currently mainstream CP.The paper gives the problem’s model and the hybrid algorithm of BAB and CP. For the job-shop scheduling problem, the main points of this paper as follows:(1) This paper proposes a constraint propagation algorithm in which both precedence constraint and resource constraint are taken into consideration. Experimental results verify feasibility and effectiveness of the method.(2) In this paper, we combine CP with BAB algorithm; make the best of CP technology cutting branches, the characteristics of this hybrid algorithm focus on the improving of the optimization performance and dealing with complex restriction ability. Based on the 1994 Peter Brucker only applied input/output to BAB, we add input/output negation、inputoroutpu(?) to BAB to solve job-shop scheduling problem. Experimental results show that the order of input/output→input/output negation→input-or-output is best. It can be conclude that CP technology is applied appropriate to BAB to effectively reduce the search space and improve the optimal effectiveness and efficiency.Finally, this article points out the shortcomings and the direction of further research.

Related Dissertations

  1. Research on Scheduling of Whole-set Orders in JSP Based on Differential Evolution Algorithm,F273
  2. Efficient Algorithms for the Job Shop Scheduling Problem,O224
  3. Research on Job Shop Scheduling Problem Based on Critical Path Method,F273
  4. Solving Job Shop Scheduling Problem Based on Natural Computation,TP18
  5. Development and Simulation Analysis of Job-shop Scheduling System,TH165
  6. Based hybrid algorithm for job shop scheduling problem,TH186
  7. Job Shop Scheduling Problem Based on Immune Clonal Selection Algorithm,TP18
  8. Cellular Particle Swarm Optimization and Its Applications on Flexible Job Shop Scheduling Problem,TP301.6
  9. Multi-Objective Flexible Job Shop Scheduling Problem Based on Hybrid Particle Swarm Optimization,TP301.6
  10. Algorithm Design for Multi-objective Flexible Job Shop Scheduling Problems,TP301.6
  11. Algorithm Designing of Varible Batch Flexible Job-shop Scheduling with Multi-products,TP301.6
  12. Immune genetic algorithm and its application in the field of job shop scheduling application,TP18
  13. Research on Optimization Methods for Uncertainty Job Shop Scheduling,O224
  14. MES for single and small batch Job Shop Scheduling Problem,TP315
  15. Research and Application of the Workshop Scheduling System Based on MES,TP311.52
  16. Research of Improved Hopfield Neural Network Algorithm on Single Dynamic Scheduling Problem,F224
  17. Constraint Propagation Based Algorithms for Solving Resource-Constrained Project Scheduling Problems,F270
  18. The Research on Location of the Leak of Natural Gas Based on the Wavelets Analysis,TE973.6
  19. Research on Job-shop Scheduling Problem Based on Immune Genetic Algorithm,TP18
  20. Research on Job Shop Scheduling Problem of the Elevator Car Production Based on Genetic Simulated Annealing Algorithm,TP18
  21. Research of Qualitative Simulation Based on Quantitive Information,TP391.9

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