On Dynamic Flow Shop Makespan Problems Based On Branch And Bound Algorithm

In a flow shop scheduling problem,each job must be processed on different machines in the same machine order.The goal is to determine the job sequence to optimize the predetermined objective function.At any given time,each machine can process at most one job,and each job can be handled at most one machine.Meanwhile,each job can't be preempted by the other jobs.Flow shop problems widely exist in industrial production,and most of them are strongly NP-hard,which means that it is impossible to obtain the global optimum solution in polynomial time.So it's also difficult to get the optimum solution even for small-scale flow shop scheduling problem.Three types of dynamic flow shop scheduling problems,minimizing makespan as objective function,are investigated in this thesis.New branch and bound algorithms are presented for small-size problems,respectively.And computational experiments are conducted to reveal the effectiveness of the proposed branch and bound algorithms.The contents are summarized as follows.Firstly,a new branch and bound algorithm is presented for slow shop minimizing makespan problem with release dates.Moreover,branching strategy,pruning rules and a new lower bound of the new algorithm are presented.At the end of the section,computational experiments reveal the effectiveness of the new branch and bound algorithm compared with the CPLEX algorithm.Secondly,a new branch and bound algorithm is presented for blocking flow shop minimizing makespan problem.Moreover,pruning rules and a new lower bound of the new algorithm are presented.At the end of the section,computational experiments reveal the effectiveness of the new branch and bound algorithm compared with the CPLEX algorithm in small-scale problems.Thirdly,a new branch and bound algorithm is presented for slow shop minimizing makespan problem with learning effects.Moreover,branching strategy,pruning rules and a new lower bound of the new algorithm are presented.At the end of the section,computational experiments reveal the effectiveness of the new branch and bound algorithm compared with the CPLEX algorithm when learning effects are linear function,power function and exponential function,respectively.Finally,the main work of this thesis is summarized and some future research directions are put forward.