基于HITHS算法的多节点多加工路线订单接受问题研究

D0L:10.13374.issn1001-053x.2013.10.016 第35卷第10期 北京科技大学学报 Vol.35 No.10 2013年10月 Journal of University of Science and Technology Beijing 0ct.2013 基于IITHS算法的多节点多加工路线订单接受问 题研究 王雷1,2)心，李铁克12)，王欣3)，许绍云1,2)，孙琦4) 1)北京科技大学东凌经济管理学院，北京1000832)钢铁生产制造执行系统技术教育部工程研究中心，北京100083 3)西北农林科技大学经济管理学院，杨凌7121004)浙江工商大学工商管理学院，杭州310018 ☒通信作者，E-mail:leonwang521@126.com 摘要针对具有提前/拖期特点的多节点多加工路线订单接受问题，提出采用改进NEH启发式算法、局部搜索和智能 调谐和声搜索算法的混合智能调谐和声搜索算法（ⅡTHS)来求解问题.该算法首先在初始解空间中采用改进NEH启 发式算法产生部分初始解，然后利用智能调谐和声搜索算法更新初始解，在更新过程中再利用局部搜索的互换、交换和 逆序操作使其避免陷入局部最优解，从而形成问题的近似最优解.最后采用所提出的混合算法对该问题进行算例分析， 并和基本和声搜索算法进行比较，表明了混合算法的有效性和可行性. 关键词生产控制：订单接受：和声搜索：局部搜索：启发式算法 分类号TP278 Research on order acceptance of multi-node and multi-process routes with HITHS algorithm WANG Lei2)K,LI Tie-kel.2),WANG Xin3),XU Shao-yun1.2),SUN Qi) 1)Dongling School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China 2)Engineering Research Center of MES Technology for Iron and Steel Production (Ministry of Education),Beijing 100083,China 3)School of Economics and Management,Northwest A&F University,Yangling 712100,China 4)School of Business Administration,Zhejiang Gongshang University,Hangzhou 310018,China Corresponding author,E-mail:leonwang521@126.com ABSTRACT Aiming at the order acceptance problem of multi-node and multi-process routes with the characteris- tics of earliness/tardiness,a mixed intelligent tuned harmony search algorithm(HITHS)with improved NEH heuristic algorithm,local search and intelligent tuned harmony search was proposed for resolving the problem.In this algorithm, some initial solutions in the initial solution space were generated by improved NEH heuristic algorithm.Then these initial solutions were updated with intelligent tuned harmony search.In the updating process,a series of operations such as interchange,exchange and reverse of local search were used to avoid falling into a local optimal solution,and thus the problem's approximate optimum solution was got.At last,a case of the problem was tested by the mixed algorithm. The effectiveness and efficiencies of the mixed algorithm was proved by the case's analysis and compared with harmony search. KEY WORDS production control;order acceptance;harmony search;local search;heuristic algorithms 按订单生产方式是企业根据顾客的订货量和品.典型的按订单生产方式进行生产的行业包括工 交货期安排生产，目的在于降低库存和生产多种产程制造、钢铁、建筑、工业锅炉等川.顾客订单是 收稿日期：2012-09-21 基金项目：教育部博士学科点专项科研基金资助项目(20100006110006)：中央高校基本科研业务费专项(FRF-SD-12-011B,FRF. SD-12-012B):国家自然科学基金资助项目(70771008.71301146)

第 35 卷 第 10 期 北 京 科 技 大 学 学 报 Vol. 35 No. 10 2013 年 10 月 Journal of University of Science and Technology Beijing Oct. 2013 基于 HITHS 算法的多节点多加工路线订单接受问 题研究 王 雷1,2) ，李铁克1,2)，王 欣3)，许绍云1,2) ，孙 琦4) 1) 北京科技大学东凌经济管理学院，北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心，北京 100083 3) 西北农林科技大学经济管理学院，杨凌 712100 4) 浙江工商大学工商管理学院，杭州 310018 通信作者，E-mail: leonwang521@126.com 摘 要 针对具有提前/拖期特点的多节点多加工路线订单接受问题，提出采用改进 NEH 启发式算法、局部搜索和智能 调谐和声搜索算法的混合智能调谐和声搜索算法 (HITHS) 来求解问题. 该算法首先在初始解空间中采用改进 NEH 启 发式算法产生部分初始解，然后利用智能调谐和声搜索算法更新初始解，在更新过程中再利用局部搜索的互换、交换和 逆序操作使其避免陷入局部最优解，从而形成问题的近似最优解. 最后采用所提出的混合算法对该问题进行算例分析， 并和基本和声搜索算法进行比较，表明了混合算法的有效性和可行性. 关键词 生产控制；订单接受；和声搜索；局部搜索；启发式算法 分类号 TP278 Research on order acceptance of multi-node and multi-process routes with HITHS algorithm WANG Lei1,2) , LI Tie-ke1,2), WANG Xin3), XU Shao-yun1,2) , SUN Qi4) 1) Dongling School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China 2) Engineering Research Center of MES Technology for Iron and Steel Production (Ministry of Education), Beijing 100083, China 3) School of Economics and Management, Northwest A&F University, Yangling 712100, China 4) School of Business Administration, Zhejiang Gongshang University, Hangzhou 310018, China Corresponding author, E-mail: leonwang521@126.com ABSTRACT Aiming at the order acceptance problem of multi-node and multi-process routes with the characteris￾tics of earliness/tardiness, a mixed intelligent tuned harmony search algorithm (HITHS) with improved NEH heuristic algorithm, local search and intelligent tuned harmony search was proposed for resolving the problem. In this algorithm, some initial solutions in the initial solution space were generated by improved NEH heuristic algorithm. Then these initial solutions were updated with intelligent tuned harmony search. In the updating process, a series of operations such as interchange, exchange and reverse of local search were used to avoid falling into a local optimal solution, and thus the problem’s approximate optimum solution was got. At last, a case of the problem was tested by the mixed algorithm. The effectiveness and efficiencies of the mixed algorithm was proved by the case’s analysis and compared with harmony search. KEY WORDS production control; order acceptance; harmony search; local search; heuristic algorithms 按订单生产方式是企业根据顾客的订货量和 交货期安排生产，目的在于降低库存和生产多种产 品. 典型的按订单生产方式进行生产的行业包括工 程制造、钢铁、建筑、工业锅炉等 [1] . 顾客订单是 收稿日期：2012-09-21 基金项目：教育部博士学科点专项科研基金资助项目 (20100006110006)；中央高校基本科研业务费专项 (FRF-SD-12-011B, FRF￾SD-12-012B)；国家自然科学基金资助项目 (70771008, 71301146) DOI:10.13374/j.issn1001-053x.2013.10.016

第10期 王雷等：基于HTHS算法的多节点多加工路线订单接受问题研究 ·1391· 按订单生产方式的主要驱动力，充分协调企业生产 有固定的加工路径.本文研究多个加工节点为背 和销售部门之间的矛盾，有利于生产资源合理利用 景、考虑订单有多个加工路径可供选择环境下的订 和顾客订单履约②.实际生产中，销售部门的目标 单接受问题，在多节点多加工路线生产模式下，订 是尽可能接受所有订单实现最大化收益，而不考虑 单接受决策和订单排产要同时协调，否则接受的订 现有生产和库存能力.生产部门关心有限产能实现 单可能提前完工造成库存成本或得不到足够的资源 最小化的存储和延迟成本.顾客订单不能履约将导 造成订单延迟.多节点多加工路线生产环境下的订 致库存成本的增加或延迟生产的惩罚费用，使企业 单接受要求有多个加工单元，每个加工单元有一台 和顾客的收益造成损失.因此，当面对大量顾客订 或多台机器，订单按照相同的顺序依次经过所有的 单到达时，如何选择和安排订单使存储成本和延迟 加工单元，但是订单在同一个加工节点会选择不同 成本最小，实现订单总收益最大是企业追求的最主 的机器进行加工，订单各工序之间有线性次序约束， 要目标 每个订单都有固定的加工时间、工期和销售价格， 一般按照订单到达的状态，可分为静态到达问 保证订单有最小的存储和延迟惩罚成本目标函数 题和订单动态到达问题.本文主要研究订单静态到 为考虑订单销售价格减去成本的最大化收益.图1 达的接受问题.Slotnick和Morton3)针对加工厂生 为多节点多加工路线生产环境下订单接受流程图， 产能力小于顾客订货量时，如何进行订单选择做出 该图描述了多节点多加工路线车间环境下订单接受 分析.构建单机环境下订单静态到达接受模型，模 的过程.订单加工过程分为三个作业区，每个作业 型中订单的加工时间、工期和收益为已知，目标函 区承担不同的加工环节，作业区1和作业区3有两 数为订单最大化净收益.Ghosh国证明了Slotnick和 台同型号机器，作业区2有一台机器.在某时间段， Morton(1996)提出的订单接受问题是NP难问题. 企业接收到三个订单，每个订单都有确定的销售价 Alidaee等同考虑了在订单池内选择订单实现目标 格和工期，每个订单有不同的加工路线和在各个加 函数最优，建立best-in规则来解决订单选择问题. 工阶段的加工时间.一般来说，单机条件下的订单 Lewis和Slotnick6l研究周期性的订单选择，顾客 接受问题是NP难问题国，所以多节点多加工路 每个阶段都订购产品直到被拒绝为止，将不在订购. 线车间环境下的订单接受问题也为NP难问题.由 目标函数为当拒绝顾客后不能再获收益的最大化订 于问题的NP难特性不能由精确算法求得最优解， 单收益.Slotnick和Mortonl可针对生产设备建立模 只能通过元启发式算法或启发式算法求得近似最优 型，模型考虑有一个订单池，从订单池中选择部分 解.因此，本文采用改进NEH算法NEH LOV、智 订单实现利润最大化.Rom和Slotnick!阁用遗传算 能调谐和声搜索和局部搜索相结合的混合和声搜索 法求解带有延迟惩罚的订单接受问题.Cesaret等o间 算法对问题进行求解 通过禁忌搜索算法对单机订单接受问题进行求解， 问题要求具有明确的订单投放时间和独立于安装时 2问题建模 间的订单排序.Parsaei等ho根据伊朗汽车制造厂 2.1多节点多加工路线订单接受问题 实际订单接受过程建立订单接受模型，利用模糊层 考虑多节点多加工路线订单接受问题是有n个 次分析法计算指标权重，TOPSIS技术确定订单排 订单到达，订单可以在每个节点的任意一台机器上 序.Xiao等1在置换流水车间条件研究了订单接 加工，加工机器每次只能加工一个订单，订单加工 受问题，采用元启发式和模拟退火结合的算法对问 时不能够中断.有个加工节点，每个加工节点都 题进行求解并得到了近似最优解 包含最少一台同型号的加工机器②.每个订单在 一般的订单接受问题在目标函数上主要考虑 每个节点选择一个加工机器，确定每个订单的加工 订单延迟的惩罚成本如何影响订单收益，很少考虑 路线，然后计算出一个订单的收益（订单销售价格 订单提前完工时的存储成本和拖期完工时的延迟成 减去订单提前完工的库存成本和延迟交货的惩罚成 本同时存在的情况.在加工环境中，大多研究在单 本).如果订单收益为负，则拒绝接受订单 个节点上的接受问题，少部分文献研究了多节点加 考虑提前/拖期的多节点多加工路线订单接受 工环境.本文将在多节点多加工路线环境下，研究 问题包括如下假设： 考虑提前/拖期的订单接受问题， 1)订单之间相互独立，订单在零时刻允许加工： ，问题描述 1 2)订单在两个连续加工节点之间的运送时间 现有文献关于订单接受问题都假设每个订单都 和设备安装时间包括在订单加工时间里：

第 10 期 王 雷等：基于 HITHS 算法的多节点多加工路线订单接受问题研究 1391 ·· 按订单生产方式的主要驱动力，充分协调企业生产 和销售部门之间的矛盾，有利于生产资源合理利用 和顾客订单履约 [2] . 实际生产中，销售部门的目标 是尽可能接受所有订单实现最大化收益，而不考虑 现有生产和库存能力. 生产部门关心有限产能实现 最小化的存储和延迟成本. 顾客订单不能履约将导 致库存成本的增加或延迟生产的惩罚费用，使企业 和顾客的收益造成损失. 因此，当面对大量顾客订 单到达时，如何选择和安排订单使存储成本和延迟 成本最小，实现订单总收益最大是企业追求的最主 要目标. 一般按照订单到达的状态，可分为静态到达问 题和订单动态到达问题. 本文主要研究订单静态到 达的接受问题. Slotnick 和 Morton[3] 针对加工厂生 产能力小于顾客订货量时，如何进行订单选择做出 分析. 构建单机环境下订单静态到达接受模型，模 型中订单的加工时间、工期和收益为已知，目标函 数为订单最大化净收益.Ghosh[4] 证明了 Slotnick 和 Morton (1996) 提出的订单接受问题是NP 难问题. Alidaee 等 [5] 考虑了在订单池内选择订单实现目标 函数最优，建立 best-in 规则来解决订单选择问题. Lewis 和 Slotnick[6] 研究周期性的订单选择，顾客 每个阶段都订购产品直到被拒绝为止，将不在订购. 目标函数为当拒绝顾客后不能再获收益的最大化订 单收益. Slotnick 和 Morton[7] 针对生产设备建立模 型，模型考虑有一个订单池，从订单池中选择部分 订单实现利润最大化. Rom 和 Slotnick[8] 用遗传算 法求解带有延迟惩罚的订单接受问题.Cesaret 等 [9] 通过禁忌搜索算法对单机订单接受问题进行求解， 问题要求具有明确的订单投放时间和独立于安装时 间的订单排序. Parsaei 等 [10] 根据伊朗汽车制造厂 实际订单接受过程建立订单接受模型，利用模糊层 次分析法计算指标权重，TOPSIS 技术确定订单排 序. Xiao 等 [11] 在置换流水车间条件研究了订单接 受问题，采用元启发式和模拟退火结合的算法对问 题进行求解并得到了近似最优解. 一般的订单接受问题在目标函数上主要考虑 订单延迟的惩罚成本如何影响订单收益，很少考虑 订单提前完工时的存储成本和拖期完工时的延迟成 本同时存在的情况. 在加工环境中，大多研究在单 个节点上的接受问题，少部分文献研究了多节点加 工环境. 本文将在多节点多加工路线环境下，研究 考虑提前/拖期的订单接受问题. 1 问题描述 现有文献关于订单接受问题都假设每个订单都 有固定的加工路径. 本文研究多个加工节点为背 景、考虑订单有多个加工路径可供选择环境下的订 单接受问题，在多节点多加工路线生产模式下，订 单接受决策和订单排产要同时协调，否则接受的订 单可能提前完工造成库存成本或得不到足够的资源 造成订单延迟. 多节点多加工路线生产环境下的订 单接受要求有多个加工单元，每个加工单元有一台 或多台机器，订单按照相同的顺序依次经过所有的 加工单元，但是订单在同一个加工节点会选择不同 的机器进行加工，订单各工序之间有线性次序约束， 每个订单都有固定的加工时间、工期和销售价格， 保证订单有最小的存储和延迟惩罚成本. 目标函数 为考虑订单销售价格减去成本的最大化收益. 图 1 为多节点多加工路线生产环境下订单接受流程图， 该图描述了多节点多加工路线车间环境下订单接受 的过程. 订单加工过程分为三个作业区，每个作业 区承担不同的加工环节，作业区 1 和作业区 3 有两 台同型号机器，作业区 2 有一台机器. 在某时间段， 企业接收到三个订单，每个订单都有确定的销售价 格和工期，每个订单有不同的加工路线和在各个加 工阶段的加工时间. 一般来说，单机条件下的订单 接受问题是 NP 难问题 [4]，所以多节点多加工路 线车间环境下的订单接受问题也为 NP 难问题. 由 于问题的 NP 难特性不能由精确算法求得最优解， 只能通过元启发式算法或启发式算法求得近似最优 解. 因此，本文采用改进 NEH 算法 NEH LOV、智 能调谐和声搜索和局部搜索相结合的混合和声搜索 算法对问题进行求解. 2 问题建模 2.1 多节点多加工路线订单接受问题 考虑多节点多加工路线订单接受问题是有 n 个 订单到达，订单可以在每个节点的任意一台机器上 加工，加工机器每次只能加工一个订单，订单加工 时不能够中断. 有 m 个加工节点，每个加工节点都 包含最少一台同型号的加工机器 [12] . 每个订单在 每个节点选择一个加工机器，确定每个订单的加工 路线，然后计算出一个订单的收益 (订单销售价格 减去订单提前完工的库存成本和延迟交货的惩罚成 本). 如果订单收益为负，则拒绝接受订单. 考虑提前/拖期的多节点多加工路线订单接受 问题包括如下假设： 1) 订单之间相互独立，订 单在零时刻允许加工； 2) 订单在两个连续加工节点之间的运送时间 和设备安装时间包括在订单加工时间里；

·1392 北京科技大学学报 第35卷 到达订单 生产加工节点（作业区） 接受订单 订单1 作业区1 作业区2 作业区3 订单1 机器 机器一 订单2 「订单21 机器一 {_拒收_ 机器 机器二 订单3 订单3 图1多节点多加工路线生产环境下订单接受流程图 Fig.1 Flow diagram of order acceptance in a production environment with multi-node and multi-process routes 3)每个订单的加工时间已知并固定： 4)当订单在一个机器上进行加工时，订单不允 含-e2m时e2网 许中断： 5)任意两个加工节点之间有无限缓冲能力： Zp=1,pe{L,2,…,n: (4) =1 6)机器可连续使用，不存在维修和故障状态. 22数学模型 2-1ie2…,: (5) (1)数学模型所需相关符号和变量定义.i∈I= p=1 {1,2,…,n}为顾客订单号：j∈J={1,2,…,m}为 C≥S+P,i∈{1,2，…，n},j∈{1,2，…，m}: 加工节点号：k∈K={1,2,…,}为加工节点 (6) 内的加工机器号：p∈P={1,2,…,n为订单 加工排列的位置号：∫为订单的总收益：M为足 C≤S,+1,i∈{1,2，…，n},j∈{1,2，…，m}:(7) 够大的整数：P为订单i在节点方上的加工时 间，i=1,2,…,n,j=1,2,…,m:C为订单i 在节点方上的加工完成时间，i=1,2,…,n,j= {1,2…,n} (8) 1,2,·,m:a为订单提前完工的单位惩罚系数：3 为订单拖期完工的单位惩罚系数；d:为顾客订单i 2,+ 的交货期，d≥0，i=1,2,…,n:p为顾客订单i的 合同金额，p:≥0：S)为顾客订单i的第j个加工节 2Z+hs+M1-2+,Sg∈ i=1 =1 点的开始时间，S≥0：X:为0-1决策变量，当订 {1,2,…,m},p∈{1,2，…，n},k∈{1,2，…，：(9) 单i被接受时，变量取1，否则取0：Yk为0-1 决策变量，当顾客订单i被安排到第方个加工节点 Xi∈{0,1}，i∈{1,2，…，n}: (10) 的第k个机器上加工，变量取1，否则取0：Zp为 Yk∈{0,1}，i,k∈{1,2，…，n},j∈{1,2，…，m}: 0-1决策变量，当订单i被排列到第p个位置时， (11) 变量取1，否则取0. Zip∈{0,1}，i,p∈{1,2，…，n} (12) (2)数学模型.根据上述问题详细描述和符号、 变量的定义，确定下列数学模型： 目标函数(1)为最大化订单总净收益.约束条 maxf=∑Xn-amax(0,d-c）- 件(2)表示订单在加工节点中只能在一台机器上进 i.j=1 行加工.约束条件(3)表示一台机器一次只能加 B;max (cij-di,0) (1) 工一个订单.约束条件（④）表示保证每个优先级的 位置只对应一个订单.约束条件（⑤）表示确保每个 s.t. 订单只有一个优先级位置.约束条件（⑥）表示各订 =1ie1,2…e红2…m 单在各节点的结束时间大于等于开始时间加上加工 (2) 时间.约束条件（⑦）表示同一个订单必须在完成当

· 1392 · 北 京 科 技 大 学 学 报 第 35 卷 图 1 多节点多加工路线生产环境下订单接受流程图 Fig.1 Flow diagram of order acceptance in a production environment with multi-node and multi-process routes 3) 每个订单的加工时间已知并固定； 4) 当订单在一个机器上进行加工时，订单不允 许中断； 5) 任意两个加工节点之间有无限缓冲能力； 6) 机器可连续使用，不存在维修和故障状态. 2.2 数学模型 (1) 数学模型所需相关符号和变量定义.i ∈ I = {1, 2, · · · , n}为顾客订单号；j ∈ J = {1, 2, · · · , m} 为 加工节点号；k ∈ K = {1, 2, · · · , k} 为加工节点 内的加工机器号；p ∈ P = {1, 2, · · · , n} 为订单 加工排列的位置号；f 为订单的总收益；M 为足 够大的整数；Pi,j 为订单 i 在节点 j 上的加工时 间，i = 1, 2, · · · , n, j = 1, 2, · · · , m；Ci,j 为订单 i 在节点 j 上的加工完成时间，i = 1, 2, · · · , n, j = 1, 2, · · · , m；αi 为订单提前完工的单位惩罚系数；βi 为订单拖期完工的单位惩罚系数；di 为顾客订单 i 的交货期，di>0，i = 1, 2, · · · , n；pi 为顾客订单 i 的 合同金额，pi>0；Sij 为顾客订单 i 的第 j 个加工节 点的开始时间，Sij>0；Xi 为 0 − 1 决策变量，当订 单 i 被接受时，变量取 1，否则取 0；Yijk 为 0 − 1 决策变量，当顾客订单 i 被安排到第 j 个加工节点 的第 k 个机器上加工，变量取 1，否则取 0；Zip 为 0 − 1 决策变量，当订单 i 被排列到第 p 个位置时， 变量取 1，否则取 0. (2) 数学模型. 根据上述问题详细描述和符号、 变量的定义，确定下列数学模型： max f = Xn i,j=1 Xi h pi − αi max (0, di − ci,j ) − βi max (ci,j − di , 0) i . (1) s.t. X k k=1 Yijk = 1, i ∈ {1, 2, · · · , n} , j ∈ {1, 2, · · · , m}； (2) Xn i=1 Yijk = 1, j ∈ {1, 2, · · · , m} , k ∈ {1, 2, · · · , k}；(3) Xn i=1 Zip = 1, p ∈ {1, 2, · · · , n}； (4) Xn p=1 Zip = 1, i ∈ {1, 2, · · · , n} ； (5) Cij > Sij + Pij , i ∈ {1, 2, · · · , n} , j ∈ {1, 2, · · · , m}； (6) Cij 6 Si,j+1, i ∈ {1, 2, · · · , n} , j ∈ {1, 2, · · · , m}；(7) Xn i=1 ZipSij 6 Xn i=1 Zi,p+1Sij , j ∈ {1, 2, · · · , m} , p ∈ {1, 2, · · · , n} ; (8) Xn i=1 ZipYijk(Sij + Pij ) 6 Xn i=1 Zi,p+1YijkSij + M(1 − Xn i=1 Zi,p+1YijkSij ),j ∈ {1, 2, · · · , m} , p ∈ {1, 2, · · · , n} , k ∈ {1, 2, · · · , k}; (9) Xi ∈ {0, 1} , i ∈ {1, 2, · · · , n}； (10) Yijk ∈ {0, 1} , i, k ∈ {1, 2, · · · , n} , j ∈ {1, 2, · · · , m}； (11) Zip ∈ {0, 1} , i, p ∈ {1, 2, · · · , n}. (12) 目标函数 (1) 为最大化订单总净收益. 约束条 件 (2) 表示订单在加工节点中只能在一台机器上进 行加工. 约束条件 (3) 表示一台机器一次只能加 工一个订单. 约束条件 (4) 表示保证每个优先级的 位置只对应一个订单. 约束条件 (5) 表示确保每个 订单只有一个优先级位置. 约束条件 (6) 表示各订 单在各节点的结束时间大于等于开始时间加上加工 时间. 约束条件 (7) 表示同一个订单必须 在完成当

第10期 王雷等：基于HTHS算法的多节点多加工路线订单接受问题研究 ·1393· 前节点加工时才能进入下一个节点进行加工.约束 敛速度.和声搜索算法求解的多节点多加工路线订 条件（⑧）表示在同一个加工节点，订单的优先级越 单接受问题的求解过程在以下各节给出， 高越早开始进行加工.约束条件(9)表示对于同一 3.1基本和声搜索算法的求解订单接受问题的流程 个加工节点分配在同一个加工机器上的订单，优先 3.1.1订单编码规则 级较高的订单加工结束后才能加工优先级较低的订 基本和声搜索算法针对连续性变量进行调整， 单.当处于不同优先级位置的订单不在同一节点的 而订单接受问题中调整的变量是订单号，具有离 同一个加工机器上加工时，公式中的M值保证了 散性质.因此，在编码规则上将采用最大位置法 公式成立.约束条件(10)、(11)和(12)表示决策变 (LPV)将(-1,1)之间随机产生的小数表示的和声序 量的取值，变量的取值为0或1. 列转换成订单号序列，这样通过调整位置中的小数 订单接受问题主要包括订单排序和订单选择 进而调整订单号序列计算出和声的适应值.最大位 两个方面，其中订单排序是核心问题.订单选择是 置法(LPV)规则示例如图2所示.根据最大位置法 在订单排序后，比较订单净收益的结果进行决策， 原则，将变量对应的最大数值放到第一个位置上， 所以利用优化算法对模型进行求解并选择出最优订 依次按照数值不升将对应的订单号依次排列，得到 单排序、计算出最大净收益是订单接受问题实现的 一个订单的加工序列. 关键.订单接受过程按以下三个过程进行：首先，按 订单号 2 3 4 5 照订单的优先级确定初始加工顺序，利用混合算法 X() 0.2 0.4 -0.1 -0.05 0.7 求解出最优加工顺序，同时计算出每个订单收益的 M 最大值：其次，对最优排序中的各个订单按照净收 益值的大小进行排列：最后，如果存在收益小于0 订单号 1 2 3 4 5 的订单将其剔除，得到收益全部大于0的订单，计 降序X() 0.7 0.4 0.2 0.05 -0.1 算出最优总净收益值，完成订单接受过程 图2 最大位置法示例 3混合算法求解多节点多加工路线订单接 Fig.2 Example of LVP rule 受问题 3.1.2利用NEH LOV启发式算法确定订单加工序列 以往文献关于订单接受问题的求解采用了遗 NEH算法是一种针对混合流水车间调度问题 传算法、粒子群算法、禁忌搜素等元启发式算法， 的有效算法，它的重要特性是具有工件的总加工时 取得了较好的效果，而和声搜索算法作为一种全局 间越大则被赋予越大的优先级，工件总加工时间小 优化的启发式方法，在某些问题求解上取得了比遗 的具有较小的优先级并被安排在后面进行加工1) 传算法、粒子群算法更好的性能. 然而对于多节点多加工路线的订单接受问题，每个 和声搜索算法将乐器类比于优化问题中的设 订单都有固定的订单订货金额，具有越大的加工时 计变量，各乐器声调的和声相当于优化问题的解向 间的订单未必能获得最大的利润，按照NEH算法 量，评价类比于目标函数.算法首先产生一些初始 安排订单加工顺序有可能造成订单利润的损失.因 解（和声）放入和声记忆库(M)）内，以和声记忆 此，本实验针对多节点多加工路线订单接受问题的 库考虑概率(HMCR)在HM内搜索新解，以概率 合理假设为具有较大订单订货金额的订单具有越大 1-HMCR在和声记忆库外的变量可能值域中搜索. 加工优先级. 然后算法以基音调整概率PAR对新解产生局部扰 由于订单具有多个加工路线进行选择，说明在 动.判断新解目标函数值是否优于和声记忆库内的 某些加工节点具有多台机器可供选择.订单按照订 最差解，若是，则替换之：然后不断迭代，直至达 单金额的大小排好加工顺序后，需要指定存在多台 到预定迭代次数为止. 加工机器节点上的加工机器，通过机器指定可以有 和声搜索算法的参数分别为和声记忆库、和声 效计算出订单接受问题的适应度值. 记忆库考虑概率、基音调整概率、基音调整步长 机器无闲置订单分配策略：给定一个排好加工 (BW)和最大迭代次数.和声记忆库考虑概率能提 顺序的订单序列，按照订单优先级的大小，依次 高算法的广度搜索能力，基音调整概率可以提高算 在各节点将各订单分配在具有最早释放时间的机器 法的深度搜索能力：同时，基音调整概率和基音调 上4.基于以上策略设计一种NEH算法的变形算 整步长能够很好地调节最优解向量，加快算法的收 法NEH.LOV(largest order value)算法，新算法的

第 10 期 王 雷等：基于 HITHS 算法的多节点多加工路线订单接受问题研究 1393 ·· 前节点加工时才能进入下一个节点进行加工. 约束 条件 (8) 表示在同一个加工节点，订单的优先级越 高越早开始进行加工. 约束条件 (9) 表示对于同一 个加工节点分配在同一个加工机器上的订单，优先 级较高的订单加工结束后才能加工优先级较低的订 单. 当处于不同优先级位置的订单不在同一节点的 同一个加工机器上加工时，公式中的 M 值保证了 公式成立. 约束条件 (10)、(11) 和 (12) 表示决策变 量的取值，变量的取值为 0 或 1. 订单接受问题主要包括订单排序和订单选择 两个方面，其中订单排序是核心问题. 订单选择是 在订单排序后，比较订单净收益的结果进行决策， 所以利用优化算法对模型进行求解并选择出最优订 单排序、计算出最大净收益是订单接受问题实现的 关键. 订单接受过程按以下三个过程进行：首先，按 照订单的优先级确定初始加工顺序，利用混合算法 求解出最优加工顺序，同时计算出每个订单收益的 最大值；其次，对最优排序中的各个订单按照净收 益值的大小进行排列；最后，如果存在收益小于 0 的订单将其剔除，得到收益全部大于 0 的订单，计 算出最优总净收益值，完成订单接受过程. 3 混合算法求解多节点多加工路线订单接 受问题 以往文献关于订单接受问题的求解采用了遗 传算法、粒子群算法、禁忌搜素等元启发式算法， 取得了较好的效果，而和声搜索算法作为一种全局 优化的启发式方法，在某些问题求解上取得了比遗 传算法、粒子群算法更好的性能. 和声搜索算法将乐器类比于优化问题中的设 计变量，各乐器声调的和声相当于优化问题的解向 量，评价类比于目标函数. 算法首先产生一些初始 解 (和声) 放入和声记忆库 (HM) 内，以和声记忆 库考虑概率 (HMCR) 在 HM 内搜索新解，以概率 1–HMCR 在和声记忆库外的变量可能值域中搜索. 然后算法以基音调整概率 PAR 对新解产生局部扰 动. 判断新解目标函数值是否优于和声记忆库内的 最差解，若是，则替换之；然后不断迭代，直至达 到预定迭代次数为止. 和声搜索算法的参数分别为和声记忆库、和声 记忆库考虑概率、基音调整概率、基音调整步长 (BW) 和最大迭代次数. 和声记忆库考虑概率能提 高算法的广度搜索能力，基音调整概率可以提高算 法的深度搜索能力；同时，基音调整概率和基音调 整步长能够很好地调节最优解向量，加快算法的收 敛速度. 和声搜索算法求解的多节点多加工路线订 单接受问题的求解过程在以下各节给出. 3.1 基本和声搜索算法的求解订单接受问题的流程 3.1.1 订单编码规则 基本和声搜索算法针对连续性变量进行调整， 而订单接受问题中调整的变量是订单号，具有离 散性质. 因此，在编码规则上将采用最大位置法 (LPV) 将 (–1,1) 之间随机产生的小数表示的和声序 列转换成订单号序列，这样通过调整位置中的小数 进而调整订单号序列计算出和声的适应值. 最大位 置法 (LPV) 规则示例如图 2 所示. 根据最大位置法 原则，将变量对应的最大数值放到第一个位置上， 依次按照数值不升将对应的订单号依次排列，得到 一个订单的加工序列. 图 2 最大位置法示例 Fig.2 Example of LVP rule 3.1.2 利用 NEH LOV启发式算法确定订单加工序列 NEH 算法是一种针对混合流水车间调度问题 的有效算法，它的重要特性是具有工件的总加工时 间越大则被赋予越大的优先级，工件总加工时间小 的具有较小的优先级并被安排在后面进行加工 [13] . 然而对于多节点多加工路线的订单接受问题，每个 订单都有固定的订单订货金额，具有越大的加工时 间的订单未必能获得最大的利润，按照 NEH 算法 安排订单加工顺序有可能造成订单利润的损失. 因 此，本实验针对多节点多加工路线订单接受问题的 合理假设为具有较大订单订货金额的订单具有越大 加工优先级. 由于订单具有多个加工路线进行选择，说明在 某些加工节点具有多台机器可供选择. 订单按照订 单金额的大小排好加工顺序后，需要指定存在多台 加工机器节点上的加工机器，通过机器指定可以有 效计算出订单接受问题的适应度值. 机器无闲置订单分配策略：给定一个排好加工 顺序的订单序列，按照订单优先级的大小，依次 在各节点将各订单分配在具有最早释放时间的机器 上 [14] . 基于以上策略设计一种 NEH 算法的变形算 法 NEH LOV (largest order value) 算法，新算法的

·1394 北京科技大学学报 第35卷 计算步骤如下 库考虑概率、基音调整概率和随机选取.首先，随机 步骤1在已到达的订单中，按照订单合同金 生成数rand1,如果随机数rand1小于记忆库考虑概 额的大小由大到小产生成一个订单加工的顺序： 率，以HMCR从和声记忆库中选择一个值作为新向 步骤2从排好的订单加工顺序中选择前两个 量中的变量.否则，以1-ⅢMCR的概率从可行取值 订单，这两个订单可以产生两个局部订单加工顺序， 范围内按照xnew()=xmin()+(zmax()-xmin()× 按照适应度值的大小选择一个更好的订单加工顺序 rand(0,1)选择一个值.无论以何种方式选择新的变 作为当前的加工顺序： 量，都要决定是否选择变量的基音调整.基音调整 步骤3把剩下的订单逐个放入已排好的局部 以PAR进行调整，以1-PAR的概率选择不调整. 订单加工顺序后面的各个位置，计算适应度函数值， 变量按照xnew()←-xnew()士rand()×BW进行调 选择出最好的局部订单加工顺序作为下一个迭代的 整，其中BW是基音调整步长，rand0为0到1之 基础加工顺序（如果几个局部订单加工顺序有相同 间的随机数. 的适应度值，则随机选取一个作为最好的局部订单 3.1.5更新订单的和声记忆库 加工顺序)： 以和声向量适应度函数值的好坏来判断新的 步骤4重复步骤3直到找出最好的订单加工 和声向量是否比原来和声记忆库中最差的和声向量 顺序 好，如果更好则在和声记忆库中保留新的和声向量， 显然，NEH.LOV算法与NEH算法具有相同的 去除原来存在的最差和声向量：如没有原来的最差 时间复杂度 和声向量好，则在和声记忆库中保留原来的和声向量 3.1.3订单的和声记忆库初始化 3.2智能调谐和声搜索算法 为了保证订单的初始和声记忆库中和声向量 智能调谐和声搜索算法基于自身的认知能力 的质量和多样性，由NHE LOV启发式算法生产 来控制深度搜索和广度搜索能力.该算法将和声记 个初始和声向量，即订单加工序列.剩下的和声向 忆库作为一个组织对待，依据种群中每个订单加工 量随机产生，和声向量按下式(13)随机生成： 序列的目标函数值选取一个领导解向量，领导解向 z(i)=Zmin(i)+(Imax(i)-Imin(i))x rand,i= 量表示为x=HM(best,1:N) 在元启发式算法中，初始种群分割为几个相互 1,2,·,n. (13) 联系的子种群能够加强深度搜索和广度搜索之间的 其中，对于和声向量的每一个维度都具有最小值和 平衡能力.因此，为了得到适当的深度搜索和广度 最大值，即xmin()=-1.0,xmax()=1.0,rand是 搜索的平衡能力，智能调谐和声搜索将和声记忆库 (O,1)之间连续的随机数.由NEH.LOV启发式算法 分解为两个子记忆库，子库A和子库B.子库A由 产生的订单加工序列应按照下式(14)转换成和声 解向量的目标函数值小于HMmean组成，HMmean 向量： 为和声记忆库中所有解向量适应值的平均值.子库 2((i))=max-max-min x (i-1) B由其余的解向量组成.子库A调节算法的深度搜 n-1 索和广度搜索能力，子库郁主要调节广度搜索能可 i=1,2,·,n. (14) 智能调谐和声搜索算法根据迭代次数自动更 式中，xmin和xmax为初始和声记忆库中的最小值 新变量PAR的值，更新表达式为PAR(Iter)= 和最大值，π()为订单i在加工序列π中对应的位 PARmax--(PARmax一PARin)'小tet Iter ,其中Iter代 置号 表当前的迭代次数，最小基音调整概率PARmin和 假设有一个五维向量，xmin=-0.6和工max= 最大基音调整概率PARmax分别取0和1.PAR值 O.9,根据NEH LOV启发式算法产生的订单加工序 随时间逐步减小可以防止过冲，因此开始要设置较 为π=(3,2,1,5,4)，由式(14)可得x(3)=0.9,x(2)= 大的基音调整BW步长，这种设置使得算法扩大了 0.525.x(1)=0.15,x(5)）=-0.225,x(4)=-0.6,最 解向量的搜索空间，避免陷入局部最优解PAR值 后得到转换后的和声向量为X=(0.9,0.525,0.15, 逐渐调整也可以调整解向量的取值，使算法在最后 -0.225.-0.6). 迭代时集中在深度搜索能力上. 3.1.4即兴产生一个新订单加工序列 智能调谐和声搜索即兴创作一个新和声，新和 产生一个新的和声向量叫做“即兴创作”.一个 声中的变量xnew()从它所属的子库中选取.选择 新的订单加工序列xmew的产生基于三条原则：记忆 变量的基音调整根据以下公式进行：

· 1394 · 北 京 科 技 大 学 学 报 第 35 卷 计算步骤如下. 步骤 1 在已到达的订单中，按照订单合同金 额的大小由大到小产生成一个订单加工的顺序； 步骤 2 从排好的订单加工顺序中选择前两个 订单，这两个订单可以产生两个局部订单加工顺序， 按照适应度值的大小选择一个更好的订单加工顺序 作为当前的加工顺序； 步骤 3 把剩下的订单逐个放入已排好的局部 订单加工顺序后面的各个位置，计算适应度函数值， 选择出最好的局部订单加工顺序作为下一个迭代的 基础加工顺序 (如果几个局部订单加工顺序有相同 的适应度值，则随机选取一个作为最好的局部订单 加工顺序)； 步骤 4 重复步骤 3 直到找出最好的订单加工 顺序. 显然，NEH LOV 算法与 NEH 算法具有相同的 时间复杂度. 3.1.3 订单的和声记忆库初始化 为了保证订单的初始和声记忆库中和声向量 的质量和多样性，由 NHE LOV 启发式算法生产一 个初始和声向量，即订单加工序列. 剩下的和声向 量随机产生，和声向量按下式 (13) 随机生成： x(i) = xmin(i) + (xmax(i) − xmin(i)) × rand, i = 1, 2, · · · , n. (13) 其中，对于和声向量的每一个维度都具有最小值和 最大值，即 xmin(i) = −1.0，xmax(i) = 1.0，rand 是 (0,1) 之间连续的随机数. 由 NEH LOV 启发式算法 产生的订单加工序列应按照下式 (14) 转换成和声 向量： x(π(i)) = xmax − xmax − xmin n − 1 × (i − 1), i = 1, 2, · · · , n. (14) 式中，xmin 和 xmax 为初始和声记忆库中的最小值 和最大值，π(i) 为订单 i 在加工序列 π 中对应的位 置号. 假设有一个五维向量，xmin = −0.6 和 xmax = 0.9，根据 NEH LOV 启发式算法产生的订单加工序 为 π = (3, 2, 1, 5, 4)，由式 (14) 可得x(3) = 0.9，x(2) = 0.525, x(1) = 0.15，x(5) = −0.225，x(4) = −0.6，最 后得到转换 后的和声向量为 X = (0.9, 0.525, 0.15, − 0.225, −0.6). 3.1.4 即兴产生一个新订单加工序列 产生一个新的和声向量叫做 “即兴创作”. 一个 新的订单加工序列 xnew 的产生基于三条原则：记忆 库考虑概率、基音调整概率和随机选取. 首先，随机 生成数 rand1，如果随机数 rand1 小于记忆库考虑概 率，以 HMCR 从和声记忆库中选择一个值作为新向 量中的变量. 否则，以 1–HMCR 的概率从可行取值 范围内按照 xnew(i) = xmin(i) + (xmax(i)−xmin(i))× rand(0, 1) 选择一个值. 无论以何种方式选择新的变 量，都要决定是否选择变量的基音调整. 基音调整 以 PAR 进行调整，以 1–PAR 的概率选择不调整. 变量按照 xnew(i) ← xnew(i) ± rand() × BW 进行调 整，其中 BW 是基音调整步长，rand() 为 0 到 1 之 间的随机数. 3.1.5 更新订单的和声记忆库 以和声向量适应度函数值的好坏来判断新的 和声向量是否比原来和声记忆库中最差的和声向量 好，如果更好则在和声记忆库中保留新的和声向量， 去除原来存在的最差和声向量；如没有原来的最差 和声向量好，则在和声记忆库中保留原来的和声向量. 3.2 智能调谐和声搜索算法 智能调谐和声搜索算法基于自身的认知能力 来控制深度搜索和广度搜索能力. 该算法将和声记 忆库作为一个组织对待，依据种群中每个订单加工 序列的目标函数值选取一个领导解向量，领导解向 量表示为 x −−→best = HM(best, 1︰N). 在元启发式算法中，初始种群分割为几个相互 联系的子种群能够加强深度搜索和广度搜索之间的 平衡能力. 因此，为了得到适当的深度搜索和广度 搜索的平衡能力，智能调谐和声搜索将和声记忆库 分解为两个子记忆库，子库 A 和子库 B. 子库 A 由 解向量的目标函数值小于 HMmean 组成，HMmean 为和声记忆库中所有解向量适应值的平均值. 子库 B 由其余的解向量组成.子库 A 调节算法的深度搜 索和广度搜索能力，子库B主要调节广度搜索能力[15] . 智能调谐和声搜索算法根据迭代次数自动更 新变量 PAR 的值， 更新表达式为 PAR(Iter) = PARmax −(PARmax −PARmin)· Iter Itermax ，其中Iter 代 表当前的迭代次数，最小基音调整概率 PARmin 和 最大基音调整概率 PARmax 分别取 0 和 1. PAR 值 随时间逐步减小可以防止过冲，因此开始要设置较 大的基音调整 BW 步长，这种设置使得算法扩大了 解向量的搜索空间，避免陷入局部最优解.PAR 值 逐渐调整也可以调整解向量的取值，使算法在最后 迭代时集中在深度搜索能力上. 智能调谐和声搜索即兴创作一个新和声，新和 声中的变量 xnew(i) 从它所属的子库中选取. 选择 变量的基音调整根据以下公式进行：