1、第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：国家重点研发计划资助项目（）；浙江省自然科学基金资助项目（）。：，（），（）采用 分拣的型材下料车间成组调度问题研究汤洪涛，郑之恒，李英德，陈青丰，江伟光（浙江工业大学 机械工程学院，浙江杭州 ）摘要：针对一种基于自动导引小车（）分拣的型材下料车间分拣新方法，以最小化损耗费用和运行费用为目标，建立了混合整数线性规划模型，设计了一种改进遗传算法对模型进行求解。该算法使用带加工属性的多层编码方式，针对多层编码设计了分层式交叉变异的方式，在邻域搜索阶段采用基于禁忌表的双层协同优化策略。算例对比实验表明，所设计的改进遗传算法与基
2、础遗传算法、基础蚁群算法、变邻域改进遗传算法，以及改进蜂群算法相比，在求解该问题上有显著优势和有良好的鲁棒性。关键词：自动导引小车分拣；型材下料车间；成组调度；遗传算法；大规模实例生产应用；禁忌表中图分类号：文献标识码：，（，）：（），：；引言型 材 下 料 车 间（，）是指对钢制原材料进行切、冲、钻等基础加工处理的车间，通常由多条辊道流水线组成。一台套整机产品所需的不同型号的型材通常需要在多条线分头下料，一根型材在产线上通常切割成不同规格的零件以供不同台套整机产品使用。型材经切割后通常需根据后道工序生产要求按整机产品成套分拣，并送往后续车间生产。为了提高分拣效率和智能化水平，一种新的使用自动
3、导引小车（，）进行成套分拣的新模式在下料车间出现。车间由数条切割下料生产线组成，需切割的型材通过辊道上料，经过切割加工后，从辊道下线至特定的料第期汤洪涛 等：采用 分拣的型材下料车间成组调度问题研究框中。搬运各个料框分别在各条下料线的下线点之间移动，确保同一台套物料放入同一个料框，并最终将完成分拣的料框搬运至成品库。考虑到型材重量和尺寸导致的搬运不便，下料时通常需要将一根型材全部切割完毕，不留余料，在生产排程时需以一根原材料为一组进行调度，因此可以归为成组调度（，）。在传统 研究方面，等首次对具有序列不相关准备时间和一致并行机类型的混合流水车间成组调度问题进行了研究，分析了在单准备时间和多准备
4、时间两种情况下 问题的性质特征，并基于此对种不同的组合启发式算法的性能进行了对比分析；随后，等对无关并行机、序列相关等各种情况下的组调度都进行了研究；袁帅鹏等对两阶段流水车间成组调度问题进行了研究；随后又针对无关并行机类型的混合流水车间成组调度问题，在考虑序列相关准备时间的情况下，以最小化最大完工时间为目标设计了一种改进的候鸟优化算法。传统成组调度的研究针对各种不同加工环境下的流水车间，而型材下料车间成组调度（，）与一般采用成组调度的作业车间相比，其工序相对较少，加工工艺简洁，无需考虑工艺间的调度，且节拍相对稳定，完工时间趋向于固定，若使用进行成套分拣则需要型材生产排程与调度密切配合，且成套分
5、拣的需求将导致更复杂的路线、更灵活的调度方案、以及更高的使用成本。在 调度研究方面，研究仓库环境中的路径以及搬运时间优化的多 调度问题较多；等 研究了矩阵式制造车间多台 的调度问题，设计了改进的迭代贪婪算法以优化运输成本；为了解决考虑运输时间和多机器人的作业车间调度问题（，），等 开发了两种新的元启发式杂交算法；等提出一种主 从方法来解决具有运输限制的 ；的应用及其成本的控制已经进入了研究的视野，但成组调度与 分拣的结合还仍有必要进行深入研究，面向 综合考虑生产排程与 调度，研究其调度方法有重要的理论意义和实用价值。针对该问题，本文以最小化 使用成本为目标建立数学模型，在考虑型材下料车间实际加
6、工生产特点的情况下提出一种采用多层编码方式的改进遗传算法，该算法采用带加工属性的多层编码方式区分加工要求，用不同层的属性来区分原料、台套和零件并分层交叉变异，设计了不同的邻域搜索机制来构造不同层的邻域结构，并提出了基于禁忌表的双层协同优化策略。最后分别与基础遗传算法、基础蚁群算法、变邻域改进遗传算法和改进蜂群算法进行综合对比，验证了本文算法的有效性与鲁棒性。问题描述和数学模型 问题描述型材下料车间加工工艺如图所示，型材从原材料库到达各条平行的下料流水生产线，经过切割下料后，由机械手抓取切割后的零件放入 搬运的料框，将车间不同产线切割的属于同一台套的零件放入同一个料框中，最后以框为单位齐套入库。
7、假设一个由条产线构成的下料车间同时生产多个台套产品，如图所示为一台 依次经过号产线的个下线点装载号台套零件的过程，其中：连续的方框表示同一根型材，数字表示零件所属的台套编号，虚线框表示下线缓存区位置，带箭头连线表示 依次在各个产线的下线点装载下线的零件。成材率是型材下料最重要的考虑因素，车间企业资源计划（，）系统安排每日加工任务时，首先根据最省型材原材料的原则进行初步排样。型材的生产排样涉及到每一根型材的先后切割顺序和每一根型材内部各段零计算机集成制造系统第 卷件的先后切割顺序。本文研究 分拣的 问题是在车间 系统经过初步排样后对型材切割顺序及一根型材内部各段的切割顺序的二次调度，可描述如下：
8、（）下料车间抽象为多台并行排列的性能不同的切割机；（）订单在上级 系统按最省原材料原则初步排样；（）同一根型材的各段零件只能在同一台机器上切割；（）零件切割完成后在缓存区等待机械手抓取下线进入料框；（）同台套的零件放入同一料框，料框由背负在产线间移动，接收下线的零件；（）同一台套的料框的每次移动可以由任意一台完成。本文优化的目标是最小化 的使用成本。的使用成本可以简化为由电池折旧成本和用电成本两部分组成。电池折旧成本可以视作与充放电 次数正相关，充放电次数与的有效工作时间正相关；用电成本也与 的有效工作时间正相 关。因此，最 终 将 使 用 成 本 转 换 为的有效工作时间（即搬运行走时间和举
9、升放下料框时间）。针对该问题，建立数学模型并设计合适的求解算法。数学模型根据以上对下料车间的描述，建立以下假设和约束：（）任一时刻一台机器只能切割一段零件，且每段零件只能被约定的机器所切割；（）切割过程不可中断，不考虑设备故障；（）零时刻，所有型材均可切割；（）假设所有设备切割一段零件用时相同；（）料框中的零件需齐套存储；（）一个料框可以容纳一台套零件，并且可以由一台 移动；（）忽略 行走过程中的拥堵等待；（）假设各条产线平行布置，依次顺序编号。为描述该车间作业问题，对数学模型中的主要参数作如下定义：表参数定义汇总表变量符号意义加工任务台套数车间产线数量第台套产品中需切割的零件数量车间产线间距
10、自然数集合极大数，台套编号，产线编号，台套中零件数量，第台套中第件完成切割的零件使用的产线编号 第根型材中第段零件完工时间 第条产线上加工的第根型材中第段零件加工时间第根型材的完工时间，即该根型材的最后一段零件的完工时间，第台套中第件完成切割的零件的完工时间。一根型材中各段零件的先后顺序指示变量。第根型材的零件在零件后，否则为。不同根型材的先后加工顺序指示变量。第根型材在第根后切割，否则为。第根型材是否在第条产线上加工指示变量，是则，否则为。同一台套中加工顺序相邻的零件是否在同一产线加工的指示变量，当，时，否则为。产线上加工的第根型材中的第段零件是否属于台套的指示变量，是则 ；否则为。第期汤洪
11、涛 等：采用 分拣的型材下料车间成组调度问题研究优化的目标函数为：（，）；（），。（）（）（），；（）（）（），；（）（）（）（），；（）（）（）（），；（），；（），；（），。（）其中：式（）表示优化目标为 所有转运任务完成所经过的路程之和最短。其中，加工完成顺序相邻的两段零件所处的加工产线间的距离为需要接运的距离。式（）表示优化目标为加工完成时间顺序相邻的同台套的两个零件所属的加工产线不同，这种情况出现的次数最少，即物料下线时需要搬运料框前往另一条产线承接物料的次数最少。式（）和式（）表示同一根型材的两段零件切割完工时间之差大于等于后一段的切割加工时间。式（）和式（）共同确定了同一根型材的
12、各段零件切割的先后顺序。式（）和式（）表示同一条产线上后一根型材的任意一段的切割完工时间大于等于前一根型材的完工时间与该段型材的加工时间之和。式（）和式（）共同确定同一条产线各根型材之间的加工顺序。式（）表示一根型材只能由一条产线加工；式（）将属于同台套的零件按加工完成的先后顺序排序，完工时间相同 的按所 在 产 线 编 号 从 小 到 大 排 序。式（）确定了同台套的零件的加工产线。改进遗传算法的设计由于采用 分拣的 问题具有强 难 的 特 点，常 采 用 遗 传 算 法 求 解 该 类 问题 ，但也存在过早收敛和后期搜索效率低的问题，因此，结合研究问题的特点，本文提出了改进的遗传算法，采用
13、三层编码，第一层表示型材型号，第二层表示零件所属的台套，第三层表示加工属性，同时在交叉变异时，将第一层与第二层分开处理，防止两者的同时变化丢失部分优秀基因，以增强全局搜索能力，并提出了不同的邻域搜索方式以构造两层不同的邻域，最后以双层禁忌表的方式将两层邻域协同优化，提高算法的效率和适用性。算法流程图如图所示。染色体的编码与解码本文采用如图所示的带加工属性的多层矩阵式编码，厂区有条生产线，各自的任务互不相同。每层产线编码有三层，从上至下，第一层为原材料型号层，表示先下料的是外径，壁厚的圆钢，后续为外径，壁厚 的圆钢；第二层为台套属性层，表示第一根圆钢被切为段，分别用于台套编号为第、的整机；第三层
14、为加工属性层，表示切割的段零件长度分别是 ，。适应度计算如前文所述，本文优化的目标是最小化 的使用成本，最终可以转换为 的有效工作时间。相邻产线间转运一次需要完成两次转弯进接运计算机集成制造系统第 卷区举升料框的动作，完成一次动作耗时为，在产线间移动速度为，产线间距为。因此总时间为：。（）适应度函数值与染色体被选择概率成正比，成本越低，表示优化效果越好，染色体越应该在进化过程中被保留，因此将适应度函数设置为：。（）初始种群生成为了增加种群的丰富度，将第一层型材的下料顺序随机打乱并同时随机打乱第二层型材内部零件的排列顺序，以生成初始种群。迭代过程 选择采用轮盘赌规则对各个染色体进行选择，染色体的
15、 适 应 度 值 与 被 选 择 概 率 成 正 比。其 选 择 概率为：（）（）（），。（）式中表示种群中的染色体。为防止最优个体没有被选择到的特殊情况，本文采用精英选择模式，直接将最优个体放在新种群的第一位。交叉交叉算子：（）（），；，。（）其中：为个体的交叉概率，和为最大、最小交叉概率，为个体适应度值，为种群中的最大适应度值，为种群的平均适应度值。由于染色体第一层的顺序变化和第二层的顺序变化都会对适应度值产生影响，两者同时交叉容易丢失最优解，本文采用第一层和第二层分开交叉的模式，的个体进行第一层的交叉，的个体进行第二层的交叉，两层交叉均采用两点交叉，如图所示以一条产线的染色体为例说明第一
16、层交叉的步骤。其中和代表两个父代个体，和分别代表其对应的交叉后的子代个体，具体步骤如下：步骤在种群中随机找到两个个体和，并在第一层随机找到两个交叉位置点和；步骤将父代个体的和之间的第一层基因 和 赋值给的子代个体相应的位置，同时将的和间的第一层基因 和 赋值给的子代个体相应的位置。而的 和 的第二、三层属性继承中的 和 的第二、三层属性。同理，的 和 的第二、三层属性继承中的 和 的第二、三层属性。步骤子代个体其他空缺基因位全部从中继承，按其在中的位置左右顺序在中从左到右填补。以图所示为例，子代个体已经通过交叉确定了、之间 和 两段基因，然后将中剩余的 、和 三段基因依次填补在的段空缺基因位上。同理，子代个体也从中继承并填补。步骤同理，对于种群中的其他个体也进行交叉操作，得到新的种群。这样的方式避免了某些可能的优秀基因在交叉过程中丢失，如图中，若直接继承了的与间的三层基因位，继承了的与间的三层基因位，则两个子代中的 都将从继承，此时的 的后两层属性就会在该过程中丢失。第二层交叉的步骤与第一层类似：步骤如图所示，在种群中随机找到和两个个体，并在中随机选择一段基因，如第一层编号为 的基因。