Sequency 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 present invention belongs to the field of system engineering and can handle complex production system optimization scheduling process method including equipment or resources of the same type, and further relates to the optimal scheduling method based on Laplace relaxation that can handle the same type of tasks, equipment of the same type, and resources of the same type. The production system sequentially adjusts the process method. 2. Background technology [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 algorith...

AI Technical Summary

Problems solved by technology

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