Heuristic Algorithm For Solving Workshop Production Resource Scheduling And Allocation

The scheduling and allocation of workshop production resources is a variant of the resource constrained project scheduling problem(RCPSP).Under the premise of the shortage of production resources and human resources,how to optimize the allocation of production resources,human resources and the scheduling scheme under various production tasks to ensure the full ability to complete various production tasks,This is the main content of the optimization problem.To solve this problem,we can save time,space,software,hardware and labor costs,which has a certain theoretical significance and practical value.In this thesis,two heuristic algorithms are proposed to solve the scheduling and allocation problem of workshop production resources.Firstly,the demand analysis of the production resource scheduling and allocation problem is carried out,the mixed integer programming model is established,and the exact solution is obtained by using the mathematical programming solver(Gurobi)as the evaluation index.In addition,two efficient heuristic algorithms are proposed in this thesis.The first algorithm is genetic algorithm,which selects parents through roulette algorithm,generates new individuals through single point crossover operator and mutation operator,and finally obtains legitimate offspring through repair operator.The second algorithm is a tabu search algorithm based on decision,which includes two kinds of neighborhood actions.The first one considers deleting one of the production machines,and then scheduling the tasks on the set of machines to generate a neighborhood solution;In the second neighborhood action,a production machine is selected from the idle production machine set to replace a currently used production machine,and then the task is scheduled on the new production machine set to generate a legal neighborhood solution.In this thesis,according to the pre constraints between processes and the process execution sequence and typical execution time in the production process,a test set is generated,and the heuristic algorithm and the mixed integer programming model are compared.The experimental results show that the genetic algorithm proposed in this thesis can get the optimal solution of the problem in the vast majority of cases,and its solving speed is significantly improved compared with the mixed integer programming model;In addition,the proposed tabu search algorithm based on decision can get the optimal solution of the problem on all cases,and the solution speed is the fastest compared with the comparison algorithm.