On Scheduling Of Satellite In Production Based On Branch And Bound Algorithm

Artificial satellite production can be abstracted as flow shop scheduling mode.And each type of satellite is produced at considerably low volumes(one or two per year for most satellite types).In a flow shop scheduling problem,each job must be processed on different machines in the same order.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.The focus of the scheduling algorithm is to determine the sequence of job scheduling and optimize the objective function.Flow shop scheduling problem play an important role in various fields of engineering technology and economic management.This mode in the modern industrial enterprise play an important role,and for this mode,the branch and bound algorithm has a good application prospect.In this thesis,three problems of the flow shop scheduling model are investigated.The branch and bound algorithm is designed,to optimize the predetermined objective function.Finally,computational experiments are conducted to reveal the performances of the proposed algorithms.The contents are summarized as follows:Firstly,for the flow shop scheduling problem with release time of minimizing the maximum delivery time,the branching rule is presented with release time to reduce the amount of calculation and speed up the optimization.A new low bound is presented for the flow shop minimizing maximum delivery time problem.The computational experiments reveal the performances of the branch and bound algorithm in different size problems.And the performance of the algorithm is evaluated by the test of real production data.Secondly,for the blocking flow shop scheduling problem of minimizing the maximum delivery time,a branch and bound algorithm is presented.A new low bound is presented with the limited of the buffer between the machines.And the computational experiments reveal the performances of the branch and bound algorithm in different size problems.Thirdly,for the flow shop scheduling problem effect of minimizing the total completion time with learning effect,a branch and bound algorithm is presented.For this problem,a branching rule is designed,and a new lower bound is presented.In order to improve the computation efficiency,the upper bound for the problem is designed.Finally,the effectiveness of the branch and bound algorithm for the cases of linear function,power function and exponential function is verified by numerical simulation experiments.Finally,the main work of this thesis is summarized and some future research directions are put forward.