一种解决移动瓶颈法不可行解问题的解环方法

摘要

本发明公开了一种解决移动瓶颈法不可行解问题的解环方法，属于调度领域。包括两个步骤，S1判定环，运用工件甘特图排序算法对未调度机器集合中的机器运用Catier算法求解的排序进行间接的无环判定；S2解环，对导致环的机器，运用解环算法进行解环。本发明解决了移动瓶颈法对于部分作业车间调度实例不能求解的不足。本发明提供的工件甘特图排序算法大大降低了算法复杂度。解环算法中结合了回溯策略，所解得的无环机器排序在不降低解的质量的同时，使得当前析取图最大完工时间尽量偏小，求解的质量也并不会差。