带有批处理机的多阶段变异混合流水车间调度方法

摘要

本发明涉及一种带有批处理机的多阶段变异混合流水车间调度方法，属于先进制造控制与调度技术领域。通过基于分派规则编码的遗传算法解决组合分派规则的决策问题，首先根据不同的调度目标建立采用三段编码描述的问题模型，再根据本发明提出的策略搜索遗传算法，分别以最小化最大完工时间和最小化加权延迟时间总和为目标，为每台机器搜索适用的分派规则，最后应用得到的组合分派规则求得调度解。本方法能够解决同时含有批处理机和单处理机两种不同设备类型的多阶段HFS调度问题；采用面向机器的编码方案，更能反映出实际的环境信息，在一定程度上避免了按阶段编码的局限性；编码无需采用修复机制；保证了调度效率。

主权项

1.带有批处理机的多阶段变异混合流水车间调度方法，其特征在于：具体包括如下步骤：第1步：定义符号变量：所述实体表示离散机和批处理机上加工的工件或工件集合；对于离散机，一个实体表示一个工件；对于批处理机，一个实体表示一个批次；第2步：根据不同的调度目标，采用三段编码描述模型α|β|γ，其中α表示机器环境，β描述工件的详细特点和约束，γ为调度目标；将带有批处理机的多阶段变异混合流水车间调度问题模型归纳为：${\mathrm{HF}}_K,{\left({\mathrm{PM}}^{\left(k\right)}\right)}_{k=1}^K|r_{j,}{S}_{\mathrm{snd}},{\mathrm{batch}}^{\left(k^{\prime }\right)}|C_{\max }---\left(1\right)$${\mathrm{HF}}_K,{\left({\mathrm{PM}}^{\left(k\right)}\right)}_{k=1}^K|r_{j,}{S}_{\mathrm{snd}},{\mathrm{batch}}^{\left(k^{\prime }\right)}|\mathrm{TWT}---\left(2\right)$式（1）和式（2）中的α部分和β部分相同，其中HF_K表示含有K个阶段的混合流水车间；表示第1阶段到第K阶段的并行机；r_j表示工件j的到达时间；S_snd表示与次序无关的准备时间；batch^(k′)表示1到K中的某一阶段k′为批处理机；式（1）和式（2）中的γ部分不相同，其中式（1）中的C_max表示以最小化最大完工时间为目标，式（2）中的TWT表示以最小化加权延迟总和为目标；第3步：确定第2步建立的调度问题模型的问题约束及优化目标；问题约束约束(3)表示工件j在阶段k只能被安排在一台机器M上；约束(4)表示工件j在阶段k只能属于一个实体b；约束(5)表示工件j在阶段k必须被调度，且只能调度一次；约束(6)表示工件j到达系统后才能开工,即到达时间r_j小于等于当前时间约束(7)表示工件j在阶段k的机器m上的实际处理总时间不早于其所属实体b中任意一个工件j在阶段k的处理总时间tt_jk；约束(8)表示除第一阶段外，工件j完成前一阶段k的加工完后后一阶段k+1才能开工约束(9)表示同一实体b的不同工件j和j’在阶段k的开始时间相同；约束(10)表示工件j在阶段k的完工时间C_jk大于等于到达时间加总处理时间tt_jk；约束(11)表示机器同一时间t不能同时加工两个不同工件j和j’；约束(12)表示每个批次的实体个数不能超过机器m的容量CM_m；确定本发明的目标为最小化最大完工时间C_max或最小化加权延迟总和TWT：优化目标第4步：基于第2步的问题模型，在第3步的约束下，采用遗传算法达到优化目标；首先，设计染色体的形式：将遗传算法中的染色体设计成工件段、机器段和组批段，分别对应加工过程中的指派方法、排序方法和组批方法，并分别设置三种编码规则，各段染色体的基因位表示其所对应编码规则的索引号；工件段染色体对应各个工件被指派到相应机器上所遵循的规则，机器段染色体对应各台机器选择缓冲区工件所遵循的规则，组批段对应批处理机对位于该批处理机缓冲区的工件进行组批所遵循的规则；在排序、指派和组批方法中采用一致的编码方案；将工件段、机器段和组批段所对应的编码索引号顺序组合在一起，构成问题模型的一个染色体；编码规则第5步：用户设置种群数量，按照第4步的染色体形式随机生成染色体；生成的染色体数量与种群数量相同；第6步：还原调度解，由于通过染色体不能直接得到调度解，所以需要解码方案来把生成的染色体还原成调度解，本发明的SSGA方法采用离散事件仿真方法，对第5步生成的每一条染色体分别进行解码，还原成实际的调度解以获取目标函数值；采用离散事件仿真方法对其中一条染色体解码的具体过程为：6.1初始时间t=0；6.2检查是否所有的工件都被调度完并且所有机器都空闲，如果是则转6.15，否则执行6.3；6.3检查是否有未被调度工件到达含有K个阶段的混合流水车间的第一个阶段，如果是则转6.4，否则转6.6；6.4将到达的工件按照该工件染色体所含的指派规则加入到指派机器的缓冲区，转6.5；6.5从未被调度的工件列表中删除已到达工件，转6.6；6.6逐台扫描所有加工机器，检查是否为空闲状态，一旦扫描到空闲机器则转6.7，否则转6.13；6.7检查6.4所述指派机器的当前是否有加工完成的工件，若有，将工件从该指派机器卸载，加入至按该工件染色体的指派规则所确定的下一台调度机器的缓冲区，同时得到该工件在该指派机器上的完工时间，转6.8；6.8检查所有机器的缓冲区，若全部为空，转6.13，否则转6.9；6.9检查所有缓冲区不为空的机器是否为批处理机，如果是则转6.10，否则转6.11；6.10按照机器的组批染色体所含的组批规则将缓冲区的工件组批为实体，转6.12；6.11将缓冲区的每一个工件组成一个实体，转6.12；6.12按照机器染色体所含的排序规则调度该机器缓冲区内的所有实体，得到每个实体在这台机器上的开始加工时刻，转6.13；6.13检查是否对所有机器完成一遍扫描，如果是则转6.14，否则转6.6继续扫描；6.14时间步进：当前总调度时间t=t+1，转6.2；6.15调度结束；采用步骤6.1-6.15的方法还原每一条染色体，得到该代染色体中每个染色体实际的调度解；第7步：对第6步还原后的染色体进行选择操作：遍历种群中的每一个染色体，对于染色体i，i=1,2,…,size，当目标函数obj(i)是C_max时，获取相应的完工时间，当目标函数obj(i)是TWT时，获取加权延迟总和；根据适应度函数计算染色体的适值：$\mathrm{fit}\left(i\right)=\frac{1}{(\mathrm{obj}\left(i\right)+1)}---\left(15\right)$输出适值最高的染色体作为该代染色体中的最优解；染色体的选择采用轮盘赌法，每代选择X个染色体，X为偶数，染色体被选择的概率为：$\mathrm{prob}\left(i\right)=\frac{\mathrm{fit}\left(i\right)}{\underset{i=1}{\overset{\mathrm{size}}{\Sigma }}\mathrm{fit}\left(i\right)}---\left(16\right)$第8步：对选出的X个染色体进行两两交叉操作，每一条染色体仅参与一次交叉操作，得到X/2对交叉后的子代；在两个染色体交叉时，需要对每个段的染色体分别进行交叉；对于每条染色体，一次交叉操作的步骤如下：8.1：在满足一定交叉概率的情况下进行交叉操作：用户设置交叉概率，交叉概率在0.05-0.9之间；在0-1间产生一个随机数，若随机数小于交叉概率则转8.2，否则不进行交叉操作；8.2：在一个染色体中的工件、机器、组批段分别随机选择两个不同的位置，得到三个基因块；8.3：在工件、机器、组批段，分别对应交换两个父代染色体中选中的基因块，产生两个交叉后的子代；第9步：用户设置变异概率，变异概率在0.01-0.18之间，对第7步选择的每个染色体执行变异操作，具体方法为：产生一个随机数，当产生的随机数小于变异概率时对一个父代染色体的每段染色体进行单点变异，指定一个位置并随机替换该位置上的基因，使得新染色体符合表4的编码规则；第10步：判断是否超过最大迭代次数，若没有超过，重复第5步到第9步，每重复一次迭代数加1；若超过最大迭代次数，则结束迭代，得到每一代的最优解，根据每一代最优解对应的调度时间或加权延迟总和，以及编码规则，确定相应的调度策略，实现带有批处理机的多阶段变异混合流水车间调度。