王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·529· tion for a chromosome.As the two subsets are independent of each other and their evolutionary constraints are essentially different,a cooperative coevolution strategy was applied to evolve the subpopulations of these subsets using partheno-genetic and traditional genetic operators.Computational experiments on a large set of randomly generated instances were performed to verify the effectiveness and effi- ciency of this algorithm.Additionally,the impacts of problem size and rejection cost were studied experimentally.The results reveal that in the majority of cases characterized by various problem sizes and rejection costs,the proposed algorithm performs effectively and efficiently. KEY WORDS order acceptance and scheduling:unrelated parallel machines;setup time:machine-eligibility constraint:genetic al- gorithm:cooperative coevolution 订单接受作为订单管理的一项关键决策，不仅 proximation scheme,FPTAS);Hoogeveen等进一步 决定了后续的生产作业，而且对企业的盈利能力以 考虑了工件允许中断的情况，证明了问题是非确定 及客户关系的维持具有直接影响.传统的订单接受 性多项式复杂程度（non-deterministic polynomial, 决策是基于车间生产能力来决定的，但在面向订单 NP)难的，且若机器数可变则为强NP难；Sengup- 生产的现代制造业，多品种生产成为常态，机器环境 a因以最小化延迟/拖期和总拒绝成本之和为目标， 和工艺约束复杂，这种方法会与实际生产存在偏差， 提出了伪多项式算法和FPTAS;Miao等研究了一 造成计划外的生产成本和拖期罚金.为解决这一问 类有界限限制的并行批调度问题，证明了问题的NP 题，研究者们将订单接受与订单调度进行联合决策， 难特性，给出了以最小化Makespan/总加权完工时 提出了订单接受与调度问题.在此问题中，如果订 间和总拒绝成本之和为目标的伪多项式时间算法： 单被拒绝，则产生订单拒绝成本，该成本一般为损失 Hsu和Chang团针对具有恶化效应的工件，以最小 的收益或外包成本；如果订单被接受，则要求给出调 化总拒绝成本加总负荷或总完工时间为目标，证明 度方案，优化拖期惩罚费用（即拖期成本）.由于订 了问题是多项式可解的；Lin等图针对两台并行机 单层面的调度为指导性的粗调度，因而此类研究一 环境，提出了一种确定性3近似算法和随机3近似 般将车间或生产线抽象为传统调度问题中的机器 算法：Jiang和Tan针对机器具有不同可用时间， (以下统称为机器)，将订单抽象为工件（以下统称 且以最小化Makespan与总拒绝成本之和为目标的 为订单).此外，由于定制生产的要求，如冰箱制造 问题，提出了一种最坏性能比为2的启发式算法 等多品种混合生产模式多具有以下特征：①可加工 以上文献所研究的不相关并行机环境下的订单接受 机器限制：车间设置若干并行机（并行生产线），每 与调度问题，在问题约束以及优化目标上均与本文 台机器只能生产有限种类的产品，且机器的产品集 问题存在明显区别，且求解方法以基于问题特征的 合存在交叉，例如冰箱门体预装车间经常并存以下 伪多项式时间算法、FPTAS和构造启发式为主，无法 三种产线：仅支持玻璃材质、仅支持钣金材质和同时 扩展应用于本文问题. 支持两种材质的预装发泡产线：②不相关并行机环 在问题复杂性方面，以最小化总完工时间为目 境：由于机器所采用的技术有所区别，同一个产品在 标、具有顺序与机器依赖的安装时间和可加工机器 不同机器上的加工时间不同：③顺序与机器依赖的 限制的不相关并行机调度是本文问题的一个特例. 安装时间：由于技术差别，机器因切换工件而产生的 在此特例中，订单交货期为0，拖期的单位成本为1， 安装时间不仅同工件顺序相关，也同机器相关.本 订单拒绝成本为一个足够大的值.Joo和Kimo证 文针对上述特征，研究不相关并行机环境下具有安 明了该问题是NP难的，因此本文问题也是NP难 装时间和可加工机器限制的订单接受与调度问题， 的，采用精确算法无法在有限时间内获得问题的解. 优化目标为最小化拒绝成本和拖期成本总和. 因此，本文将通过对问题性质的探讨，提出订单拒绝 从订单拒绝角度考虑的订单接受与调度问题也 规则，进而基于协同进化策略设计遗传算法进行 称为考虑拒绝的调度(scheduling with rejection),文 求解 献-2]对该问题进行了详尽的综述.目前，不相 1问题描述与建模 关并行机的订单接受与调度问题研究较少，主要成 果如下：Angel等同以最小化最大完工时间(makes- 本文所研究的订单接受与调度问题描述如下： pan)和订单总拒绝成本之和为目标，提出了一种完 给定n个订单和m台不相关并行机，同一订单在不 全多项式时间近似方案(fully polynomial time ap- 同机器上的加工时间不同.订单允许被拒绝，若拒王柏琳等: 安装时间和机器受限的订单接受与并行机调度 tion for a chromosome． As the two subsets are independent of each other and their evolutionary constraints are essentially different，a cooperative coevolution strategy was applied to evolve the subpopulations of these subsets using partheno-genetic and traditional genetic operators． Computational experiments on a large set of randomly generated instances were performed to verify the effectiveness and effi￾ciency of this algorithm． Additionally，the impacts of problem size and rejection cost were studied experimentally． The results reveal that in the majority of cases characterized by various problem sizes and rejection costs，the proposed algorithm performs effectively and efficiently． KEY WOＲDS order acceptance and scheduling; unrelated parallel machines; setup time; machine-eligibility constraint; genetic al￾gorithm; cooperative coevolution 订单接受作为订单管理的一项关键决策，不仅 决定了后续的生产作业，而且对企业的盈利能力以 及客户关系的维持具有直接影响． 传统的订单接受 决策是基于车间生产能力来决定的，但在面向订单 生产的现代制造业，多品种生产成为常态，机器环境 和工艺约束复杂，这种方法会与实际生产存在偏差， 造成计划外的生产成本和拖期罚金． 为解决这一问 题，研究者们将订单接受与订单调度进行联合决策， 提出了订单接受与调度问题． 在此问题中，如果订 单被拒绝，则产生订单拒绝成本，该成本一般为损失 的收益或外包成本; 如果订单被接受，则要求给出调 度方案，优化拖期惩罚费用( 即拖期成本) ． 由于订 单层面的调度为指导性的粗调度，因而此类研究一 般将车间或生产线抽象为传统调度问题中的机器 ( 以下统称为机器) ，将订单抽象为工件( 以下统称 为订单) ． 此外，由于定制生产的要求，如冰箱制造 等多品种混合生产模式多具有以下特征: ①可加工 机器限制: 车间设置若干并行机( 并行生产线) ，每 台机器只能生产有限种类的产品，且机器的产品集 合存在交叉，例如冰箱门体预装车间经常并存以下 三种产线: 仅支持玻璃材质、仅支持钣金材质和同时 支持两种材质的预装发泡产线; ②不相关并行机环 境: 由于机器所采用的技术有所区别，同一个产品在 不同机器上的加工时间不同; ③顺序与机器依赖的 安装时间: 由于技术差别，机器因切换工件而产生的 安装时间不仅同工件顺序相关，也同机器相关． 本 文针对上述特征，研究不相关并行机环境下具有安 装时间和可加工机器限制的订单接受与调度问题， 优化目标为最小化拒绝成本和拖期成本总和． 从订单拒绝角度考虑的订单接受与调度问题也 称为考虑拒绝的调度( scheduling with rejection) ，文 献［1--2］对该问题进行了详尽的综述． 目前，不相 关并行机的订单接受与调度问题研究较少，主要成 果如下: Angel 等［3］以最小化最大完工时间( makes￾pan) 和订单总拒绝成本之和为目标，提出了一种完 全多项 式 时 间 近 似 方 案( fully polynomial time ap￾proximation scheme，FPTAS) ; Hoogeveen 等［4］进一步 考虑了工件允许中断的情况，证明了问题是非确定 性多项式复杂程度 ( non-deterministic polynomial， NP) 难的，且若机器数可变则为强 NP 难; Sengup￾ta［5］以最小化延迟/拖期和总拒绝成本之和为目标， 提出了伪多项式算法和 FPTAS; Miao 等［6］研究了一 类有界限限制的并行批调度问题，证明了问题的 NP 难特性，给出了以最小化 Makespan /总加权完工时 间和总拒绝成本之和为目标的伪多项式时间算法; Hsu 和 Chang［7］针对具有恶化效应的工件，以最小 化总拒绝成本加总负荷或总完工时间为目标，证明 了问题是多项式可解的; Lin 等［8］针对两台并行机 环境，提出了一种确定性 3-近似算法和随机 3-近似 算法; Jiang 和 Tan［9］针对机器具有不同可用时间， 且以最小化 Makespan 与总拒绝成本之和为目标的 问题，提出了一种最坏性能比为 2 的启发式算法． 以上文献所研究的不相关并行机环境下的订单接受 与调度问题，在问题约束以及优化目标上均与本文 问题存在明显区别，且求解方法以基于问题特征的 伪多项式时间算法、FPTAS 和构造启发式为主，无法 扩展应用于本文问题． 在问题复杂性方面，以最小化总完工时间为目 标、具有顺序与机器依赖的安装时间和可加工机器 限制的不相关并行机调度是本文问题的一个特例． 在此特例中，订单交货期为 0，拖期的单位成本为 1， 订单拒绝成本为一个足够大的值． Joo 和 Kim［10］证 明了该问题是 NP 难的，因此本文问题也是 NP 难 的，采用精确算法无法在有限时间内获得问题的解． 因此，本文将通过对问题性质的探讨，提出订单拒绝 规则，进而基于协同进化策略设计遗传算法进行 求解． 1 问题描述与建模 本文所研究的订单接受与调度问题描述如下: 给定 n 个订单和 m 台不相关并行机，同一订单在不 同机器上的加工时间不同． 订单允许被拒绝，若拒 · 925 ·