Sequence updating method for supbroblem of production system management based on L'S relaxation

Abstract

The present invention discloses a subproblem sequential renwal method based on L's relaxation for optimizing production management in production system for treating same kind of tasks, same type of equiopment and same class of resource, and is characterized by that under the frame of La's relaxation every subproblem correspondent to every equipment or every task possesses penalty item related to other equipment or task, only one subproblem is undergont eh process of sequential solution of renewal treatment, the La's multiplier (system price) also is renewed, so that it basically solves the isomorphism difficult problem of optimizing sceduling algorithm under the frame of La's relaxation, at the same time remains the advantages of frame of La's relaxation, progressive gradient method and augemented La's relaxation method.

Description

[0001] 1. Field [0002] The invention belongs to the field of system engineering and can handle complex production system optimization scheduling methods including equipment or resources of the same type, and further relates to a Laplace relaxation-based sub Question Sequential Update Method. [0003] The optimal scheduling of production systems is an important problem faced by many companies on a daily basis. Its purpose is to rationally arrange limited production resources to optimize one or some indicators, such as the shortest time, the lowest cost, the lowest risk, and the largest profit. Wait. So far, a wide variety of methods such as heuristic method, dynamic programming method, hybrid programming method, Lagrangian relaxation method, genetic algorithm, neural network algorithm, etc. have been used to solve various production scheduling problems. With the increasing requirements for economic and social benefits and the increasingly fierce market competition, the import...

AI Technical Summary

Problems solved by technology

[0022] A pseudo-subgradient method (X.Zhao, P.B.Luh, and J.Wang, Surrogate Subgradient Algorithm for Lagrangian Relaxation, Journal of Optimization Theory and Applications, Vol.100, No.3, 1999, pp.609-712) uses pseudo-subgradient The gradient is used as the direction to correct the Lagrangian multiplier. It only needs to solve one or several sub-problems to obtain the pseudo-subgradient, which reduces the amount of calculation, but it cannot guarantee that the dual solution is close enough to the optimal solution of the original problem.

Images