A New Method for Production Scheduling with Hybrid Dynamic Constraints
具有混合动态约束的生产系统优化调度新算法

A class of scheduling problems with hybrid dynamic constraints is studied. Even under the Lagrangian relaxation framework, solving the subproblems with hybrid dynamic constraints is still difficult and almost all existing methods can only obtain sub-optimal dual solutions. This will reduce the effectiveness of the Lagrangian relaxation approach. This paper presents a new method for defining the discrete and continuous state spaces so that the discrete decision variables and the continuous decision variables can be decoupled. A scheme is presented to solve the subproblems with hybrid dynamic constraints where the discrete optimization and continuous optimization can be conduc-ted separately with overall optimality guaranteed. Complexity analysis and numerical testing for a power generation scheduling problem show the new method is efficient and effective.