用拉氏松弛法解决 FMS 中一类特殊的生产调度问题

Using lagrangian relaxation algorithms to solve a kind of production scheduling problem in FMS

考虑了柔性制造系统（ＦＭＳ）中的一类调度问题，其目标是极小化一个加工作业集的加权平方ｔａｒｄｉｎｅｓ和．由于物料传送系统同时只能最多处理固定数量的加工作业，使得问题变得比一般ｊｏｂｓｈｏｐ问题更为复杂．本文提出了一种基于拉氏松弛的算法，借助该算法不仅能求得满意的次优解，而且能对解的次优性做出定量评估．计算实验验证了这种算法的有效性．

This paper considers a kind of production scheduling problem in Flexible Manufacturing System(FMS),with weighted quadratic tardiness criterion. Because of the total numbers limitation of processing jobs which the transport system can handle simultaneously,the above problem becomes more complex than the normal job shop scheduling problem. this paper does not only proposes a solution to solve this problem,but also evaluates its suboptimality.Finally numerical experiments verify our methods efficiency,which show that it can obtain stable suboptimal schedules with high quality,and can easily answer so called “whatif” problem.