工程科学学报，第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 algorithm ( CCGA) was developed． In this CCGA，an encoding scheme was proposed that divides chromosomes into two subsets corresponding 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 efficiency 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 algorithm; cooperative coevolution 订单接受作为订单管理的一项关键决策，不仅 决定了后续的生产作业，而且对企业的盈利能力以 及客户关系的维持具有直接影响． 传统的订单接受 决策是基于车间生产能力来决定的，但在面向订单 生产的现代制造业，多品种生产成为常态，机器环境 和工艺约束复杂，这种方法会与实际生产存在偏差， 造成计划外的生产成本和拖期罚金． 为解决这一问 题，研究者们将订单接受与订单调度进行联合决策， 提出了订单接受与调度问题． 在此问题中，如果订 单被拒绝，则产生订单拒绝成本，该成本一般为损失 的收益或外包成本; 如果订单被接受，则要求给出调 度方案，优化拖期惩罚费用( 即拖期成本) ． 由于订 单层面的调度为指导性的粗调度，因而此类研究一 般将车间或生产线抽象为传统调度问题中的机器 ( 以下统称为机器) ，将订单抽象为工件( 以下统称 为订单) ． 此外，由于定制生产的要求，如冰箱制造 等多品种混合生产模式多具有以下特征: ①可加工 机器限制: 车间设置若干并行机( 并行生产线) ，每 台机器只能生产有限种类的产品，且机器的产品集 合存在交叉，例如冰箱门体预装车间经常并存以下 三种产线: 仅支持玻璃材质、仅支持钣金材质和同时 支持两种材质的预装发泡产线; ②不相关并行机环 境: 由于机器所采用的技术有所区别，同一个产品在 不同机器上的加工时间不同; ③顺序与机器依赖的 安装时间: 由于技术差别，机器因切换工件而产生的 安装时间不仅同工件顺序相关，也同机器相关． 本 文针对上述特征，研究不相关并行机环境下具有安 装时间和可加工机器限制的订单接受与调度问题， 优化目标为最小化拒绝成本和拖期成本总和． 从订单拒绝角度考虑的订单接受与调度问题也 称为考虑拒绝的调度( scheduling with rejection) ，文 献［1--2］对该问题进行了详尽的综述． 目前，不相 关并行机的订单接受与调度问题研究较少，主要成 果如下: Angel 等［3］以最小化最大完工时间( makespan) 和订单总拒绝成本之和为目标，提出了一种完 全多项 式 时 间 近 似 方 案( fully polynomial time approximation scheme，FPTAS) ; Hoogeveen 等［4］进一步 考虑了工件允许中断的情况，证明了问题是非确定 性多项式复杂程度 ( non-deterministic polynomial， NP) 难的，且若机器数可变则为强 NP 难; Sengupta［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 linear 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):若1F:否则，记订单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 ·
王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·533· 限定在可加工机器范围内，令y,对应订单j而不是 输出决策对RS,{π：IHi}） 订单x,且y的值域为0,1M门而不是可加工机器 此编码和解码方案具有以下优点：首先，保证了 集合M,即y,表示订单j被指派到可加工机器集合 个体X和Y的独立性：此外，将算法的搜索空间限 M的第y台机器上 定在可行解范围内，这样可以简化遗传算子的设计， 下面举例说明此编码方案.考虑5个工件、3台 从3.3节可以看出，在此编码下，采用最基本的遗传 机器的实例，其中M1={1,2},M2={1,3},M3= 算子即可保证子代个体的合法性. {1,2,3},M4={2,3},M={2}.给定染色体编码 3.2协同进化策略 X,Y],其中X=B4215],Y=21321].根据个体 协同进化策略能够有效解决多决策的联合优化 X,首先调度订单3(x1=3),将其指派到机器3(M3 问题.如果一个问题能够拆分成关联性不强的多个 (y3)=3);此后，订单4(x2=4)指派到机器3(M4 子问题，则可以采用基于协同进化的群智能算法，独 (y)=3),紧随订单3加工；订单2和订单1依次被 立地对每个子问题进行进化操作，然后综合各个子 指派到机器1和机器2；订单5指派到机器2且紧随 问题的解来进行评价和选择.在本文的CCGA编码 订单1加工.因此，初始调度为Ⅱ。={，π，π}= 方案中，个体X和Y是彼此独立的，分别对应着订 {J2},{J1,J},{J3,J}}. 单排序决策和订单指派决策，且任意的X和Y均可 在CCGA中，订单拒绝决策是基于初始调度制 组合成一个可行的调度方案.这一特征符合协同进 定的，解码过程的伪代码如下，其中循环语句的单次 化的应用场景.此外，个体X和Y具有不同的进化 耗时0(1)，共循环n次，复杂度为0(n). 要求：个体X是一个订单序列，要求每个基因的取 Decoding() 值都不同：个体Y允许基因间取值重复，但每个基 Iput:染色体K,Y]: 因的值域不同.因此，对个体X和Y分别设计遗传 π：=☑，Hi;Rs=0: 算子并令其独自进化，这种方式比执行统一的遗传 For u=1 to n do 进化操作更为有效. j=x:i=M(y) 因此，本文将协同进化引入算法，基本思路如 f(π：=O)Then C=Pg' 下：依次进化由个体X和Y组成的两个种群（分别 Else C=C()+Sim(I+Pii 记为popx和pop:在每次迭代中，首先进化popx, T;=max (C:-d,0} 将其中个体与po即y中的最优个体进行组合，通过评 If (rej,<T)Then RS=RSU), 价和选择得到新种群popx;进而采用相同的方法进 Elseπ：=π：U{U};/Rule2 化popy令off,和of,表示popx和popy的子代种 End For 群，ps表示种群规模，则CCGA的求解框架如图1 生成初始种群pOP pop,,确定最好个体X,Y门 进化集合X 进化集合Y 调用集合X的遗传算子， 调用集合的遗传算子 进化popr,得到of, 进化pop,得到o, 构造2s个染色体X,门 构造2ps个染色体X",了 VXE pop,U offy VYepop,Uoffy 中 对2ps个染色体解码并评价 对2ps个染色体解码并评价 选择Ts个集合X,构成新的 选择ps个集合Y,构成新的 种群popx,更新X 种群popy,更新Y” 否 满足终止准则 是 输出染色体X,Y门 图1CCGA的协同进化求解框架 Fig.1 Cooperative coevolution in CCGA
王柏琳等: 安装时间和机器受限的订单接受与并行机调度 限定在可加工机器范围内，令 yj 对应订单 j 而不是 订单 xj ，且 yj 的值域为［1，| Mj |］而不是可加工机器 集合 Mj ，即 yj 表示订单 j 被指派到可加工机器集合 Mj 的第 yj 台机器上． 下面举例说明此编码方案． 考虑 5 个工件、3 台 机器的实例，其中 M1 = { 1，2} ，M2 = { 1，3} ，M3 = { 1，2，3} ，M4 = { 2，3} ，M5 = { 2} ． 给定染色体编码 ［X，Y］，其中 X =［34215］，Y =［21321］． 根据个体 X，首先调度订单 3( x1 = 3) ，将其指派到机器 3( M3 ( y3 ) = 3) ; 此后，订单 4( x2 = 4) 指派到机器 3 ( M4 ( y4 ) = 3) ，紧随订单 3 加工; 订单 2 和订单 1 依次被 指派到机器1 和机器2; 订单5 指派到机器2 且紧随 订单1 加工． 因此，初始调度为 Π0 = { π0 1，π0 2，π0 3 } = { { J2 } ，{ J1，J5 } ，{ J3，J4 } } ． 在 CCGA 中，订单拒绝决策是基于初始调度制 定的，解码过程的伪代码如下，其中循环语句的单次 耗时 O( 1) ，共循环 n 次，复杂度为 O( n) ． 图 1 CCGA 的协同进化求解框架 Fig． 1 Cooperative coevolution in CCGA Decoding( ) Input: 染色体［X，Y］; πi = ，i; ＲS = ; For u = 1 to n do j = xu ; i = Mj ( yj ) ; If ( πi = ) Then Cj = pij， Else Cj = Cπi ( | πi| ) + siπi ( | πi| ) j + pij; Tj = max { Cj － dj ，0} ; If ( rejj≤Tj ) Then ＲS = ＲS∪{ j} ， Else πi = πi∪{ j} ; / /Ｒule 2 End For 输出决策对〈ＲS，{ πi |i} 〉 此编码和解码方案具有以下优点: 首先，保证了 个体 X 和 Y 的独立性; 此外，将算法的搜索空间限 定在可行解范围内，这样可以简化遗传算子的设计， 从 3. 3 节可以看出，在此编码下，采用最基本的遗传 算子即可保证子代个体的合法性． 3. 2 协同进化策略 协同进化策略能够有效解决多决策的联合优化 问题． 如果一个问题能够拆分成关联性不强的多个 子问题，则可以采用基于协同进化的群智能算法，独 立地对每个子问题进行进化操作，然后综合各个子 问题的解来进行评价和选择． 在本文的 CCGA 编码 方案中，个体 X 和 Y 是彼此独立的，分别对应着订 单排序决策和订单指派决策，且任意的 X 和 Y 均可 组合成一个可行的调度方案． 这一特征符合协同进 化的应用场景． 此外，个体 X 和 Y 具有不同的进化 要求: 个体 X 是一个订单序列，要求每个基因的取 值都不同; 个体 Y 允许基因间取值重复，但每个基 因的值域不同． 因此，对个体 X 和 Y 分别设计遗传 算子并令其独自进化，这种方式比执行统一的遗传 进化操作更为有效． 因此，本文将协同进化引入算法，基本思路如 下: 依次进化由个体 X 和 Y 组成的两个种群( 分别 记为 popX 和 popY ． 在每次迭代中，首先进化 popX， 将其中个体与 popY 中的最优个体进行组合，通过评 价和选择得到新种群 popX ; 进而采用相同的方法进 化 popY ． 令 offX 和 offY 表示 popX 和 popY 的子代种 群，ps 表示种群规模，则 CCGA 的求解框架如图 1 · 335 ·
·534 工程科学学报，第41卷，第4期 所示. 然而，单亲遗传算子并不适合个体Y.个体Y 3.3遗传算子设计 的每个基因都有其特定值域，而单亲遗传算子通过 在CCGA中，个体X和Y具有不同的约束特 更改基因位置来实现进化，很容易使子代的基因超 征，因此本文分别为其设计遗传算子 出值域.个体Y因基因值域受限而具有以下特征. 个体X为置换序列，要求基因的值各不相同， 特征1.若个体Y,和Y2可行，那么交换Y,和Y2 而传统的交叉和变异算子容易产生基因取值重复的 相同基因位置上的值，得到的子代个体均可行 非法解.李茂军与童调生6为解决这一问题，提出 根据此特征，采用最基本的GA交叉算子就可 了单亲遗传算法(partheno-genetic algorithm,PGA). 以得到合法子代.此外，对于变异算子，也仅需要将 PGA是GA的改进算法Dm,采用基因重组算子来代 基因y:的变异范围限定在，1M,I门即可，无需搜索 替交叉算子，每个子代个体仅对应一个父代，通过改 订单j的可加工机器集合.因此，CCGA采用传统 变父代中基因的位置而非基因值来生成子代，因而 GA的交叉和变异算子来进化个体Y,分别命名为 对于置换序列编码的染色体能够保证遗传个体的合 Y_Crossover()和Y_Mutation().其中，交叉算子交 法性.经典的基因重组算子有三类：移位算子、换位 换两个父代指定基因位置集合上的值，最坏情况下 算子和倒位算子，分别等同于插入邻域、交换邻域和 的时间复杂度为O(n):变异算子随机改变一个基 逆序邻域，易见其复杂度分别为0(n)、0(1)和 因值，复杂度为0(1).因此，个体Y的遗传操作复 O(n).CCGA采用这三种算子来进化popr,分别命 杂度为0(n),且能够确保of,的可行性. 名为X_Shif()、X_Exchange()和X_Inverse(),其整 图2以3.1节的例子为例，给出了上述5种遗 体复杂度为0(n),且能够确保of,的可行性. 传算子的示意图. 个体X的单亲遗传算子 个体Y的传统遗传算子 父代个体 子代个体 父代个体 子代个体 34215◆32154 (a)X_Shift(:s =2.s,=5 213212221▣ :待插人基因； :插人位置 1221四32▣ 34215→35214 (a)Y_Crossover(:c,=2,c=4 (b)X_Exchange(:e,=2.e,=5 %2:待交换的基因位 ?,C:交叉操作基因组的首尾基因位 34215=35124 21321-2112 (c)X_Inverse(:r=2.r,=5 (b)Y_Mutation(:m,=3 「：逆序操作基因组的首尾基因位 m:待变异的基因位 图2CCCA遗传算子示意图 Fig.2 Genetic operators of CCGA 3.4CCGA算法步骤 令XAr=popx Uoffx; 在CCGA中，初始种群随机生成，适应度函数采 Forx=1to2ps:调用Decoding()解码染色体 用总成本目标函数，选择算子采用两两锦标赛方法， [XArr(x),Y ] 算法终止准则为最大进化代数mxGen.CCGA的伪 采用两两锦标赛方法选择s个个体X,将其 代码如下 作为新种群，更新poPr; 111.初始化 将X更新为popx中的最优个体X; 随机生成ps个染色体，将其分解为popx和 I12.2采用GA遗传算子进化popy popy: 调用Y_Crossover(),Y_Mutation()生成ofy; 对每个染色体调用Decoding()来进行解码；记 令YAr=poPyUoff,: 录最优染色体，Y]: Fory=1to2ps:调用Decoding()解码染色体 112.遗传进化 X,YAr(y）]; For t=1 to mxGen do 采用两两锦标赛方法选择Ps个个体Y,将其 /12.1采用PGA单亲遗传算子进化popx 作为新种群，更新poPy; 调用X_Shift(),X_Exchange(),X_nverse() 将Y更新为popy中的最优个体Y; 生成ofx; End For
工程科学学报，第 41 卷，第 4 期 所示． 3. 3 遗传算子设计 在 CCGA 中，个体 X 和 Y 具有不同的约束特 征，因此本文分别为其设计遗传算子． 个体 X 为置换序列，要求基因的值各不相同， 而传统的交叉和变异算子容易产生基因取值重复的 非法解． 李茂军与童调生［16］为解决这一问题，提出 了单亲遗传算法( partheno-genetic algorithm，PGA) ． PGA 是 GA 的改进算法［17］，采用基因重组算子来代 替交叉算子，每个子代个体仅对应一个父代，通过改 变父代中基因的位置而非基因值来生成子代，因而 对于置换序列编码的染色体能够保证遗传个体的合 法性． 经典的基因重组算子有三类: 移位算子、换位 算子和倒位算子，分别等同于插入邻域、交换邻域和 逆序邻域，易见其复杂度分别为 O( n) 、O( 1 ) 和 O( n) ． CCGA 采用这三种算子来进化 popX，分别命 名为 X_Shift( ) 、X_Exchange( ) 和 X_Inverse( ) ，其整 体复杂度为 O( n) ，且能够确保 offX 的可行性． 然而，单亲遗传算子并不适合个体 Y． 个体 Y 的每个基因都有其特定值域，而单亲遗传算子通过 更改基因位置来实现进化，很容易使子代的基因超 出值域． 个体 Y 因基因值域受限而具有以下特征． 特征 1． 若个体 Y1和 Y2可行，那么交换 Y1和 Y2 相同基因位置上的值，得到的子代个体均可行． 根据此特征，采用最基本的 GA 交叉算子就可 以得到合法子代． 此外，对于变异算子，也仅需要将 基因 yj 的变异范围限定在［1，| Mj |］即可，无需搜索 订单 j 的可加工机器集合． 因此，CCGA 采用传统 GA 的交叉和变异算子来进化个体 Y，分别命名为 Y_Crossover( ) 和 Y_Mutation( ) ． 其中，交叉算子交 换两个父代指定基因位置集合上的值，最坏情况下 的时间复杂度为 O( n) ; 变异算子随机改变一个基 因值，复杂度为 O( 1) ． 因此，个体 Y 的遗传操作复 杂度为 O( n) ，且能够确保 offY 的可行性． 图 2 以 3. 1 节的例子为例，给出了上述 5 种遗 传算子的示意图． 图 2 CCGA 遗传算子示意图 Fig． 2 Genetic operators of CCGA 3. 4 CCGA 算法步骤 在 CCGA 中，初始种群随机生成，适应度函数采 用总成本目标函数，选择算子采用两两锦标赛方法， 算法终止准则为最大进化代数 mxGen． CCGA 的伪 代码如下． / /1. 初始化 随机生 成 ps 个 染 色 体，将 其 分 解 为 popX 和 popY ; 对每个染色体调用 Decoding( ) 来进行解码; 记 录最优染色体［X* ，Y* ］; / /2. 遗传进化 For t = 1 to mxGen do / /2. 1 采用 PGA 单亲遗传算子进化 popX 调用 X_Shift( ) ，X_Exchange( ) ，X_Inverse( ) 生成 offX ; 令 XArr = popX∪offX ; For x = 1 to 2ps: 调用 Decoding( ) 解码染色体 ［XArr( x) ，Y* ］; 采用两两锦标赛方法选择 ps 个个体 X，将其 作为新种群，更新 popX ; 将 X* 更新为 popX 中的最优个体 X; / / 2. 2 采用 GA 遗传算子进化 popY 调用 Y_Crossover( ) ，Y_Mutation( ) 生成 offY ; 令 YArr = popY∪offY ; For y = 1 to 2ps: 调用 Decoding( ) 解码染色体 ［X* ，YArr( y) ］; 采用两两锦标赛方法选择 ps 个个体 Y，将其 作为新种群，更新 popY ; 将 Y* 更新为 popY 中的最优个体 Y; End For · 435 ·
王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·535· 输出染色体☒，Y]的拒绝订单集合和调度 散均匀分布；安装时间s海∈DU几0,20]；订单拒绝 方案 成本rej∈DU1,10];单位拖期成本e:∈U0.5, 1.5],交货期d,∈DU50,50n/(m+1)]. 4数据实验 算法参数设置如下：GADR采用Joo和Kimo 4.1实验环境设置 的实验参数，即交叉和变异概率分别为0.8和0.2， 为了检验模型的正确性以及算法的有效性，本 种群规模ps=2n,最大代数mxGen=1000.对于 节首先针对较小问题规模的算例进行实验，通过 CCGA、CCGAⅡ和TGA,考虑到插入邻域和交换邻 IBM公司的CPLEX数学规划软件对数学模型求解， 域是调度算法中被广泛应用且十分有效的两种邻域 并将CCGA取得的解与最优解进行比较；进而，为了 结构，且二者优化效果相近8-9，因此在进化个体 检验CCGA算法及其协同进化策略和列表拒绝方法 X时移位和换位概率设置为相等且相对较高的值， 的有效性，针对问题规模较大的算例进行实验，并设 均为0.4，而基于逆序邻域的倒位概率则设为相对 置了如下三个对比算法： 较低的值，为0.2：进化个体Y时，参考GADR的参 (1)由Joo和Kima提出的基于指派规则的遗 数设置，交叉和变异概率分别为0.8和0.2.考虑到 传算法GADR_PO(这里简称为GADR),用来解 TGA和GADR均未采用协同进化，因此TGA种群规 决引言部分提到的本文特例问题，即考虑安装时间 模ps和最大代数mxGen与GADR相同，采用协同 和可加工机器限制的不相关并行机调度.此处将第 进化的CCGA和CCGAII的ps和mxGen减半：ps= 三个对比算法所采用的订单拒绝方法（详见(3）)引 n,mxGen =500. 入GADR 4.2小规模算例的实验检验 (2)未采用协同进化策略的传统遗传算法(tra- 本节将检验本文提出的数学模型的可行性，并 ditional GA,TGA).TGA将X和Y作为一条染色体 观察CCGA算法相对于最优值的偏差情况.考虑到 同时进化，其编码方案、遗传算子和选择算子均与 精确算法适用于问题规模较小的算例，因此本节的 CCGA相同.TGA用来检验CCGA协同进化策略的 实验对象为小规模算例，具体设置如下：机器数m= 有效性. 2,3,4,订单数n=m,其中倍数t=2,3,4.根据 (3)一种协同进化遗传算法，与CCGA的区别 问题规模分为9组实验，每组随机生成10个算例， 在于，此算法用染色体编码来表示订单拒绝决策，而 共计90个算例.数学模型采用CPLEX数学规划软 没有采用列表拒绝方法，将其记为CCGAI.为提高 件，在.NET环境下用C#语言编写；CCGA算法采用 计算效率，CCGAⅡ不另设染色体子集来表示订单拒 C#语言编写.运行环境为ntel Core5-6300U/ 绝变量，而是参考Shabtay等回提出的方法，将个体 CPU2.40GHz and RAM 8.0G. Y的基因y（j)值域由1，IMI]扩展为O, 实验结果见表I,其中Avg.表示该组实验的成 IM,I],若y=0则说明订单j被拒绝。CCGAII用来 本均值，Time表示平均计算时间，Opt.表示CCGA 检验CCGA列表拒绝方法的有效性. 算法取得最优值的比例（即取得最优值的算例数/ 在以上两组实验中，算例参数均设置为：订单j 该组实验算例总数) 的加工时间上下限为p∈DU2,99]和p∈DU 由表1看出，CCGA共有80%的算例取得了最 几，Lp,2],在机器i上的加工时间为P∈DU 优值，即最小的总成本，其中有两组实验取得最优值 p,,P],其中DUa,b]表示位于[a,b]区间的离 的算例的比例高达1O0%;此外，CCGA的总成本均 表1 CPLEX与CCGA的实验结果 Table 1 Experimental results for CPLEX and CCGA CPLEX CCGA CPLEX CCGA t(n) t(n) Avg. Time/s Avg. 0pt./% Time/s Avg. Time/s Avg. 0pt./% Time/s 22(4) 0 0.072 0.9 70 0.022 34(12) 0.8 0.106 1.6 80 0.077 3(6) 0.7 0.069 2.1 60 0.036 4 2(8) 2.1 0.086 2.1 100 0.055 4(8) 0.8 0.084 2.8 70 0.048 3(12) 1.6 0.106 1.6 100 0.081 32(6) 0 0.069 0.5 80 0.036 4(16) 0.8 0.220 3.2 70 0.109 3(9) 0.1 0.077 0.8 90 0.056 平均值 0.77 0.099 1.73 80 0.058
王柏琳等: 安装时间和机器受限的订单接受与并行机调度 输出染色体［X* ，Y* ］的拒绝订单集合和调度 方案 4 数据实验 4. 1 实验环境设置 为了检验模型的正确性以及算法的有效性，本 节首先针对较小问题规模的算例进行实验，通过 IBM 公司的 CPLEX 数学规划软件对数学模型求解， 并将 CCGA 取得的解与最优解进行比较; 进而，为了 检验 CCGA 算法及其协同进化策略和列表拒绝方法 的有效性，针对问题规模较大的算例进行实验，并设 置了如下三个对比算法: ( 1) 由 Joo 和 Kim［10］提出的基于指派规则的遗 传算法 GA_DＲ_P［10］( 这里简称为 GADＲ) ，用来解 决引言部分提到的本文特例问题，即考虑安装时间 和可加工机器限制的不相关并行机调度． 此处将第 三个对比算法所采用的订单拒绝方法( 详见( 3) ) 引 入 GADＲ． ( 2) 未采用协同进化策略的传统遗传算法( traditional GA，TGA) ． TGA 将 X 和 Y 作为一条染色体 同时进化，其编码方案、遗传算子和选择算子均与 CCGA 相同． TGA 用来检验 CCGA 协同进化策略的 有效性． ( 3) 一种协同进化遗传算法，与 CCGA 的区别 在于，此算法用染色体编码来表示订单拒绝决策，而 没有采用列表拒绝方法，将其记为 CCGAII． 为提高 计算效率，CCGAII 不另设染色体子集来表示订单拒 绝变量，而是参考 Shabtay 等［2］提出的方法，将个体 Y 的 基 因 yj ( j) 值 域 由［1，| Mj |］扩 展 为［0， | Mj |］，若 yj = 0 则说明订单 j 被拒绝． CCGAII 用来 检验 CCGA 列表拒绝方法的有效性． 在以上两组实验中，算例参数均设置为: 订单 j 的加工时间上下限为 p + j ∈DU［2，99］和 p － j ∈DU ［1，? p + j /2」］，在机器 i 上的加工时 间 为 pij ∈DU ［p － j ，p + j ］，其中 DU［a，b］表示位于［a，b］区间的离 散均匀分布; 安装时间 sikj∈DU［10，20］; 订单拒绝 成本 rejj∈DU［1，10］; 单位拖期成本 wj ∈U［0. 5， 1. 5］，交货期 dj∈DU［50，50n /( m + 1) ］． 算法参数设置如下: GADＲ 采用 Joo 和 Kim［10］ 的实验参数，即交叉和变异概率分别为 0. 8 和 0. 2， 种群规模 ps = 2n，最大代数 mxGen = 1000． 对于 CCGA、CCGAII 和 TGA，考虑到插入邻域和交换邻 域是调度算法中被广泛应用且十分有效的两种邻域 结构，且二者优化效果相近［18--19］，因此在进化个体 X 时移位和换位概率设置为相等且相对较高的值， 均为 0. 4，而基于逆序邻域的倒位概率则设为相对 较低的值，为 0. 2; 进化个体 Y 时，参考 GADＲ 的参 数设置，交叉和变异概率分别为 0. 8 和 0. 2． 考虑到 TGA 和 GADＲ 均未采用协同进化，因此 TGA 种群规 模 ps 和最大代数 mxGen 与 GADＲ 相同，采用协同 进化的 CCGA 和 CCGAII 的 ps 和 mxGen 减半: ps = n，mxGen = 500． 4. 2 小规模算例的实验检验 本节将检验本文提出的数学模型的可行性，并 观察 CCGA 算法相对于最优值的偏差情况． 考虑到 精确算法适用于问题规模较小的算例，因此本节的 实验对象为小规模算例，具体设置如下: 机器数 m = 2，3，4，订单数 n = tm，其中倍数 t = 2，3，4． 根据 问题规模分为 9 组实验，每组随机生成 10 个算例， 共计 90 个算例． 数学模型采用 CPLEX 数学规划软 件，在 . NET 环境下用 C#语言编写; CCGA 算法采用 C# 语 言 编 写． 运 行 环 境 为 Intel Core i5--6300U / CPU2. 40GHz and ＲAM 8. 0G． 实验结果见表 1，其中 Avg． 表示该组实验的成 本均值，Time 表示平均计算时间，Opt． 表示 CCGA 算法取得最优值的比例( 即取得最优值的算例数/ 该组实验算例总数) ． 由表 1 看出，CCGA 共有 80% 的算例取得了最 优值，即最小的总成本，其中有两组实验取得最优值 的算例的比例高达 100% ; 此外，CCGA 的总成本均 表 1 CPLEX 与 CCGA 的实验结果 Table 1 Experimental results for CPLEX and CCGA m t( n) CPLEX CCGA Avg． Time / s Avg． Opt． /% Time / s m t( n) CPLEX CCGA Avg． Time / s Avg． Opt． /% Time / s 2 2 ( 4) 0 0. 072 0. 9 70 0. 022 3 4 ( 12) 0. 8 0. 106 1. 6 80 0. 077 3 ( 6) 0. 7 0. 069 2. 1 60 0. 036 4 2 ( 8) 2. 1 0. 086 2. 1 100 0. 055 4 ( 8) 0. 8 0. 084 2. 8 70 0. 048 3 ( 12) 1. 6 0. 106 1. 6 100 0. 081 3 2 ( 6) 0 0. 069 0. 5 80 0. 036 4 ( 16) 0. 8 0. 220 3. 2 70 0. 109 3 ( 9) 0. 1 0. 077 0. 8 90 0. 056 平均值 0. 77 0. 099 1. 73 80 0. 058 · 535 ·
·536 工程科学学报，第41卷，第4期 值(1.73)仅比CPLEX的总成本均值(0.77)多不到 在有效性方面，表2给出了4个算法对20组实 一个成本单位.以上结果说明CCGA对求解小规模 验取得的总成本均值（Avg.)和标准差(Std.).此 实例是有效的.在计算时间方面，CCGA比CPLEX 外，我们采用方差分析(analysis of variance,.ANO- 少将近一倍，表明CCGA具有较好的求解效率 VA)对每组实验进行总成本均值差异性的显著性检 4.3大规模实验与结果分析 验，其中a=0.05,对应的F临界值为2.41.表2的 本小节主要针对问题规模较大的算例展开实 最后两列给出了每组实验的F值与P值，最后一行 验，检验CCGA算法在各种问题规模下的求解性能. 的最后两列为所有1000个算例下总成本均值的F 算例的问题规模设置如下：订单数n=20,50,100, 值和P值.表3给出了4个算法在每组取得零成本 150,200:机器数m=2,5,10,15,20.其中，订单 最优值的算例数 数为20时机器数只考虑m=2,5:订单数为50时 表2表明，CCGA的总成本明显低于其他算法： 只考虑m=2,5,10.根据问题规模分为20组实 此外，每组实验进行ANOVA分析得到的P值均接 验，每组随机生成50个算例，共计1000个算例.本 近于0，明显小于α(0.05)，且随着n的增加，P值呈 小节的4种算法均采用C#语言编程，运行环境为 显著下降趋势，这说明算法间的求解质量存在显著 Intel Core i3-4020Y/CPU1.5 GHz and RAM 4.0 G. 差异，而且随着工件订单规模增加，差异愈加明显 算法性能从有效性和求解效率两方面衡量.有 另外，在表3中，25.5%的实例由CCGA取得了零成 效性以总成本为评价指标，求解效率以计算机中央 本，且对于规模组20X5/50X5/50X10/100X20,60% 处理器(central processing unit,CPU)的处理时间（简 以上的实例由CCGA取得了零成本，明显优于其他 称CPU时间)为指标. 算法.以上结果表明CCGA能够取得高质量的解. 表24种算法求解每组算例的总成本均值、标准差与ANOVA分析结果 Table 2 Means and standard deviations of the total costs obtained by the four algorithms CCCA CCGAI TGA GADR AN0VA(a=0.05) Avg. Std. Avg. Std. Avg. Std. Avg. Std. Palue 20 2.80 3.37 3.74 4.36 7.54 5.38 14.88 18.22 15.40 4.88×10-9 1.28 2.15 1.76 2.83 3.44 3.33 9.44 13.86 13.07 8.15×10-8 50 2 3.90 4.22 9.84 7.80 35.02 12.17 59.06 53.86 40.93 1.39×10-20 5 1.36 2.61 4.60 5.71 23.00 10.90 17.82 19.68 39.41 5.63×10-20 10 1.46 2.60 3.78 4.39 18.60 8.71 7.22 8.43 66.85 8.15×10-0 100 1016 97.54 16.84 275.28 137.86 150.81 1.13×10-0 5 15 77.04 15.05 72.12 55.02 75.72 1.44×10-2 10 6240 15.30 34.54 32.61 106.78 5.25×10-41 15 55.66 13.32 24.68 27.25 122.77 8.93×10-45 54.40 11.68 12.74 14.25 307.94 6.80×10-74 150 154.78 19.06 606.68 236.72 258.03 8.62×10-68 122.58 20.62 165.22 89.23 121.48 1.75×10-4 10 107.70 20.60 72.60 47.45 151.68 7.59×10-51 105.52 16.39 62.42 48.72 146.19 9.29×10-50 X XO 100.98 16.69 48.60 39.99 193.02 2.97x10-58 200 2 34.32 12. 107.68 24.49 224.46 26.05 1217.00 436.96 317.92 5.14×10-5 5 19.48 10.40 69.84 20.07 175.78 22.11 343.62 135.49 212.14 2.75×10-61 10 12.42 6.76 45.28 18.15 151.48 19.03 150.94 76.30 157.65 5.35×10-52 15 10.14 5.57 38.70 1485 150.72 19.74 121.56 77.50 133.52 3.90×10-47 20 4.78 4.48 23.82 10.77 135.92 20.03 77.06 46.06 261.06 3.45X10-68 平均值 7.80 5.32 26.74 11.05 93.23 15.65 169.67 80.77 218.11 4.9×10-131
工程科学学报，第 41 卷，第 4 期 值( 1. 73) 仅比 CPLEX 的总成本均值( 0. 77) 多不到 一个成本单位． 以上结果说明 CCGA 对求解小规模 实例是有效的． 在计算时间方面，CCGA 比 CPLEX 少将近一倍，表明 CCGA 具有较好的求解效率． 4. 3 大规模实验与结果分析 本小节主要针对问题规模较大的算例展开实 验，检验 CCGA 算法在各种问题规模下的求解性能． 算例的问题规模设置如下: 订单数 n = 20，50，100， 150，200; 机器数 m = 2，5，10，15，20． 其中，订单 数为 20 时机器数只考虑 m = 2，5; 订单数为 50 时 只考虑 m = 2，5，10． 根据问题规模分为 20 组实 验，每组随机生成 50 个算例，共计 1000 个算例． 本 小节的 4 种算法均采用 C #语言编程，运行环境为 Intel Core i3--4020Y / CPU1. 5 GHz and ＲAM 4. 0 G． 算法性能从有效性和求解效率两方面衡量． 有 效性以总成本为评价指标，求解效率以计算机中央 处理器( central processing unit，CPU) 的处理时间( 简 称 CPU 时间) 为指标． 在有效性方面，表 2 给出了 4 个算法对 20 组实 验取得的总成本均值( Avg． ) 和标准差( Std． ) ． 此 外，我们采用方差分析( analysis of variance，ANOVA) 对每组实验进行总成本均值差异性的显著性检 验，其中 α = 0. 05，对应的 F 临界值为 2. 41． 表 2 的 最后两列给出了每组实验的 F 值与 P 值，最后一行 的最后两列为所有 1000 个算例下总成本均值的 F 值和 P 值． 表 3 给出了 4 个算法在每组取得零成本 最优值的算例数． 表 2 表明，CCGA 的总成本明显低于其他算法; 此外，每组实验进行 ANOVA 分析得到的 P 值均接 近于 0，明显小于 α( 0. 05) ，且随着 n 的增加，P 值呈 显著下降趋势，这说明算法间的求解质量存在显著 差异，而且随着工件订单规模增加，差异愈加明显． 另外，在表 3 中，25. 5% 的实例由 CCGA 取得了零成 本，且对于规模组 20X5 /50X5 /50X10 /100X20，60% 以上的实例由 CCGA 取得了零成本，明显优于其他 算法． 以上结果表明 CCGA 能够取得高质量的解． 表 2 4 种算法求解每组算例的总成本均值、标准差与 ANOVA 分析结果 Table 2 Means and standard deviations of the total costs obtained by the four algorithms n m CCGA CCGAII TGA GADＲ ANOVA( α = 0. 05) Avg． Std． Avg． Std． Avg． Std． Avg． Std． F P-value 20 2 2. 80 3. 37 3. 74 4. 36 7. 54 5. 38 14. 88 18. 22 15. 40 4. 88 × 10 － 9 5 1. 28 2. 15 1. 76 2. 83 3. 44 3. 33 9. 44 13. 86 13. 07 8. 15 × 10 － 8 50 2 3. 90 4. 22 9. 84 7. 80 35. 02 12. 17 59. 06 53. 86 40. 93 1. 39 × 10 － 20 5 1. 36 2. 61 4. 60 5. 71 23. 00 10. 90 17. 82 19. 68 39. 41 5. 63 × 10 － 20 10 1. 46 2. 60 3. 78 4. 39 18. 60 8. 71 7. 22 8. 43 66. 85 8. 15 × 10 － 30 100 2 9. 36 5. 99 29. 04 10. 16 97. 54 16. 84 275. 28 137. 86 150. 81 1. 13 × 10 － 50 5 6. 38 5. 81 19. 98 11. 15 77. 04 15. 05 72. 12 55. 02 75. 72 1. 44 × 10 － 32 10 2. 28 2. 98 10. 16 8. 34 62. 40 15. 30 34. 54 32. 61 106. 78 5. 25 × 10 － 41 15 1. 46 2. 14 7. 04 6. 71 55. 66 13. 32 24. 68 27. 25 122. 77 8. 93 × 10 － 45 20 1. 14 1. 96 6. 02 6. 47 54. 40 11. 68 12. 74 14. 25 307. 94 6. 80 × 10 － 74 150 2 19. 76 10. 20 57. 96 16. 16 154. 78 19. 06 606. 68 236. 72 258. 03 8. 62 × 10 － 68 5 9. 30 7. 13 37. 68 15. 44 122. 58 20. 62 165. 22 89. 23 121. 48 1. 75 × 10 － 44 10 5. 20 4. 94 23. 54 12. 99 107. 70 20. 60 72. 60 47. 45 151. 68 7. 59 × 10 － 51 15 4. 78 5. 49 20. 46 11. 34 105. 52 16. 39 62. 42 48. 72 146. 19 9. 29 × 10 － 50 20 4. 40 4. 82 13. 86 8. 80 100. 98 16. 69 48. 60 39. 99 193. 02 2. 97 × 10 － 58 200 2 34. 32 12. 87 107. 68 24. 49 224. 46 26. 05 1217. 00 436. 96 317. 92 5. 14 × 10 － 75 5 19. 48 10. 40 69. 84 20. 07 175. 78 22. 11 343. 62 135. 49 212. 14 2. 75 × 10 － 61 10 12. 42 6. 76 45. 28 18. 15 151. 48 19. 03 150. 94 76. 30 157. 65 5. 35 × 10 － 52 15 10. 14 5. 57 38. 70 14. 85 150. 72 19. 74 121. 56 77. 50 133. 52 3. 90 × 10 － 47 20 4. 78 4. 48 23. 82 10. 77 135. 92 20. 03 77. 06 46. 06 261. 06 3. 45 × 10 － 68 平均值 7. 80 5. 32 26. 74 11. 05 93. 23 15. 65 169. 67 80. 77 218. 11 4. 9 × 10 － 131 · 635 ·
王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·537· 表34种算法生成零成本问题解的算例数量 Table 3 Number of solutions with zero total cost produced by the four algorithms CCGA TGA GADR CCGA CCGAII TGA GADR 30 2 20 19 ◇ 150 0 0 0 31 呼 14 分 5 0 0 0 2 14 0 10 0 1 31 23 0 15 0 0 2 33 20 22 12 0 0 3 100 2 0 0 0 200 2 0 0 0 1 0 0 0 0 10 3 10 0 0 0 0 15 24 11 0 12 15 0 0 0 20 32 , 20 9 0 0 总计 255 126 18 113 此外，表2中CCGA的标准差最小，说明CCGA的求 是有效的.②CCGAⅡ的平均总成本是CCGA的3.4 解性能相对稳定.进一步，由表2可以计算出 倍，这说明对于订单接受与调度，列表拒绝方法比嵌 CCGAII、TGA和GADR相对于CCGA的平均总成本 入染色体进化的拒绝决策更为有效 偏离率，分别为2.43、10.95和20.75，由此可得：① 表4给出了4种算法在求解规模组20X5、 基于协同进化的CCGA和CCGAII明显优于TGA和 100X10、200X20以及所有1000个实例的平均CPU GADR.在实验中，CCGA和CCGAII的种群规模和 时间，计算效率由高至低分别为CCGAII、CCGA、 进化代数仅为TGA和GADR的一半，却能显著超越 TGA、GADR,其中CCGAII和CCGA的计算时间非 后两种算法，这说明协同进化对于求解并行机调度 常相近. 表44种算法的CPU时间 Table 4 CPU times of the four algorithms CCGA CCGAII TGA GADR n m CCGA CCGAII TGA GADR 0.31 0.30 0.59 0.84 200 20 33.91 32.41 66.45 241.31 100 10 7.72 7.37 15.46 32.98 平均值 14.24 13.23 23.28 72.28 现对表4结果分析如下： GADR.这说明了CCGA的编码方案有效且遗传算 (1)CCGA计算时间略多于CCGAII,这是因为 子的计算效率较优. CCGA需要对订单逐一判定是否拒绝.但两个算法 下面对算法收敛性进行比较.图3给出了规模 的计算时间平均差值仅1.01s,说明列表拒绝方法 100X10的实例在迭代600代时的算法收敛曲线. 对计算时间的影响基本可以忽略 可以看出，基于列表拒绝方法的CCGA和TGA (2)TGA和GADR的计算时间明显慢于CCGA 能够得到相对较优的初始解.为便于进一步观察， 和CCGAI,这是由两倍的种群规模和进化代数所导 图4给出了CCGA和TGA的收敛曲线.在这4种算 致的.其中GADR的计算时间最长，这是因为 法中，CCGA最先在第241代找到了最优的零成本 GADR采用了单点交叉算子来生成合法的置换序 解，CCGAⅡ则在550代达到零成本.经进一步运行 列，进而采用指派规则为订单确定机器.单点交叉 算法发现，GADR和TGA在2OO0代时仍未取得零 算子需要搜索一个父代在交叉点后的每个等位基因 成本，最终达到6和67.以上结果表明，CCGA具有 在另一父代中出现的顺序，复杂度为0(n2):指派规 良好的收敛性和求解质量 则为每个订单寻找具有最小临时加工时间的机器， 5结论 复杂度为0(m),共计n个订单，复杂度为0(mm). 因此每条染色体进化操作的复杂度为0(mm+n2), 本文针对不相关并行机环境下具有可加工机器 而CCGA、CCGAII和TGA则为O(n),明显低于 限制、顺序和机器依赖的安装时间的订单接受与调
王柏琳等: 安装时间和机器受限的订单接受与并行机调度 表 3 4 种算法生成零成本问题解的算例数量 Table 3 Number of solutions with zero total cost produced by the four algorithms n m CCGA CCGAII TGA GADＲ n m CCGA CCGAII TGA GADＲ 20 2 20 19 3 17 150 2 0 0 0 0 5 31 28 14 21 5 2 0 0 0 50 2 14 7 0 1 10 8 0 0 1 5 31 23 0 13 15 9 0 0 2 10 33 20 1 22 20 12 0 0 3 100 2 0 0 0 0 200 2 0 0 0 0 5 7 0 0 1 5 0 0 0 0 10 22 7 0 5 10 0 0 0 0 15 24 11 0 12 15 1 0 0 0 20 32 11 0 15 20 9 0 0 0 总计 255 126 18 113 此外，表 2 中 CCGA 的标准差最小，说明 CCGA 的求 解 性 能 相 对 稳 定． 进 一 步，由 表 2 可 以 计 算 出 CCGAII、TGA 和 GADＲ 相对于 CCGA 的平均总成本 偏离率，分别为 2. 43、10. 95 和 20. 75，由此可得: ① 基于协同进化的 CCGA 和 CCGAII 明显优于 TGA 和 GADＲ． 在实验中，CCGA 和 CCGAII 的种群规模和 进化代数仅为 TGA 和 GADＲ 的一半，却能显著超越 后两种算法，这说明协同进化对于求解并行机调度 是有效的． ②CCGAII 的平均总成本是 CCGA 的 3. 4 倍，这说明对于订单接受与调度，列表拒绝方法比嵌 入染色体进化的拒绝决策更为有效． 表 4 给 出 了 4 种 算 法 在 求 解 规 模 组 20X5、 100X10、200X20 以及所有 1000 个实例的平均 CPU 时间，计算效率由高至低分别为 CCGAII、CCGA、 TGA、GADＲ，其中 CCGAII 和 CCGA 的计算时间非 常相近． 表 4 4 种算法的 CPU 时间 Table 4 CPU times of the four algorithms s n m CCGA CCGAII TGA GADＲ n m CCGA CCGAII TGA GADＲ 20 5 0. 31 0. 30 0. 59 0. 84 200 20 33. 91 32. 41 66. 45 241. 31 100 10 7. 72 7. 37 15. 46 32. 98 平均值 14. 24 13. 23 23. 28 72. 28 现对表 4 结果分析如下: ( 1) CCGA 计算时间略多于 CCGAII，这是因为 CCGA 需要对订单逐一判定是否拒绝． 但两个算法 的计算时间平均差值仅 1. 01 s，说明列表拒绝方法 对计算时间的影响基本可以忽略． ( 2) TGA 和 GADＲ 的计算时间明显慢于 CCGA 和 CCGAII，这是由两倍的种群规模和进化代数所导 致的． 其 中 GADＲ 的 计 算 时 间 最 长，这 是 因 为 GADＲ 采用了单点交叉算子来生成合法的置换序 列，进而采用指派规则为订单确定机器． 单点交叉 算子需要搜索一个父代在交叉点后的每个等位基因 在另一父代中出现的顺序，复杂度为 O( n2 ) ; 指派规 则为每个订单寻找具有最小临时加工时间的机器， 复杂度为 O( m) ，共计 n 个订单，复杂度为 O( mn) ． 因此每条染色体进化操作的复杂度为 O( mn + n2 ) ， 而 CCGA、CCGAII 和 TGA 则为 O ( n) ，明显 低 于 GADＲ． 这说明了 CCGA 的编码方案有效且遗传算 子的计算效率较优． 下面对算法收敛性进行比较． 图 3 给出了规模 100X10 的实例在迭代 600 代时的算法收敛曲线． 可以看出，基于列表拒绝方法的 CCGA 和 TGA 能够得到相对较优的初始解． 为便于进一步观察， 图 4 给出了 CCGA 和 TGA 的收敛曲线． 在这 4 种算 法中，CCGA 最先在第 241 代找到了最优的零成本 解，CCGAII 则在 550 代达到零成本． 经进一步运行 算法发现，GADＲ 和 TGA 在 2000 代时仍未取得零 成本，最终达到 6 和 67． 以上结果表明，CCGA 具有 良好的收敛性和求解质量． 5 结论 本文针对不相关并行机环境下具有可加工机器 限制、顺序和机器依赖的安装时间的订单接受与调 · 735 ·