【摘要】 一种基于加工能力特征模型的机器组调度方法，属于自动控制、信息技术和先进制造领 域，其特征在于基于通过调度信息硬件采集系统所获得的调度时刻机器组信息和被调度工件 信息，由基于加工能力特征模型的机器组调度软件以最小化工件总拖期时间为调度目标建立 基于加工能力特征模型的机器组调度模型，进而采用基于工件特征的遗传算法进行机器组优 化调度，得到基于工件组排序的机器组优化调度方案，并基于工件释放时刻扰动信息对原机 器组优化调度方案进行动态修正以应对由于工件释放时刻扰动导致原机器组优化调度方案性 能下降乃至不可行的问题。该调度方法可对难以直接采用将工件分派到具体机器的传统调度 模式的机器组进行有效的整体优化调度。 【专利类型】发明授权 【申请人】清华大学 【申请人类型】学校 【申请人地址】100084北京市100084-82信箱 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810114732.8 【申请日】2008-06-11 【申请年份】2008 【公开公告号】CN100580594C 【公开公告日】2010-01-13 【公开公告年份】2010 【授权公告号】CN100580594C 【授权公告日】2010-01-13 【授权公告年份】2010.0 【IPC分类号】G05B19/418; G06N3/12 【发明人】刘民; 李鹏; 吴澄 【主权项内容】1.基于加工能力特征模型的机器组调度方法，其特征在于，所述方法是在计算机中依次按以下步骤实现的： 步骤(1)，通过调度信息采集硬件系统采集得到调度相关信息，所述的调度相关信息包括在调度开始时刻的机器组和工件如下相关信息： 机器组中既未发生故障也未被占用的机器数量，机器组中的故障机器编号，所述故障机器的预期修复时刻，机器组中已被占用的机器编号，所述被占用机器的预期释放时刻，机器组中按维修计划和保养计划将进行维修与保养的机器编号，所述被维修或保养机器的维修与保养计划开始时刻和计划结束时刻，被调度工件总数，所述被调度各工件的释放时刻或预期释放时刻、加工时间和交货期、释放时刻扰动量， 步骤(2)，通过运行在调度服务器上的基于加工能力特征模型的机器组调度软件，以下简称调度软件，从所述采集系统中读取所述调度相关信息，并在所述调度相关信息的基础上，依次按如下步骤建立加工能力特征模型： 步骤(2.1)，定义如下加工能力特征模型参数： 调度开始时刻为0， 调度开始时刻后的任一可变时刻t机器组中允许被使用的机器总数记为C(t)，在调度开始时刻其值等于该时刻机器组中既未发生故障也未被占用的机器数量m0，而在调度开始时刻后的时间中，当调度开始时刻正处于故障中的每台机器在其维修完成后C(t)的数值会相应增加1台，当调度开始时刻正在加工工件的每台机器在被释放后C(t)的数值会相应增加1台，当按照维修计划或保养计划某机器需要被维修或保养时C(t)的数值会相应减少1台，当某机器结束其维修或保养时C(t)的数值会相应增加1台，由此计算出调度开始时刻后的任意时刻t机器组中允许被使用的机器总数C(t)的数值， 调度开始时刻后的任一可变时刻t机器组中被调度工件的集合{Ji，1≤i≤N}，其中N为所述调度相关信息中的被调度工件总数， pi、 分别为所述被调度工件Ji的释放时刻或预期释放时刻、加工时间和交货期， 为被调度工件Ji的释放时刻扰动量，其为被调度工件Ji的实际释放时刻与预期释放时刻之差，当工件提前到达时该值小于零，当工件延后 到达时该值大于零， 被调度时间范围[0，T)，其中T按下式计算： 其中η为设定的系数，满足0＜η＜∞，m为设定的机器组中的能用机器数估计值，满足m＞0，L为设定的时间区间长度，满足L＞0， 被调度时间范围[0，T)内机器组的整体加工能力U1，其按下式计算： 时间区间集合 其中时间区间 q为时间区间的序号，取正整数，时间区间的总数由设定的L值和T值确定， 和 分别为所述时间区间Zq的开始时刻和结束时刻， 和 按下式计算： 其中 步骤(2.2)，定义如下的加工能力特征模型决策变量及相关变量， 所述被调度工件Ji的计划加工开始时间 其满足 即所述被调度工件Ji必须在其释放时刻或预期释放时刻 之后开始加工， 所述被调度工件Ji在时刻t所占用的机器组中的机器数oi(t)，单位为台，按下式计算： 其中1≤i≤N， 被调度时间范围[0，T)内所有被调度工件{Ji，1≤i≤N}所占用的机器组总加工能力CT，按下式计算： 其中O(t)为时刻t所有被调度工件所占用的机器总数，按下式计算： 所述被调度工件Ji所在的时间区间 其由计划加工开始时间 确定： 其中1≤i≤N， 其中qi为工件Ji所在时间区间 的序号， 加工能力特征模型决策变量为所述被调度工件的工件组排序，即：根据每个工件Ji所在的时间区间 将所有被调度工件分为若干工件组，每个时间区间 对应一个工件组，工件组的总数等于时间区间的总数，每个工件Ji属于某个工件组，所有工件组内的工件构成了全部被调度工件的集合，将工件组按时间区间 先后进行排序，加工能力特征模型决策变量具体包括每个工件组内包含的工件号以及工件组的加工顺序， 由所述加工能力特征模型决策变量构成机器组调度方案sp， 步骤(2.3)，定义如下的加工能力特征模型约束条件及相关特征量： 所述加工能力特征模型约束条件：在所述被调度时间范围[0，T)内由所述被调度工件所占用的机器组总加工能力CT小于或等于该机器组的整体加工能力U1，即： CT≤U1， 加工能力超限量相对值α是加工能力特征模型的特征量，其按下式计算： 其中U2为加工能力超限量，其按下式计算： 所述被调度工件Ji的工件加工能力超限量相对值βi，其按如下方法计算： 步骤(3)，所述调度软件依次按如下步骤实现所述基于加工能力特征模型的机器组调度方法： 步骤(3.1)，用基于工件特征的遗传算法优化求解步骤(2.2)中的机器组调度方案sp，其步骤如下： 步骤(3.1.1)，按如下方法生成规模为M的初始种群，其中M为偶数，个体Vm的基因串定义为Vm＝{rs1，rs2，…，rsi，…，rsN}，1≤m≤M，每一个个体Vm对应一个机器组调度方案spm，基因rsi为spm中工件Ji的加工开始时间相对值，按如下公式取值： 其中1≤i≤N， 步骤(3.1.2)，首先对个体Vm中的加工开始时间相对值rsi按下式解码以得到工件Ji的计划加工开始时刻 随后按下式评价个体Vm的性能指标： 其中qi为按步骤(2.2)所述方法所确定的工件Ji所在时间区间 的序号， 为工件Ji所在的时间区间 的中点时间，K1和K2为设定的加权系数，其满足K1+K2＝1，0＜K1＜1，0＜K2＜1， 为机器组调度方案spm所对应的工件总拖期时间估计值，αm′为机器组调度方案spm所对应的加工能力超限量相对值αm的估计值，其用如下方法计算： 其中1≤i≤N 步骤(3.1.3)，若当前种群已经满足停止条件，则转步骤(3.1.8)，否则转步骤(3.1.4)，所述停止条件为： nitr＞Kitr， 其中nitr为当前的种群代数，Kitr为设定的最大代数，满足Kitr＞0， 步骤(3.1.4)，对当前种群进行适应度变换，按下式计算各个体Vm的适应度函数fm： 1≤m≤M， 其中K3为设定的幂指数，其为正实数， 步骤(3.1.5)，采用经典的基于轮盘赌方法的比例选择法生成下一代种群，具体方法如下： 若xm为1，则其对应的个体Vm即被选中作为下一代种群成员，若xm为0，则其对应的个体未被选中，其中r1是在[0，1)区间内随机生成的实数， 重复进行所述选择操作直到选出M个个体为止， 步骤(3.1.6)，对由步骤(3.1.5)得到的父代个体采用多点交叉方法进行交叉操作， 实现方法如下： 首先将所有父代个体随机配成M/2对，然后按下述步骤以交叉概率K4进行多点交叉，对每对参与交叉的父代个体随机选择K5个相同的交叉位，将两个父代个体分解为K5+1个基因串，交叉后的子代个体1的第一段基因串选择父代个体1的第一段基因串，子代个体2的第一段基因串选择父代个体2对应的基因串，子代个体1的第二段基因串选择父代个体2的第二段基因串，子代个体2的第二段基因串选择父代个体1对应的基因串，依次类推，其中K4满足0＜K4＜1，K5为交叉位个数，其满足1≤K5＜N， 步骤(3.1.7)，对由步骤(3.1.6)得到的所有父代个体以变异概率K6按以下步骤进行变异，其中K6满足0＜K6＜1，对参与变异个体中的加工开始时间相对值rsi按如下方法进行变异，随后转回步骤(3.1.2)： 其中1≤i≤N， 其中r2和r3皆为在[0，1)区间内随机生成的实数，K7为设定的系数，其满足0＜K7＜1，βi为工件Ji的工件加工能力超限量相对值，其按如下方法计算： 步骤(3.1.8)，把当前种群中的最优个体对应的机器组调度方案作为优化结果输出，在该机器组调度方案中 为被调度工件Ji所在的时间区间，则工件Ji的加工优先级按下式计算： 其中 为区间 的序号。 【当前权利人】清华大学 【当前专利权人地址】北京市100084-82信箱 【专利权人类型】公立 【统一社会信用代码】12100000400000624D 【引证次数】6.0 【他引次数】6.0 【家族引证次数】6.0 【家族被引证次数】17
