基于不等量二分法的开放车间调度问题关键操作识别方法

摘要

本发明提出了一种基于不等量二分法的开放车间调度问题关键操作识别方法，首先根据不等量分配原则，将编码序列分为长度不等的左右两部分，然后根据洗牌算法分别调整左右两部分编码顺序，对调整后的编码序列重新计算评价指标，根据评价指标更新位置参数，不断缩小搜索范围，直到满足终止条件。本发明所提供的快速识别OSP中关键操作的方法，利用了二分法可以快速缩小范围、操作简单、方向明确的特点，变优化方案的“被动寻找”为“主动利用”，快速高效地找到制约整个方案的关键操作（包含关键机器、关键工件和关键工序），能够快速找到较优的生产方案，提高企业效益。

主权项

1.一种基于不等量二分法的开放车间调度问题关键操作识别方法，其特征在于：采用以下步骤：步骤1：问题编码：对开放车间调度问题采用基于操作的整数编码，得到编码序列I₀＝{g₁,g₂,...,g_N}，其中N是I₀中包含的基因个数，g_j是I₀的第j个基因，j为基因在编码序列I₀中的位置编号，基因所表示的整数值对应实际调度问题中的一个工件编号，某个整数值在I₀中按从左向右顺序出现的次数表示该整数值对应工件的工序数；步骤2：对编码序列I₀进行活动解码运算，得到编码序列I₀对应的总的完工时间V₀和编码序列I₀对应的生产方案S₀；步骤3：参数初始化：迭代次数sd初始值为1，邻域搜索左边界pos_L初始值为1，邻域搜索右边界pos_R初始值为N；步骤4：采用以下步骤产生区间[pos_L+1,pos_R-1]内的随机整数mid：步骤4.1：产生区间[0,1]内的随机实数r；步骤4.2：产生区间[pos_L+1,pos_R-1]内的随机实数tmid：tmid＝r×[(pos_R-1)-(pos_L+1)]+(pos_L+1)；步骤4.3：对步骤4.2得到的随机实数tmid进行取整运算，得到区间[pos_L+1,pos_R-1]内的随机整数mid；步骤5：对编码序列I₀中位置编号对应区间[pos_L，mid]的所有基因利用洗牌算法随机重排，得到重排后的编码序列I_L；对编码序列I₀中位置编号对应区间[mid，pos_R]的所有基因利用洗牌算法随机重排，得到重排后的编码序列I_R；步骤6：对编码序列I_L,I_R进行活动解码运算，得到编码序列I_L,I_R对应的总的完工时间V_L,V_R；步骤7：根据步骤6得到的编码序列I_L,I_R对应的总的完工时间V_L,V_R，对比编码序列I₀对应的总的完工时间V₀，更新邻域搜索左边界_pos_L和邻域搜索右边界_pos_R，更新规则为：步骤8：若|pos_R-pos_L≥2，则进行步骤9，否则进行步骤10；步骤9：若迭代次数sd小于最大迭代次数SD，则迭代次数加1，并返回步骤4，否则进行步骤10；步骤10：根据得到的基因位置编号区间[pos_L,pos_R]，该基因位置编号区间内对应的所有工件组成关键工件集合J^*，关键工件在该基因位置编号区间内对应的工序组成关键工序集合P^*，关键工件以及关键工序根据生产方案S₀得到关键机器集合M^*，J^*、P^*和M^*组成关键操作集合O^*。