安装时间和机器受限的订单接受与并行机调度

工程科学学报，第41卷，第4期：528-538,2019年4月 Chinese Journal of Engineering,Vol.41,No.4:528-538,April 2019 DOI:10.13374/j.issn2095-9389.2019.04.014:http://journals.ustb.edu.cn 安装时间和机器受限的订单接受与并行机调度 王柏琳12)四，李铁克2)，王海凤2) 1)北京科技大学东凌经济管理学院，北京1000832)钢铁生产制造执行系统技术教有部工程研究中心，北京100083 ☒通信作者，E-mail:wangbl@usth.cdu.cm 摘要订单接受与不相关并行机调度是订单接受与订单调度的联合决策，广泛存在于面向定制的多品种混合生产环境中 针对这一问题，考虑了顺序与机器依赖的安装时间以及可加工机器限制，并以最小化总成本为优化目标.其中，总成本由被接 受订单的总拖期成本和被拒绝订单的总拒绝成本构成.通过分析订单拒绝对目标的影响，提出了列表拒绝方法和订单拒绝规 则，进而设计了协同进化遗传算法.算法将染色体编码分解为订单列表和订单指派两个个体，提出了基于列表拒绝方法的解 码方案来进行订单拒绝决策.由于两个个体相互独立，且二者的进化约束不同，因而引入协同进化策略，并根据个体的编码特 征，分别采用单亲遗传算子和传统遗传算子进行遗传操作.数据实验验证了算法的有效性和求解效率，并对问题规模和订单 拒绝成本对算法性能的影响进行了分析. 关键词订单接受与调度：不相关并行机：安装时间：可加工机器限制：遗传算法：协同进化 分类号TP278 Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints WANG Bai-lin,LI Tie-ke,WANG Hai-feng 1)Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China 2)Engineering Research Center of MES Technology for Iron&Steel Production,Ministry of Education,Beijing 100083,China Corresponding author,E-mail:wangbl@ustb.edu.cn ABSTRACT Integration of order acceptance and scheduling on unrelated parallel machines is a joint decision problem,and arise from the multivariety customized production environment,which usually has the following characteristics.First,there are a number of parallel machines (production lines),each of which can only produce a limited variety of products referred as the machine-eligibility constraint.Second,the processing technologies of various machines differ:thus,these parallel machines are unrelated.Third,because the machines are unrelated,the setup time of an order is related not only to the order sequence but also to the machine used,which is called a sequence-and machine-dependent setup time.To minimize total cost,this study investigates the scheduling problems posed by order acceptance and unrelated parallel machines with setup time and machine-eligibility constraints.In this problem,an order has two options,rejection or acceptance.If an order is rejected,it generates a rejection cost.Otherwise,the order process must be completed before the due date,or there will be a tardiness cost.Therefore,the total cost spent is calculated as the sum of the total rejection cost of rejected orders and total weighted tardiness cost of accepted orders.To solve this problem,the effect of rejecting an order on the total cost was analyzed,and a list of rejecting methods and rejection rules were proposed.Furthermore,a cooperative coevolving genetic al- gorithm (CCGA)was developed.In this CCGA,an encoding scheme was proposed that divides chromosomes into two subsets corre- sponding to the order list and order assignment.Moreover,a list-rejecting-based decoding procedure was presented for deciding rejec- 收稿日期：2018-03-08 基金项目：国家自然科学基金资助项目(71701016,71471015)：北京市自然科学基金资助项目(9174038)：教有部人文社会科学研究青年基金 项目资助(17Y)C630143):中央高校基本科研业务费资助项目(FRF-BD-18009A)

工程科学学报，第 41 卷，第 4 期: 528--538，2019 年 4 月 Chinese Journal of Engineering，Vol． 41，No． 4: 528--538，April 2019 DOI: 10． 13374 /j． issn2095--9389． 2019． 04． 014; http: / /journals． ustb． edu． cn 安装时间和机器受限的订单接受与并行机调度 王柏琳1，2) ，李铁克1，2) ，王海凤1，2) 1) 北京科技大学东凌经济管理学院，北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083 通信作者，E-mail: wangbl@ ustb． edu． cn 摘 要 订单接受与不相关并行机调度是订单接受与订单调度的联合决策，广泛存在于面向定制的多品种混合生产环境中． 针对这一问题，考虑了顺序与机器依赖的安装时间以及可加工机器限制，并以最小化总成本为优化目标． 其中，总成本由被接 受订单的总拖期成本和被拒绝订单的总拒绝成本构成． 通过分析订单拒绝对目标的影响，提出了列表拒绝方法和订单拒绝规 则，进而设计了协同进化遗传算法． 算法将染色体编码分解为订单列表和订单指派两个个体，提出了基于列表拒绝方法的解 码方案来进行订单拒绝决策． 由于两个个体相互独立，且二者的进化约束不同，因而引入协同进化策略，并根据个体的编码特 征，分别采用单亲遗传算子和传统遗传算子进行遗传操作． 数据实验验证了算法的有效性和求解效率，并对问题规模和订单 拒绝成本对算法性能的影响进行了分析． 关键词 订单接受与调度; 不相关并行机; 安装时间; 可加工机器限制; 遗传算法; 协同进化 分类号 TP278 收稿日期: 2018--03--08 基金项目: 国家自然科学基金资助项目( 71701016，71471015) ; 北京市自然科学基金资助项目( 9174038) ; 教育部人文社会科学研究青年基金 项目资助( 17YJC630143) ; 中央高校基本科研业务费资助项目( FＲF--BD--18--009A) Order acceptance and scheduling on parallel machines with setup time and machine-eligibility constraints WANG Bai-lin1，2)  ，LI Tie-ke1，2) ，WANG Hai-feng1，2) 1) Donlinks School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China 2) Engineering Ｒesearch Center of MES Technology for Iron ＆ Steel Production，Ministry of Education，Beijing 100083，China Corresponding author，E-mail: wangbl@ ustb． edu． cn ABSTＲACT Integration of order acceptance and scheduling on unrelated parallel machines is a joint decision problem，and arise from the multi-variety customized production environment，which usually has the following characteristics． First，there are a number of parallel machines ( production lines) ，each of which can only produce a limited variety of products referred as the machine-eligibility constraint． Second，the processing technologies of various machines differ; thus，these parallel machines are unrelated． Third，because the machines are unrelated，the setup time of an order is related not only to the order sequence but also to the machine used，which is called a sequence-and machine-dependent setup time． To minimize total cost，this study investigates the scheduling problems posed by order acceptance and unrelated parallel machines with setup time and machine-eligibility constraints． In this problem，an order has two options，rejection or acceptance． If an order is rejected，it generates a rejection cost． Otherwise，the order process must be completed before the due date，or there will be a tardiness cost． Therefore，the total cost spent is calculated as the sum of the total rejection cost of rejected orders and total weighted tardiness cost of accepted orders． To solve this problem，the effect of rejecting an order on the total cost was analyzed，and a list of rejecting methods and rejection rules were proposed． Furthermore，a cooperative coevolving genetic al￾gorithm ( CCGA) was developed． In this CCGA，an encoding scheme was proposed that divides chromosomes into two subsets corre￾sponding to the order list and order assignment． Moreover，a list-rejecting-based decoding procedure was presented for deciding rejec-

王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·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 ·

·530 工程科学学报，第41卷，第4期 绝则产生拒绝成本，若接受则必须安排生产，此时可 器限制的订单接受与调度模型如下： 能产生拖期成本，且每个订单具有不同的单位拖期 min F= 惩罚.此外，订单只允许在指定的机器集合中选择 A=A1-)回+A7 加工机器，且存在顺序与机器依赖的安装时间约束. (1) 问题要求确定被拒绝的订单集合以及被接受订单的 =0j=1,2…n (2) 调度方案，优化目标为最小化总拒绝成本和总拖期 ,台 成本之和 正如引言所述，己有文献所研究的订单接受与 ∑)0≤1，i=1,2,m,k=1,2,n（63) 不相关并行机调度在问题约束以及优化目标方面均 与本文存在差别，因此有必要建立问题的数学模型， 三X≤M月 对问题进行准确描述.本文问题是不相关并行机调 i=1,2,…,m,k=1,2,…,n-1 (4) 度的扩展问题，目标函数则是在总加权拖期这一经 C1-Pa-s-C+M(2-yk+)-y）≥0， 典调度目标的基础上增加了总拒绝成本.调度问题 j≠l,j,l=1,…,n,VieM nM, 的关键是确定机器上的工件（订单）加工序列，相应 k=1,2,…,n-1 (5) 的决策变量在模型中有两种基于0一1整型变量的 (6) 表示方式：一种是定义订单间的相对位置关系， C-∑y,≥0，j=1,2,n M,= 另一种则是定义订单在机器上的具体位置.安装时 T,≥0，j=1,2,…,n (7) 间约束下的不相关并行机调度多采用前一种表示方 T+M(1-x）≥C-d,j=1,2,…,n (8) 法，回，但后一种方法能更为直观的表示订单加工 y城=0，j,k=1,2,…,n,Hi∈{1,2，…，m}1M 序列，易于与算法中的编码方案相互转化（参见本 (9) 文第2节首段)，因此本文采用后一种方式建模.此 y继∈{0,1}，j,k=1,2,…,n,i∈M,(10) 外，考虑到本文问题还需要确定订单的接受决策，且 目标函数(1)表示最小化总成本，即总拒绝成 该决策仅有“接受”拒绝”两种状态，因此在模型中 本和总拖期成本之和.约束(2)表示若订单j被拒 引入0一1整型变量来表示订单的接受情况.具体建 绝则不允许加工，否则该订单必须且只能指派到一 模如下. 台可加工机器的一个位置上.约束(4)表示每个机 首先，为便于建模，定义以下符号 器位置至多允许安排一个订单；约束(4)表示机器 (1)索引与集合.m为机器数量：i为机器编号， 位置编号的连续性，若位置k未安排订单，则之后的 i=1,2,,m;n为订单数量：j为订单编号，j=1,2, 位置也不允许安排订单.约束(5)要求同一台机器 ·,n;k为机器的加工位置，表示在机器上第k个加 在同一时刻只允许加工一个订单，且紧邻订单之间 工的订单，1≤k≤n;M为订单j的可加工机器编号 存在顺序与机器依赖的安装时间.约束(6)限定了 集合. 订单的完工时间.约束(7)和(8)定义了订单拖期 (2)问题参数.P为订单j在机器i上的加工时 约束(9)为可加工机器限制，订单不允许被指派到 间；r©心；和d,为订单j的拒绝成本、单位拖期成本 不可加工的机器上.约束(10)为变量取值约束. 和交货期；s为订单j被指派到机器i且紧前订单为 此模型为混合整数线性规划(mixed integer lin- l时的安装时间；M为极大的正数. ear programming,MLP),前文也指出该问题是NP (3)决策变量.x为0-1变量，若订单j被接受 难的.针对这类问题，遗传算法等群智能算法是一 则为1，否则为0；y继为0-1变量，若订单j被指派到 种有效方法，且将问题特征引入算法中能够提高求 机器i的位置k上则为1，否则为0；C:为订单j的完 解质量.因此，本文将首先探讨问题的性质，进而结 工时间. 合问题性质设计算法 (4)决策变量的衍生变量.T:为订单j的拖期， 2基于调度的订单拒绝策略 T=max{C-d,0};F和f为总成本和订单j的成 本：若订单j被拒绝，则f=rej,否则f=w,T: 订单接受与调度是一类联合决策问题，令RS 表示拒绝订单集合，Ⅱ表示接受订单的调度方案， F- 则问题解可表示为决策对RS,Ⅱ).根据MP模 不相关并行机环境下具有安装时间和可加工机 型，RS和Ⅱ定义为：RS={jlx=0,j∈{1,2

工程科学学报，第 41 卷，第 4 期 绝则产生拒绝成本，若接受则必须安排生产，此时可 能产生拖期成本，且每个订单具有不同的单位拖期 惩罚． 此外，订单只允许在指定的机器集合中选择 加工机器，且存在顺序与机器依赖的安装时间约束． 问题要求确定被拒绝的订单集合以及被接受订单的 调度方案，优化目标为最小化总拒绝成本和总拖期 成本之和． 正如引言所述，已有文献所研究的订单接受与 不相关并行机调度在问题约束以及优化目标方面均 与本文存在差别，因此有必要建立问题的数学模型， 对问题进行准确描述． 本文问题是不相关并行机调 度的扩展问题，目标函数则是在总加权拖期这一经 典调度目标的基础上增加了总拒绝成本． 调度问题 的关键是确定机器上的工件( 订单) 加工序列，相应 的决策变量在模型中有两种基于 0--1 整型变量的 表示方式［11］: 一种是定义订单间的相对位置关系， 另一种则是定义订单在机器上的具体位置． 安装时 间约束下的不相关并行机调度多采用前一种表示方 法［10，12］，但后一种方法能更为直观的表示订单加工 序列，易于与算法中的编码方案相互转化( 参见本 文第 2 节首段) ，因此本文采用后一种方式建模． 此 外，考虑到本文问题还需要确定订单的接受决策，且 该决策仅有“接受”“拒绝”两种状态，因此在模型中 引入 0--1 整型变量来表示订单的接受情况． 具体建 模如下． 首先，为便于建模，定义以下符号: ( 1) 索引与集合． m 为机器数量; i 为机器编号， i = 1，2，…，m; n 为订单数量; j 为订单编号，j = 1，2， …，n; k 为机器的加工位置，表示在机器上第 k 个加 工的订单，1≤k≤n; Mj 为订单 j 的可加工机器编号 集合． ( 2) 问题参数． pij为订单 j 在机器 i 上的加工时 间; rejj 、wj 和 dj 为订单 j 的拒绝成本、单位拖期成本 和交货期; silj为订单 j 被指派到机器 i 且紧前订单为 l 时的安装时间; M 为极大的正数． ( 3) 决策变量． xj 为 0--1 变量，若订单 j 被接受 则为 1，否则为 0; yijk为 0--1 变量，若订单 j 被指派到 机器 i 的位置 k 上则为 1，否则为 0; Cj 为订单 j 的完 工时间． ( 4) 决策变量的衍生变量． Tj 为订单 j 的拖期， Tj = max { Cj － dj ，0} ; F 和 fj 为总成本和订单 j 的成 本; 若 订 单 j 被 拒 绝，则 fj = rejj ，否 则 fj = wj Tj ; F = ∑ n j = 1 fj ． 不相关并行机环境下具有安装时间和可加工机 器限制的订单接受与调度模型如下: min F = ∑ n j = 1 fj = ∑ n j = 1 ( 1 － xj ) rejj + ∑ n j = 1 xj wj Tj ( 1) s． t． xj － ∑i∈Mj ∑ n k = 1 yijk = 0，j = 1，2，…，n ( 2) ∑ n j = 1 yijk≤1，i = 1，2，…，m，k = 1，2，…，n ( 3) ∑ n j = 1 yi，j，k + 1≤M ∑ n j = 1 yijk， i = 1，2，…，m，k = 1，2，…，n － 1 ( 4) Cl － pil － sijl － Cj + M( 2 － yil( k + 1) － yijk ) ≥0， j≠l，j，l = 1，…，n，i∈Mj∩Ml， k = 1，2，……，n － 1 ( 5) Cj － ∑i∈Mj ∑ n k = 1 yijk pij≥0，j = 1，2，…，n ( 6) Tj≥0，j = 1，2，…，n ( 7) Tj + M( 1 － xj ) ≥Cj － dj ，j = 1，2，…，n ( 8) yijk = 0，j，k = 1，2，…，n，i∈{ 1，2，…，m} \Mj ( 9) xj ，yijk∈{ 0，1} ，j，k = 1，2，…，n，i∈Mj ( 10) 目标函数( 1) 表示最小化总成本，即总拒绝成 本和总拖期成本之和． 约束( 2) 表示若订单 j 被拒 绝则不允许加工，否则该订单必须且只能指派到一 台可加工机器的一个位置上． 约束( 4) 表示每个机 器位置至多允许安排一个订单; 约束( 4) 表示机器 位置编号的连续性，若位置 k 未安排订单，则之后的 位置也不允许安排订单． 约束( 5) 要求同一台机器 在同一时刻只允许加工一个订单，且紧邻订单之间 存在顺序与机器依赖的安装时间． 约束( 6) 限定了 订单的完工时间． 约束( 7) 和( 8) 定义了订单拖期． 约束( 9) 为可加工机器限制，订单不允许被指派到 不可加工的机器上． 约束( 10) 为变量取值约束． 此模型为混合整数线性规划( mixed integer lin￾ear programming，MILP) ，前文也指出该问题是 NP 难的． 针对这类问题，遗传算法等群智能算法是一 种有效方法，且将问题特征引入算法中能够提高求 解质量． 因此，本文将首先探讨问题的性质，进而结 合问题性质设计算法． 2 基于调度的订单拒绝策略 订单接受与调度是一类联合决策问题，令 ＲS 表示拒绝订单集合，Π 表示接受订单的调度方案， 则问题解可表示为决策对〈ＲS，Π〉． 根据 MILP 模 型，ＲS 和 Π 定义为: ＲS = { j | xj = 0，j∈{ 1，2，…， · 035 ·

王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·531· n}};Ⅱ={π：li=1,…,m},其中π：为机器i的订单 综上，当ej,≤0仙T时，若π：(k)为机 序列，T:(k)为π：的第k个订单，|T:I为π：包含的 器i的首/末订单或满足△k≥0，则拒绝π：(k)有 订单数量.若y狱=1则T:(k)=方.给定RS,Ⅱ)，完 F' 工时间C可按式计算. 定理2.给定初始调度。={m1},若m C(D)=Pi() {p,}≥max{s}-2min{s}（i),则对于由Ⅱo C)=Crk-)+sim-)m(+Pa因’ j.kem k=2,…,lT:l,i=1,2,…,m (11) 衍生出来的任何决策对RS,Ⅱ)，拒绝满足r©j仙≤ 因此，问题求解的关键在于如何确定决策对 0,T,(困的订单T:(k)均不会使总成本增加，即 F≤F RS,Ⅱ〉，对此本文采用如下策略：首先，不考虑订 单拒绝，生成包含所有工件的初始调度，记为；进 证明：因为RS,T)是由Ⅱ。得到的，有π：二π 而，根据完工时间等参数来确定拒绝订单集合.显 (Hi),因此min{pg}≥min{Pg},marx{st}≤max JcnI jcm jke j.kem 然，一个初始调度能够衍生出2”个决策对RS,Ⅱ)， {s},min{s球}≥min{s},进而min{pg}≥max jkem j.ke jeal jkem 若将其中成本最低的称为°的最好解，则问题最 {s}-2min{s}.所以，对于Vi,当1<k<lπ：I 优解必然存在于所有初始调度的最好解之中.因 时，式(12)成立 此，基于此策略的算法是可行的，而其有效性取决于 基于调度的订单拒绝策略，本节将探讨这一问题 △g=Pm,因-Sia,k-)mt+1)+S,k-1）m因+ 2.1订单拒绝的相关性质 sw:(+w≥min{p}-max{s}+2min{s}≥0 本节将分析拒绝一个订单对总成本的影响.给 (12) 定决策对RS,Ⅱ)，总成本为F:〈RS,Ⅱ〉是拒绝订 根据定理1，当k=1或|π：1或满足△4≥0时，新 单π：(k)的新决策对，即RS=RSU{T:(k)},π= 决策对RS,Ⅱ)满足F≤F,定理2成立 π：1{m:(k)},总成本为F;定义△：=P因+ 2.2列表拒绝与拒绝规则 (s-D,因+5，国=+D一5-=+)），其中k= 对于订单拒绝决策，本节提出一种基于初始调 2,…,lπ：1-1，i=1,2,…,m,则定理1成立 度Ⅱ。的列表拒绝方法，即以加工序列π∈Ⅱ。(i= 定理1.若订单T:（k)满足rejW≤0( 1,…,m)为列表，依次确定是否拒绝当前订单，其 Tw,且π：(k)为机器i的首/宋订单或满足△≥0， 中，针对当前订单的订单拒绝规则是列表拒绝方法 则拒绝π：(k)不会导致总成本增加，即F≤F 的关键 证明：由于rej,仙≤0仙T份’T:(k)满足fW≤ 假设订单π()为当前待定的订单，π：为机器 f·如果jS均满足≤，则有F≤F.下面 i上已确定接受的订单序列，显然π：中的订单均位 于π(k)之前加工，即1π1<k.式(13)(14)定义了 将证明这点 (1)拒绝订单T:()不会影响其他机器的订单， π(k)的当前完工时间C和拖期T9,其中π： 也不影响在其之前加工的订单.即，对于jRSU (Iπ：I)为机器i上最新被接受的订单编号.显然若 π：和j∈{π：(1)，…，π：(k-1)},有f=f 订单π(k)被接受，则其紧前订单为π：(1π：I) (2)l=k+1,…,|T:时f0和f,0关系如下： TC》+sm,lW)+p.因，ifT:≠⑦ C= ①若k=1,则C2)=Pm,0+s,m2)+Pa(2’ Pi.m(因’ otherwise C(2)=Pim(2C(0-C(0)=C(2)-C(2)<0(= (13) 2,,lml).因此f0≤fw,F≤F. T=max (C-d,0} (14) ②若k=|π：1，则拒绝π：()不会影响所有接受 根据定理1，本节提出了订单拒绝规则Rulel.. 订单，因此F-F=f仙-f的≤0. Rle1.若rejP≤0TP,并且以下情况 ③若1<k<|π：1，则Ck+)=Ck-)+ 之一成立，则拒绝订单π(k): Sm,-)r因+Pm,因+sm,(因m,+)+Pmk+),Ck+)= (a)m:=☑：(b)k=|πI:(c)△k=Pw+ C4-)+5a4-+D+Pa+,因此C4+)- （s,rm),9因+S份9k+)-5a山9+1)）≥0 C4+D=-△·当△≥0，有C,4+)≤C,u+),此时 根据定理1可知，给定初始调度Ⅱ。，采用基于 l=k+1,…,1m:1,订单π：(1)完工时间将提前 Rule1的列表拒绝方法，得到的最终决策对RS,I) △k,因而f0≤f0,F≤F. 的总成本必然不大于（⑦，Ⅱ。〉的总成本.此外，根

王柏琳等: 安装时间和机器受限的订单接受与并行机调度 n} } ; Π = { πi | i = 1，…，m} ，其中 πi 为机器 i 的订单 序列，πi ( k) 为 πi 的第 k 个订单，| πi | 为 πi 包含的 订单数量． 若 yijk = 1 则 πi ( k) = j． 给定〈ＲS，Π〉，完 工时间 Cj 可按式计算． Cπi ( 1) = piπi ( 1) ; Cπi ( k) = Cπi ( k － 1) + siπi ( k － 1) πi ( k) + piπi ( k) ， k = 2，…，|πi |，i = 1，2，…，m ( 11) 因此，问题求解的关键在于如何确定决策对 〈ＲS，Π〉，对此本文采用如下策略: 首先，不考虑订 单拒绝，生成包含所有工件的初始调度，记为 Π0 ; 进 而，根据完工时间等参数来确定拒绝订单集合． 显 然，一个初始调度能够衍生出 2n 个决策对〈ＲS，Π〉， 若将其中成本最低的称为 Π0 的最好解，则问题最 优解必然存在于所有初始调度的最好解之中． 因 此，基于此策略的算法是可行的，而其有效性取决于 基于调度的订单拒绝策略，本节将探讨这一问题． 2. 1 订单拒绝的相关性质 本节将分析拒绝一个订单对总成本的影响． 给 定决策对〈ＲS，Π〉，总成本为 F; 〈ＲS'，Π'〉是拒绝订 单 πi ( k) 的新决策对，即 ＲS' = ＲS∪{ πi ( k) } ，π' i = πi \ { πi ( k ) } ，总 成 本 为 F'; 定 义 Δk = piπi ( k) + ( siπi ( k － 1) πi ( k) + siπi ( k) πi ( k + 1) － siπi ( k － 1) πi ( k + 1) ) ，其中 k = 2，…，|πi | － 1，i = 1，2，…，m，则定理 1 成立． 定理 1． 若 订 单 πi ( k ) 满 足 rejπi ( k) ≤ wπi ( k) Tπi ( k) ，且 πi ( k) 为机器 i 的首/末订单或满足 Δk≥0， 则拒绝 πi ( k) 不会导致总成本增加，即 F'≤F． 证明: 由于 rejπi ( k) ≤wπi ( k) Tπi ( k) ，πi ( k) 满足 f'πi ( k) ≤ fπi ( k) ． 如果jＲS'均满足 f'j≤fj ，则有 F'≤F． 下面 将证明这点． ( 1) 拒绝订单 πi ( k) 不会影响其他机器的订单， 也不影响在其之前加工的订单． 即，对于 jＲS'∪ πi 和 j∈{ πi ( 1) ，…，πi ( k － 1) } ，有 f'j = fj ． ( 2) l = k + 1，…，|πi |时，f'πi ( l) 和 fπi ( l) 关系如下: ①若 k = 1，则 Cπi ( 2) = piπi ( 1) + siπi ( 1) πi ( 2) + piπi ( 2) ， C'πi ( 2) = piπi ( 2) ，C'πi ( l) － Cπi ( l) = C'πi ( 2) － Cπi ( 2) ＜ 0( l = 2，…，|πi | ) ． 因此 f'πi ( l) ≤fπi ( l) ，F'≤F． ②若 k = |πi |，则拒绝 πi ( k) 不会影响所有接受 订单，因此 F' － F = f'πi ( k) － fπi ( k) ≤0． ③若 1 ＜ k ＜ | πi |，则 Cπi ( k + 1) = Cπi ( k － 1) + siπi ( k － 1) πi ( k) + piπi ( k) + siπi ( k) πi ( k + 1) + piπi ( k + 1) ，C'πi ( k + 1) = Cπi ( k － 1) + siπi ( k － 1) πi ( k + 1) + piπi ( k + 1) ，因 此 C'πi ( k + 1) － Cπi ( k + 1) = － Δk ． 当 Δk≥0，有 C'πi ( k + 1) ≤Cπi ( k + 1) ，此时 l = k + 1，…，| πi |，订单 πi ( l) 完工时间将提前 Δk，因而 f'πi ( l) ≤fπi ( l) ，F'≤F． 综上，当 rejπi ( k) ≤wπi ( k) Tπi ( k) 时，若 πi ( k) 为机 器 i 的首/末订单或满足 Δk ≥0，则拒绝 πi ( k) 有 F'≤F． 定理 2． 给定初始调度 Π0 = { π0 i | i} ，若min j∈π0 i { pij} ≥ max j，k∈π0 i { sijk } － 2 min j，k∈π0 i { sijk } ( i) ，则对于由 Π0 衍生出来的任何决策对〈ＲS，Π〉，拒绝满足 rejπi ( k) ≤ wπi ( k) Tπi ( k) 的订单 πi ( k) 均不会使总成本增加，即 F'≤F． 证明: 因为〈ＲS，Π〉是由 Π0 得到的，有 πiπ0 i ( i) ，因此min j∈πi { pij} ≥min j∈π0 i { pij} ，max j，k∈πi { sijk } ≤ max j，k∈π0 i { sijk } ，min j，k∈πi { sijk } ≥ min j，k∈π0 i { sijk } ，进而min j∈πi { pij} ≥ max j，k∈πi { sijk } － 2 min j，k∈πi { sijk } ． 所以，对于i，当 1 ＜ k ＜ | πi | 时，式( 12) 成立． Δk = piπi ( k) － siπi ( k － 1) πi ( k + 1) + siπi ( k － 1) πi ( k) + siπi ( k) πi ( k + 1) ≥min j∈πi { pij} － max j，k∈πi { sijk } + 2 min j，k∈πi { sijk } ≥0 ( 12) 根据定理 1，当 k = 1 或|πi |或满足 Δk≥0 时，新 决策对〈ＲS'，Π'〉满足 F'≤F，定理 2 成立． 2. 2 列表拒绝与拒绝规则 对于订单拒绝决策，本节提出一种基于初始调 度 Π0 的列表拒绝方法，即以加工序列 π0 i ∈Π0 ( i = 1，…，m) 为列表，依次确定是否拒绝当前订单，其 中，针对当前订单的订单拒绝规则是列表拒绝方法 的关键． 假设订单 π0 i ( k) 为当前待定的订单，πi 为机器 i 上已确定接受的订单序列，显然 πi 中的订单均位 于 π0 i ( k) 之前加工，即|πi | ＜ k． 式( 13) ( 14) 定义了 π0 i ( k) 的当前完工时间 Cπ0 i ( k) 和拖期 Tπ0 i ( k) ，其中 πi ( |πi | ) 为机器 i 上最新被接受的订单编号． 显然若 订单 π0 i ( k) 被接受，则其紧前订单为 πi ( |πi | ) ． Cπ0 i ( k) = Cπi ( |πi|) + si，πi ( |πi|) ，π0 i ( k) + pi，π0 i ( k) ， if πi≠ pi，π0 i { ( k) ， otherwise ( 13) Tπ0 i ( k) = max { Cπ0 i ( k) － dπ0 i ( k) ，0} ( 14) 根据定理 1，本节提出了订单拒绝规则 Ｒule1． Ｒule 1． 若 rejπ0 i ( k) ≤wπ0 i ( k) Tπ0 i ( k) ，并且以下情况 之一成立，则拒绝订单 π0 i ( k) : ( a) πi = ; ( b) k = | π0 i | ; ( c) Δk = piπ0 i ( k) + ( si，πi ( | πi| ) ，π0 i ( k) + siπ0 i ( k) π0 i ( k + 1) － siπi ( | πi| ) π0 i ( k + 1) ) ≥0 根据定理 1 可知，给定初始调度 Π0，采用基于 Ｒule1 的列表拒绝方法，得到的最终决策对〈ＲS，Π〉 的总成本必然不大于〈，Π0〉的总成本． 此外，根 · 135 ·

·532 工程科学学报，第41卷，第4期 据定理2可知，当Ⅱ满足min{pg}≥max{s}-2 工，则rej.因≥rej-f月=w,T”-rej≥-ej此外， jem jken min{s}（Hi)时，Rule1可简化为Rule2. min{p,}≥max{s}-2min{s}则有C≥C(l生 jkc j.ke i.key Rule2.若rejW≤0Tpw,则拒绝订单 RS),因此”≥综上，式(16)成立 π9(k. f(σ"-f(σ)=f(σ")-f(σ）+ rejr≥rej.w-rej≥0 (16) 定理3将证明，基于Rule2的列表拒绝方法在 一定情况下可以获得初始调度的最好解. 综上，任意对决策对RS,Ⅱ〉的调整均不会令 定理3.给定初始调度Ⅱo={π1Vi},其中π 总成本增加，因此〈RS,Ⅱ)是Ⅱo的最好解 (Vi)按订单拒绝成本非增排序.若L有min{pg}≥ 定理3说明基于Rule2的列表拒绝方法能够获 得某些初始调度的最好解.此外，即使对于一般问 max{s}-2min{st}(Hi),则采用基于Rule2的 j.kem j.kem 题，每次根据Rule2对一个订单进行拒绝决策后得 列表拒绝方法得到的决策对RS,Ⅱ)只要不存在拖 到的新局部解，显然其总成本的变动最小.这种策 期工件，就必然是Ⅱ。的最好解. 略在决策过程中不需要考虑其后的订单情况，不需 证明：若对RS,Ⅱ)的任意变动均不会导致总 要提前构造一个完整的调度方案，因而适合动态生 成本的增加，则定理得证.RS,Ⅱ)的任意变动均可 产环境以及采取顺序解码的群智能算法.本文将在 视为以下三种变动的组合：(1)拒绝一个调度订单； 算法中引入列表拒绝方法，并将Rule2作为订单拒 (2)接受一个拒绝订单；(3)拒绝一个调度订单的同 绝判定规则（见3.1节） 时接受一个拒绝订单.下面分别进行分析. (1)拒绝调度订单π：(k).令RS,Ⅱ〉表示得 3基于协同进化的遗传算法 到的新决策对.因为jRS有T,=0,所以f- 可加工机器限制会使调度解空间中存在不可行 f=ejm仙>0.此外，根据定理2可知，由于 解，如果算法在搜索过程中能够避开不可行解，则可 min{p,}≥max{s}-2min{s},拒绝订单π：(k) 以有效提高求解效率.遗传算法(genetic algorithm, jem j.kem jkem 不会推迟其他接受订单的完工时间，因此HjRS GA)具有快速求解能力，且能够通过合理的染色体 有T=T=0.综上，F-F=rej>0. 编码和遗传算子，灵活限定搜索空间.另外，协同进 化是面向群智能算法的优化策略，能够有效解决多 (2)接受拒绝订单j(U∈RS).令RS",")表 决策的联合优化问题，现已成功应用于遗传算法、粒 示得到的新决策对，对应的总成本为F”.不失一般 性，假设根据Ⅱ。的订单序列，订单j应插入当前序 子群算法、蜂群算法等.本节将设计协同进化 列π：的位置k上.由于列表拒绝方法是按订单在 遗传算法(cooperatively coevolving GA,CCGA),根 据约束特征设计编码解码方案和遗传算子，提高搜 π中的顺序依次执行的，因而有心，T≥rej,进而 索的有效性 f此外，若k=1或k=1m:1+1,有C"≥C,(Hl庄 3.1编码与解码方案 RS):若1<k≤1T:I,式(15)成立.因此，也满足 在遗传算法中，染色体的编码设计是问题相关 C≥C,(HlRS).综上，有T≥T,(HlRS),进而 的，且遗传算子的设计依赖于编码结构.对于订单 有F"≥F. 接受与并行机调度问题，若将订单拒绝决策设置为 （P与+smk-1+sm,份）-5海-Dm国≥ 染色体的一部分，则其决策具有随机性，无法保证解 min{p时}+2min{st}-max{st}≥0(15) jkem j.ken 的质量（本文的数据实验也对这一结论进行了验 (3)拒绝一个调度订单的同时接受一个拒绝订 证).因此，CCGA没有采用这一思路，而是基于上 单.不失一般性，首先拒绝决策对RS,Ⅱ〉的订单 述对订单拒绝策略的分析，用染色体表示初始调度 π：(k),得到新决策对RS,Ⅱ〉，此时有F=F+ 方案，在对该调度的解码过程中，采用基于Rule2的 r©jm,仙·进而，接受订单j(eRS),进一步得到新决 列表拒绝方法来依次确定订单的接受状态 策对RS”,T").若jπ，如情况(2)所示，有F"≥ 并行机调度由机器指派方案和订单排序方案共 F>F:否则，记订单j插入到π：的位置为k,则存 同构成，因此，本文将染色体分解为两个个体X和 在两种情况：k≤k或k>k:①当k≤k,即拒绝订单 Y.个体X={x1,…,xn}表示订单列表，其中基因x 位于订单j之后，则与情况(2)相似，有rej≤w,T, 表示第j个被调度的订单.个体Y={y1,,yn}表 F"≥F>F:②当k>k,即拒绝订单先于订单j加 示订单所指派的机器，且为了将CCGA的搜索空间

工程科学学报，第 41 卷，第 4 期 据定理 2 可知，当 Π0 满足min j∈π0 i { pij} ≥ max j，k∈π0 i { sijk } － 2 min j，k∈π0 i { sijk } ( i) 时，Ｒule1 可简化为 Ｒule2． Ｒule 2． 若 rejπ0 i ( k) ≤wπ0 i ( k) Tπ0 i ( k) ，则拒 绝 订 单 π0 i ( k) ． 定理 3 将证明，基于 Ｒule2 的列表拒绝方法在 一定情况下可以获得初始调度的最好解． 定理 3． 给定初始调度 Π0 = { π0 i | i} ，其中 π0 i ( i) 按订单拒绝成本非增排序． 若 Π0 有min j∈π0 i { pij} ≥ max j，k∈π0 i { sijk } － 2 min j，k∈π0 i { sijk } ( i) ，则采用基于 Ｒule2 的 列表拒绝方法得到的决策对〈ＲS，Π〉只要不存在拖 期工件，就必然是 Π0 的最好解． 证明: 若对〈ＲS，Π〉的任意变动均不会导致总 成本的增加，则定理得证． 〈ＲS，Π〉的任意变动均可 视为以下三种变动的组合: ( 1) 拒绝一个调度订单; ( 2) 接受一个拒绝订单; ( 3) 拒绝一个调度订单的同 时接受一个拒绝订单． 下面分别进行分析． ( 1) 拒绝调度订单 πi ( k) ． 令〈ＲS'，Π'〉表示得 到的新决策对． 因为jＲS 有 Tj = 0，所以 f'πi ( k) － fπi ( k) = rejπi ( k) ＞ 0． 此外，根 据 定 理 2 可 知，由 于 min j∈π0 i { pij} ≥ max j，k∈π0 i { sijk } － 2 min j，k∈π0 i { sijk } ，拒绝订单 πi ( k) 不会推迟其他接受订单的完工时间，因此jＲS' 有 T'j = Tj = 0． 综上，F' － F = rejπi ( k) ＞ 0． ( 2) 接受拒绝订单 j ( j∈ＲS) ． 令〈ＲS″，Π″〉表 示得到的新决策对，对应的总成本为 F″． 不失一般 性，假设根据 Π0 的订单序列，订单 j 应插入当前序 列 πi 的位置 k 上． 由于列表拒绝方法是按订单在 π0 i 中的顺序依次执行的，因而有 wj T″j ≥rejj ，进而 f″j≥fj ． 此外，若 k = 1 或 k = |πi | + 1，有 C″l≥Cl ( l ＲS) ; 若 1 ＜ k≤ | πi |，式( 15) 成立． 因此，也满足 C″l≥Cl ( lＲS) ． 综上，有 T″l≥Tl ( lＲS) ，进而 有F″≥F． ( pij + siπi ( k － 1) j + sijπi ( k) ) － siπi ( k － 1) πi ( k) ≥ min j∈π0 i { pij} + 2 min j，k∈π0 i { sijk } － max j，k∈π0 i { sijk } ≥0 ( 15) ( 3) 拒绝一个调度订单的同时接受一个拒绝订 单． 不失一般性，首先拒绝决策对〈ＲS，Π〉的订单 πi ( k) ，得到新决策对〈ＲS'，Π'〉，此时有 F' = F + rejπi ( k) ． 进而，接受订单 j ( j∈ＲS) ，进一步得到新决 策对〈ＲS″，Π″〉． 若 jπ0 i ，如情况( 2) 所示，有 F″≥ F' ＞ F; 否则，记订单 j 插入到 πi 的位置为 k'，则存 在两种情况: k'≤k 或 k' ＞ k: ①当 k'≤k，即拒绝订单 位于订单 j 之后，则与情况( 2) 相似，有 rejj≤wj T″j ， F″≥F' ＞ F; ②当 k' ＞ k，即拒绝订单先于订单 j 加 工，则 rejπi ( k) ≥rejj ，f″j － f'j = wj T″ － rejj≥ － rejj ． 此外， min j∈π0 i { pij} ≥max j，k∈π0 i { sijk } － 2 min j，k∈π0 i { sijk } 则有 C″l≥C'l ( l ＲS') ，因此 f″l≥f'l ． 综上，式( 16) 成立． f( σ″) － f( σ) = f( σ″) － f( σ') + rejπi ( k) ≥rejπi ( k) － rejj≥0 ( 16) 综上，任意对决策对〈ＲS，Π〉的调整均不会令 总成本增加，因此，〈ＲS，Π〉是 Π0 的最好解． 定理 3 说明基于 Ｒule2 的列表拒绝方法能够获 得某些初始调度的最好解． 此外，即使对于一般问 题，每次根据 Ｒule2 对一个订单进行拒绝决策后得 到的新局部解，显然其总成本的变动最小． 这种策 略在决策过程中不需要考虑其后的订单情况，不需 要提前构造一个完整的调度方案，因而适合动态生 产环境以及采取顺序解码的群智能算法． 本文将在 算法中引入列表拒绝方法，并将 Ｒule2 作为订单拒 绝判定规则( 见 3. 1 节) ． 3 基于协同进化的遗传算法 可加工机器限制会使调度解空间中存在不可行 解，如果算法在搜索过程中能够避开不可行解，则可 以有效提高求解效率． 遗传算法( genetic algorithm， GA) 具有快速求解能力，且能够通过合理的染色体 编码和遗传算子，灵活限定搜索空间． 另外，协同进 化是面向群智能算法的优化策略，能够有效解决多 决策的联合优化问题，现已成功应用于遗传算法、粒 子群算法、蜂群算法等［13--15］． 本节将设计协同进化 遗传算法( cooperatively coevolving GA，CCGA) ，根 据约束特征设计编码解码方案和遗传算子，提高搜 索的有效性． 3. 1 编码与解码方案 在遗传算法中，染色体的编码设计是问题相关 的，且遗传算子的设计依赖于编码结构． 对于订单 接受与并行机调度问题，若将订单拒绝决策设置为 染色体的一部分，则其决策具有随机性，无法保证解 的质量( 本文的数据实验也对这一结论进行了验 证) ． 因此，CCGA 没有采用这一思路，而是基于上 述对订单拒绝策略的分析，用染色体表示初始调度 方案，在对该调度的解码过程中，采用基于 Ｒule2 的 列表拒绝方法来依次确定订单的接受状态． 并行机调度由机器指派方案和订单排序方案共 同构成，因此，本文将染色体分解为两个个体 X 和 Y． 个体 X = { x1，…，xn } 表示订单列表，其中基因 xj 表示第 j 个被调度的订单． 个体 Y = { y1，…，yn } 表 示订单所指派的机器，且为了将 CCGA 的搜索空间 · 235 ·