工程科学学报，第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-