A Dynamic Job Shop Scheduling Method Based on Lagrangian Relaxation

摘要

Due to the complexity of dynamic job shop scheduling in flexible manufacturing s ystem(FMS), many heuristic rules are still used today. A dynamic scheduling appr oach based on Lagrangian relaxation is proposed to improve the quality and guara ntee the real-time capability of dynamic scheduling. The proposed method makes use of the dynamic predictive optimal theory combined with Lagrangian relaxation to obtain a good solution that can be evaluated quantitatively. The Lagrangian multipliers introduced here are capable of describing machine predictive states and system capacity constraints. This approach can evaluate the suboptimality of the scheduling systems. It can also quickly obtain high quality feasible schedu les, thus enabling Lagrangian relaxation to be better used in the dynamic schedu ling of manufacturing system. The efficiency and effectiveness of this method ar e verified by numerical experiments.