带有跨工序约束的柔性job shop调度问题*

飞机制造企业的金属加工车间是一种小批量、多品种生产，其生产指挥是一种带有跨工序约束的柔性job shop调度问题。针对这个NP-hard问题，提出一种三阶段启发式方法，通过依次完成瓶颈工作中心的判定、设备分配和任务排序，使这一问题的复杂度得以逐步降低，从而可以在多项式时间内得到有效的调度方案。实际运行表明，依据该启发式方法产生的调度方案，其关键路径的等待时间占总完工时间的比例不足1.5%，取得了满意的效果。

Scheduling flexible job shop problem with inter-stage constraint

The metal-processing shop of airplane manufacturing is a small-batch and multi-variety production where a job shop scheduling problem with inter-stage constraint needs to be solved.This paper presented a three-phase heuristic approach to deal with this NP-hard problem. During the process of determining the bottleneck work center, arranging the devices, and ordering the jobs,reduced the complexity of the problem gradually. Therefore obtained an effective solution within polynomial time. Application sample shows that the heuristic approach is satisfactory as the idle time of the critical path is less than 1.5% of the completing time.