Hybrid Algorithm Of CP And BAB For Solving Job-shop Problems

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.