公开(公告)号：CN114638479A

公开(公告)日：2022-06-17

申请号：CN202210167345.0

申请日：2022-02-23

Applicant: 华中科技大学

Inventor： 李新宇 ,  王思涵 ,  高亮 ,  李培根 ,  张春江

IPC: G06Q10/06 ,  G06Q50/04

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

公开(公告)号：CN114638479B

公开(公告)日：2024-09-27

申请号：CN202210167345.0

申请日：2022-02-23

Applicant: 华中科技大学

Inventor： 李新宇 ,  王思涵 ,  高亮 ,  李培根 ,  张春江

IPC: G06Q10/0631 ,  G06Q50/04

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

公开(公告)号：CN115222086A

公开(公告)日：2022-10-21

申请号：CN202210162509.0

申请日：2022-02-22

Applicant: 华中科技大学

Inventor： 高亮 ,  王思涵 ,  李新宇 ,  李培根

IPC: G06Q10/04 ,  G06Q10/06 ,  G06Q50/04

Abstract: 本发明公开邻域解集裁剪方法和作业车间调度问题的局部搜索方法，属于车间调度领域。包括：对当前可行调度解中的关键工序按照邻域结构进行移动，得到一组关键工序的移动组合；采用以下方式对每个关键工序的移动组合进行评估：若移动组合对应的关键工序的移动不能够减小至少一个关键块的开始时间，该移动组合对应的邻域解的制造期将不会减小；将邻域解的制造期增大的移动组合裁剪，剩余移动组合对应的邻域解构成邻域解集。本发明通过关键路径变化特征分析邻域解质量下降原因，剔除无法减小制造期的关键工序的移动组合，细化对邻域解质量的管理；经过裁剪，生成的邻域解数量减少，从而有效提高局部搜索的计算速度和计算效率，更快地得到局部最优解。