1、第 卷第期计算机集成制造系统 年月 ：收稿日期：；修订日期：。；基金项目：国家自然科学基金资助项目（）；陕西省自然科学基础研究计划资助项目（，）；陕西省教育厅自然科学基金资助项目（）；西安建筑科技大学自然科学基础研究资助项目（）。：，（），（，），（），（）基于交替混合迭代搜索方法的预制构件生产调度与工人配置集成优化熊福力，杜瑶，曹劲松，汪琳婷（西安建筑科技大学 信息与控制工程学院，陕西西安 ）摘要：针对以往预制构件生产过程中工人指派与生产调度递阶求解方法的不足，研究了预制构件生产调度与工人配置的集成优化问题。在深入分析预制构件的生产工艺、工序约束、工人数量、工人技能水平等制约关系的基础上，首
2、先以最小化拖期惩罚和工人成本为目标建立了预制构件生产调度与工人配置集成优化数学模型。随后，为降低问题求解困难，基于交替分解思想，通过集成构造启发式、群体搜索、邻域搜索和破坏构造机制，提出一种混合遗传迭代贪婪交替搜索算法（）来解决该问题。其主要思想是：首先利用启发式方法产生一个初始工人配置和生产调度解；随后固定生产调度方案，设计一种混合遗传配置算法用于优化工人配置方案；反过来固定工人配置方案，设计一种迭代贪婪调度算法用于优化生产调度方案，如此两阶段交替优化，直到满足终止条件。最后，针对不同规模算例对所提算法进行了测试。计算结果显示，所提算法具有较优的求解质量、鲁棒性和收敛性。与预制构件制造企业常
3、用的基于经验的启发式方法相比，算法具有较大的改进率，有望产生显著的经济效益。关键词：预制构件生产调度；工人配置；集成优化；交替迭代优化；迭代贪婪搜索中图分类号：文献标识码：，（，）：，（），；，计算机集成制造系统第 卷 ；，：；引言装配式建筑现已成为国家和行业大力发展的新型建筑模式，具有施工时间短、生产效率高、环境污染小等特点。预制构件作为装配式建筑中极为重要的一环，也受到了这种新兴建筑模式发展带来的机遇和挑战。然而，对于国内现阶段预制构件生产模式而言，全自动化生产方式现在还为时过早，所有预制件工厂都采用机器处理与工人作业共存的方式。因此对于这种生产模式，同一项工作的效益可能随所配置的工人不同
4、而有很大的区别。这也导致相同工序的处理时间的可变性，最终将影响生产调度的可靠性。这种缺陷将造成生产管理效率低下、生产计划失效，潜在地导致运营混乱、工期延长和供应链成本增加。因此，工人配置与预制构件生产调度的集成优化对现阶段预制构件生产调度研究具有重要的理论意义和实用价值。在预制构件生产调度问题上，近年来已取得一定的成果。等以最小化完工时间和拖期提前交货惩罚成本为目标建立了流水车间调度模型（，）；等在此基础上建立了预制构件生产六阶段生产模型；等以最小化空闲时间、拖期和提前惩罚、存储成本、完工时间等目标建立了多预制生产线的 。随后 等提出了改进的九阶段生产调度模型，并考虑了模具制造、预制件存储和运
5、输等因素对生产过程的影响。熊福力等以最大化总净利润为目标解决了预制构件生产中交货期配置、订单选择与生产调度的同时决策问题。秦璇等则考虑了预制构件生产过程中受资源约束的多目标调度问题。上述研究缺乏实现生产成本和及时交货这两个相互冲突的目标之间权衡的方法。此外，实际生产中会有一定因素的干扰，每道工序的处理时间会随着工人资源配置的不同而不同，进而对生产调度造成直接影响，但以上研究中皆把每道工序的处理时间设置为固定值，即假定工人资源已经配置好，在实际生产过程中往往需要根据实际订单情况，对工人资源和生产调度进行集成优化。在考虑劳动力资源的调度优化方面，首先加入了对人员因素的考虑，提出员工对于生产进度表的
6、满意度是维持员工士气的重要原因，理想的生产计划应根据员工的工作日、休假、加班等偏好调 度，提 出 在 到 期 日 约 束 下 满 足 工 人 的 偏 好；等考虑使用具有不同生产力的员工组来制定劳动力计划的问题；等提出一种动态规划（，）算法，解决具有若干实际休假时间约束的人工调度问题，并给出了每个员工的工作顺序所决定的成本结构，同时提出一个适合于中等规模实例的 算法来确定最优的工作分配，使总人工成本最小化，同时在规定的约束条件下满足工作需求；等 提出一种具有两阶段启发式算法的混合整数规划模型，用于解决精密工程行业的人力调度问题，并提出一个两阶段的启发式算法，第一阶段通过考虑作业，机器和其生产计划
7、来计算每个班次的技能要求，第二 阶 段 通 过 考 虑 技 能 及 来 分 配 操 作 员 到 机 器；等 开发了一种改进的学习曲线来代替对数线性学习曲线，以监控工人绩效的提升，还考虑了工人先前的经验和机器在学习过程中的影响；等 提出一种数学模型，用于确定机组人员具有不同经验水平的单技能和多技能工人的最佳组合，以通过考虑多技能、不同技能水平和学习对机组人员的重叠影响来最大限度地缩短建设项目的工期生产率；陈俊杰等 建立了考虑胜任力差异的人力资源受限多目标项目调度问题模型，提出两阶段优化算法。上述工人配置问题研究中，在装配式建筑背景下，尚未有集成预制构件生产调度与工人配置的研究，究其原因主要有以下
8、第期熊福力 等：基于交替混合迭代搜索方法的预制构件生产调度与工人配置集成优化两点：（）从研究背景层面看，装配式建筑背景下的预制构件生产属于新兴产业，发展时间较短，虽然目前已有一些针对预制构件生产调度问题的相关研究，随着实际生产管理问题的不断涌现，以及信息技术和优化技术的不断发展，还存在较大的研究发展空间。而本文所研究的问题就是其中之一。（）从问题本身层面看，预制构件生产工序之间的差异较大，具有可利用时间与不可利用时间混合、串并行混合、可中断和不可中断混合以及资源可利用时间和资源量受限等特点，通常来讲，即使是单一工人配置问题和单一的生产调度问题就已经是 问题，因此在这种复杂生产背景下，将二者集成
9、优化无疑具有一定的挑战性，但同时对于提高预制构件生产企业净收益和改善客户满意度具有重要的意义。基于以上分析，本文考虑了预制构件生产背景下的生产调度与工人配置集成优化问题，以期为预制构件制造企业及类似制造企业提供有价值的管理启示。首先以最小化工人成本和拖期惩罚总费用为目标建立了预制构件工人配置与生产调度集成优化数学模型，随后基于交替分解思想，提出一种交替式混合遗传迭代贪婪搜索算法（，），并通过大量计算实验验证了所提算法的有效性。问题描述与数学模型 生产背景描述预制构件生产一般包含道工序：铸模；放置预埋件；混凝土浇灌；蒸汽养护；脱模；修复。每道工序仅有一台机器（即单生产线工作模式）。预制构件生产不
10、同于传统流水车间问题，其生产工序分为可中断工序（如第、工序）和不可中断工序（如第、工序）。如图中可中断工序情形和情形所示，可中断工序如果可以在工作时间内完成，则正常生产；否则，订单需继续处理至下班时间，剩余工作中断至次日工作时间完成。不可中断工序（如第、工序）指工序在处理完成前不能中断操作，否则会出现工件损坏等情况，不可中断工序如果在工人允许加班时间内可以完成则加班完成，否则该工序推迟于次日工作时间开始处理，如图中不可中断工序且需要人工情形和情形所示。第道工序蒸汽养护属于不可中断工序，但不需要工人操作，因此不受工作时间约束。其完工时间如图中不可中断且不需要人工情形情形所示。不同的工人配置方案不
11、但会造成订单处理时间的变化，影响订单的最大完工时间，而且配置不同等级或不同数量的工人需要支付的工人薪资成本也会随之变化。根据预制生产过程的实际工人需求，对各工序中所需工人数量进行约束，如表所示。其中第道工序为蒸汽养护，工厂采用全自动化方式处理，不需要工人干预且处理时间不随工人配置方案调整而变化。不同等级的工人具有不同的处理水计算机集成制造系统第 卷平和操作熟练度，对同一订单的处理时间也不相同，同时也具有不同的薪资待遇。因此，对不同等级工人的工作效率和薪资水平作出如下假设：将工人分为初级工人、中级工人、高级工人种等级；不同等级工人具有不同的工作效率和薪资水平；工人等级越低，工作效率和薪资水平也越
12、低。订单调整处理时间与原处理时间成正比，与分配工人的工作效率和工人数量，成反比。为使模型更加精确，工人成本的计算采用绩效制，即以工人工作时间计算工人工资，若工作时间为，则该工人没有工资。表各生产工序工人数量约束 ，问题描述基于以上预制构件生产背景，预制构件生产调度与工人配置集成优化问题可描述如下：个订单需要按照相同的处理顺序经过道预制构件生产工序且订单在每道工序上只能处理一次，每道工序每次只能同时处理一个订单（第道工序蒸汽养护除外，其采用并行处理方式）。各订单在各工序上所需的处理时间已知，但其会随工人配置方案的改变而变化，受工人配置方案影响的调整处理时间在订单处理前为已知。问题需要对各处理工序
13、上的工人进行配置，计算工人配置后的调整处理时间，并以最小化工人成本和订单拖期惩罚为目标优化生产调度和工人配置。为使问题更加明确，对生产过程作出如下假设：（）每道工序有且仅有一台机器；（）所 有 工 件、机 器 在 调 度 零 时 刻 均 为 可 用状态；（）所有工人在上班时间均为可配置状态；（）所有工人均有能力处理所有工序；（）每道工序配置的工人均为同一等级；（）工序间缓冲区容量为无限；（）不考虑工件恶化、人员请假和机器突发故障情况。（）各工人采用小时工作制，允许加班时间不超过 小 时，否 则 必 须 停 止 工 作。即 工 作 时 间，可加班时间，非工作时间。数学模型基于以上问题描述，建立如
14、下数学模型：（）标引和输入参数为订单数量；为工人数量；为工序数量；为工人等级数量；，为订单编号；，为工序编号；，为工人等级编号；，为工序上级工人的最小数量；，为工序上级工人的最大数量；，为工序上订单的原处理时间；，为工序上订单的调整处理时间；为订单交货期；为订单单位时间拖期惩罚；为级工人单位时间薪水；为级工人工作效率；为工作时间；为可加班时间（）；为非工作时间（）。（）决策变量，为工序中配置的级工人的数量；，为决策变量，表示工序中是否配置级工人；，为订单在工序上的完工时间；，为订单在工序上的累计完成时间。（）目标函数 （，（，）。（）（）约束条件，；（），；（），；（），；（），；（）第期熊福
15、力 等：基于交替混合迭代搜索方法的预制构件生产调度与工人配置集成优化，；（），（，），（，），（，），。（），；（），；（），；（），；（），；（），；（），。（）其中：式（）为目标函数最小化工人成本和拖期惩罚，其中 ，为订单拖期惩罚，如果订单在最后一道工序上的完工时间，即最大完工时间，小于或等于订单交货期，则该订单的拖期惩罚为，否则将会产生拖期惩罚。（，）为订单工人成本。式（）为订单在工序上的处理时间不早于上一订单在此工序上的完工时间，第道工序蒸汽养护为并行处理过程，不需要满足该约束；式（）表示订单在工序上的开始处理时间不早于该订单上一工序的完工时间；式（）表示可中断工序完工时间，若订单可在
16、当天工作时间内完成，则完成处理，完工时间为订单在工序上的累积完成时间，可由式（）计算得到，否则将中断至次日工作时间继续加工完成，完工时间为订单在工序上的累积完成时间，与非工作时间之和；式（）为订单在工序上的累计工作日，为订单在工序上的累积完成时间除以 并向下取整，若累积完成时间为 小时，则，；式（）为订单在不可中断工序且需要人工时的完工时间，若订单在当天工作时间可以完成，则完成处理，完工时间为订单在工序上的累积完成时间，否则将该工序推迟至次日工作时间开始加工，则完工时间为，；式（）为订单在不可中断工序且不需要人工时的完工时间，该工序采用并行处理，当工件在当天工作时间完成或第二天工作时间完成，则完工时间为订单在工序上的累积完成时间，否则工作处理时间延长至次日上班时间截止，则完工时间为（，）；式（）和式（）表示订单在不可中断工序且不需要人工时的累积完成时间和累计工作日；式（）和式（）限制各工序工人必须为同一等级；式（）为工人分配数量约束，分配人数不能超过各工序工人数量限制；式（）表示分配工人数和订单完工时间必须大于等于；式（）表示工人配置后的调整处理时间。从以上模型可以看出，从变量角度看，