A Branch And Bound Method For The Open Shop Scheduling Problem

As one of the core issue for manufacturing system optimization, scheduling problem has received great attentions.Open shop scheduling problem is an very important branch of production scheduling problem and a hard combinatorial optimization problem.Because of the wide application field,it has been paid more and more attention.In many real industrial settings,some setup is carried out before the process of a job. Usually,the magnitude of this setup depends on the order of two consecutive jobs. In this case, the setup is called sequence dependent.In this paper Branch and Bound Method is utilized to solve the open shop with sequence dependent setup times to minimize makespan.When scheduling problem is solving optimally,Branch and Bound is usually used. But the solving process is very complex and time is cosumed largely.So it is not applied widely in real settings.Especially at present,almost all kinds of intelligent optimization algorithm are becoming main stream of scheduling algorithms.However,because most intelligent optimization algorithms are random optimization algorithm,they can not guarantee the qulity of solution gained every time.Furthermore,parameter chosen in algorithm running and constraint of algorithm ended etc. are difficult to obain general regular. Therefore, researching branch and bound method and other traditional optimization method is still important significative and valuable.Designing good upper bound (UB) and lower bound (LB) is the key to gain optimal solution in branch and bound method.The better the quality of the UB and LB are,the more useless branch nodes can be removed,and thus accelerate the speed of solving.In this paper, good UB and LB method is presented,and it can solve quite optimally.But there is no good Dominance Rule,therefore a lot of time must be wasted in useless branch nodes. Through the experimental results the qualities of the UB algrithms are compared.But in real settings,it depends on datas.Finally,several future research directions are presented.