作业车间调度问题工序交换可行性判定和局部搜索方法

摘要

本发明公开了作业车间调度问题工序交换可行性判定和局部搜索方法，属于车间调度领域。包括：对于一个可行调度解，当满足时，将工序u移动至工序v后将不会产生不可行邻域解；当满足时，将工序v移动至工序u前将不会产生不可行邻域解；u和v在同一台机器上进行加工；BSγ(u)为工件紧后工序的后序工序集合，FSα(v)为工件紧前工序的前序工序集合。本发明构建了工序集合BSγ(u)和FSα(v)，在判定过程中充分考虑工件不同工序之间的加工顺序约束和同一机器上的加工顺序约束，排除违反工序顺序约束的不可行情况，属于对问题的完全映射，几乎不会出现将可行解判定为不可行的误判情形。因此，这种判定方法适于用来辅助局部搜索算法对作业车间调度问题进行高效求解。