Study On The Single Machine Scheduling Problem With Undirected Cycle Precedence

Scheduling refers to the fixed conditions, through the rational allocation of resources to complete the given job or task, and reach the optimal performance evaluation index of some.Single machine scheduling has been a hot issue in the field of optimization of the portfolio.It is also a very active branch in the field of operations research. Single machine scheduling can be seen as the special form of other scheduling problems,and a subsystem of the complex machine scheduling system. So,researching deeply on the single machine scheduling problem can make us understand better the structure of complex scheduling system.Scientific and rational single scheduling scheme can effectively reduce the vacancy rate of the device, control the WIP inventory level,increase productivity,shorten production cycles and increase customer satisfaction,thereby reducing production costs to improve enterprise efficiency.Therefore,the research and application of single machine scheduling scheme and the optimization technology, is the base and key to improve production efficiency and core competitiveness of enterprises.Based on the single machine scheduling problem as the research object.In designing effective algorithms for solving this kind of problems as the research key.Lagrange relaxation algorithm was proposed to solve the single machine scheduling problem with undirected cycle precedence.First of all,a detailed analysis of two kinds of composed of workpiece precedence graph:A connection precedence graph with an undirected cycle and an undirected precedence graph with an an undirected cycle.Then,based on the above, according to the actual production environment in different production characteristics and optimization,integer programming model was established.By introducing Lagrange multipliers and relaxation machine capacity constraints,the original problem was divided into a plurality of workpiece level problem solving. Hybrid backward and forward dynamic programming was then applied to solve this problem. In order to accelerate the convergence speed and guarantee the quality of the solution.Heuristic algorithm was designed to construct a feasible solution.Subgradient algorithm was used to update Lagrange multipliers.Finally,experiments on a lot of different scale problems.Experimental results show that hybrid backward and forward dynamic programming based Lagrangian relaxation can obtain satisfactory solutions within a shorter running time.