Research Of Flow Shop Optimization Algorithm On GPU Scheduling

With development of semiconductor technology,the computing capability of graphics processing unit(i.e.GPU)has been improved a lot.As a result,GPU was applied in many areas to solve complex problems with the advantages of high-speed floating-point performance.A GPU scheduling problem is abstracted into a flow shop problem,which includes data transmission and execution process.Hence,research of flow shop optimization algorithm will promote the development of load scheduling on GPU,and improve the computing performance of GPU.Tree kinds of flow shop problems are considered,and various optimization algorithms are used to solve these problems.First of all,a flow shop problem with total quadratic completion time criterion is considered.A mathematical programming model of the problem is established,and transformed for Lagrangian relaxation algorithm.Relaxing precedence constraints of jobs,capacity constraints and precedence constraints of machines,the problem is decomposed into much easier completion time subproblems and job assignment subproblems.The completion time subproblem is solved by derivation,while the job assignment subproblem is solved by enumeration.Subgradient algorithm is applied to update lagrangian multipliers,and a better solution can be obtained by iteration.A tabu search algorithm is introduced to obtain a better feasible solution,and numerical experiments are executed to verify the effectiveness of Lagrangian relaxation algorithm.Secondly,a minimizing total k-power completion time flow shop problem with release date is considered(k = 2,3).A branch and bound algorithm is introduced for the small-scaled problem,while a discrete differential evolution algorithm is used for the medium-scaled problem.Moreover,pruning rules and a new lower bound of the branch and bound algorithm are presented,and original solutions from branch and bound algorithm are used in discrete differential evolution algorithm.Computational experiments reveal the effectiveness of the branch bound algorithm and discrete differential evolution algorithm.Thirdly,a dynamic minimizing total quadratic completion time flow shop problem with learning effect is studied.Three kinds of learning effect function are considered,including linear function,power function and exponential function.Branch and bound algorithm is introduced to solve small-scaled problem,and discrete differential evolution algorithm is applied to deal with medium-scaled problem.Moreover,pruning rules and a new lower bound of the branch and bound algorithm are presented.SPTA heuristic is used to schedule these nodes that are not pruned by branch and bound algorithm,then feasible solutions are obtained as original solutions for discrete differential evolution algorithm.Computational experiments are executed to verify the effectiveness of the branch bound algorithm and the discrete differential evolution algorithm.