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 characteristics 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, FRFSD-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) 从它所属的子库中选取. 选择 变量的基音调整根据以下公式进行：
第10期 王雷等：基于HTHS算法的多节点多加工路线订单接受问题研究 .1395· best()-(best()-Emew()×rand[0,1,以概率小于等于PAR=0.5 Enew(②)= best()+(wrost()-xmew()×rand0,1,以概率大于PAR=0.5; (15) znew(),以概率1一PAR Tbest()和Tworst()为最好和最差解向量的 声记忆库考虑概率、基音调整概率、基音调整步长 第个变量，变量以和声记忆库中之前迭代的历史 和最大迭代次数： 适应值为标准进行选取，因此基音调整基于搜索的 步骤2利用NEH_LOV启发式算法和随机搜 自我认知能力（和声搜索的记忆能力）.在算法的 索确定初始订单加工序列，并计算每个订单加工序 早期阶段，需要在深度搜索和广度搜索之间进行平 列的目标函数值： 衡，而在子库A中采取的基音调整策略能够实现这 步骤3即兴创作一个新订单加工序列： 种平衡.best(i)-(best()-xnew()×rand0,1允 步骤4针对新创作的订单加工序列进行局部 许被选择的变量xnew()在它本身和best()之间进 搜索，更新订单加工序列： 行搜索，所以这种基音调整策略主要体现在深度搜 索上.best(i)+(worst-xmew)×rand[0,主要调整 步骤5将新订单加工序列的目标函数值与和 声记忆库中最差目标函数值的订单加工序列进行比 算法的广度搜索能力，如果选择的变量xmew()接近 worst(i)则zbest(i)+(worst(i)-工new）×rand[0,1刂 较，如果大于最差目标函数值的订单加工序列则替 更接近于Zbest().如果选择的变量xnew(i)远离 换该订单加工序列，更新订单和声记忆库： worst(①)则值也远离zbest().子库A中这种基音 步骤6如果算法满足终止条件结束算法，否 调整策略可以加强算法的广度搜索能力 则跳转到步骤3重新计算， 子库A的搜索空间以cbest(d)和Tworst()为 混合和声搜索算法由智能调谐和声搜索和局 上下边界，如果解向量不在子库A的边界内，智 部搜索算法组成，混合算法可以利用各个算法自身 能调谐和声搜索的解有可能陷入局部最优解。为 的优势来计算出更好的解.和声搜索算法利用不 了克服搜索空间边界问题，提高智能调谐和声搜索 要求决策变量的初始值设置、应用概率随机搜索等 算法搜索的广度，构建子库B.如果被选择的变量 优势能够在深度搜索和广度搜索之间进行很好的平 工new()属于子库B,则子库B能够提高算法搜索 衡.局部搜索对新创作的和声进行进一步的更新， 的广度，变量best(d)从best中随机选择决策变量 增强了算法的局部搜索能力 并在它的邻域内开始搜索.子库B中变量xmew() 的基音调整策略按照以下方式进行：m=int(1+ 4数据实验 (N -1)x rand),zhew =Enew(i)+(xbest(m)- 4.1实验设计 xmew()×rand0,1.其中，m是根据初始规模随机 本文采用Microsoft Visual C++实现改进粒子 例，变量 生成的正整数，beat(m)=best(m×包 群算法，实验环境为Pentium4/2.80GHZ/2.24GB/ xnew()的边界为Lx(i),ux(,tbest(m)的范围是 Windows7.基本和声搜索算法参数设置为：初始 Lx(m),Uz(m)]. 和声记忆库规模大小为30、和声记忆库考虑概率为 3.3嵌入局部搜索的智能调谐和声搜索算法 0.9、基音调整概率为0.33、基音调整步长为0.01、 将局部优化算法嵌入到智能调谐和声搜索算法 最大迭代次数为100.混合智能调谐和声搜索算法 中能够提高算法的搜索能力，在即兴创作和声阶段 参数设置为：初始和声记忆库规模大小为30，和声 改进和声向量的质量.和声向量和订单加工顺序都 记忆库考虑概率为0.99，最大基音调整概率(PAR) 可以应用局部搜索进行改进，本文选取以订单加工 为1.0，最小基音调整概率(PAR)为0，初始和声记 顺序为基础的局部搜索.局部搜索可以使每个和 忆库中的基音的最大值为1.0，初始和声记忆库中 声在其邻域内进行局部最优值的搜索过程.在产生 的基音的最小值为-1.0，最大迭代次数为200. 新的和声时，对新的和声邻域展开搜索，如果某个 实验数据设置如下：订单数n=10,15,20:每 邻居的适应值优于这个和声，那么用这个邻居进行 个订单的合同金额在均匀分布区间「100,10001内随 替换.常用的局部搜索策略包括互换操作、交换操 机产生：订单在各个节点的加工时间在均匀分布区 作和逆序操作 间[1,10]内随机产生；订单的交货期在均匀分布区 3.4混合算法求解订单接受问题的计算步骤 间[4,40]内随机产生：订单提前完工单位惩罚系数 步骤1设置算法的参数订单和声记忆库、和 为1；订单延迟完工单位惩罚系数为3：假设加工节
第 10 期 王 雷等：基于 HITHS 算法的多节点多加工路线订单接受问题研究 1395 ·· xnew(i) = x best(i) − (x best(i) − xnew(i)) × rand[0, 1],以概率小于等于PAR = 0.5; x best(i) + (x wrost(i) − xnew(i)) × rand[0, 1],以概率大于PAR = 0.5; xnew(i),以概率 1 − PAR. (15) x best(i) 和 x worst(i) 为最好和最差解向量的 第i个变量，变量以和声记忆库中之前迭代的历史 适应值为标准进行选取，因此基音调整基于搜索的 自我认知能力 (和声搜索的记忆能力). 在算法的 早期阶段，需要在深度搜索和广度搜索之间进行平 衡，而在子库 A 中采取的基音调整策略能够实现这 种平衡. x best(i) − (x best(i) − xnew(i)) × rand[0, 1] 允 许被选择的变量 xnew(i) 在它本身和 x best(i) 之间进 行搜索，所以这种基音调整策略主要体现在深度搜 索上. x best(i) + (x worst −xnew)×rand[0, 1] 主要调整 算法的广度搜索能力，如果选择的变量 xnew(i) 接近 x worst(i) 则 x best(i) + (x worst(i) − xnew) × rand[0, 1] 更接近于 x best(i). 如果选择的变量 xnew(i) 远离 x worst(i) 则值也远离 x best(i). 子库 A 中这种基音 调整策略可以加强算法的广度搜索能力. 子库 A 的搜索空间以 x best(i) 和 x worst(i) 为 上下边界，如果解向量不在子库 A 的边界内，智 能调谐和声搜索的解有可能陷入局部最优解. 为 了克服搜索空间边界问题，提高智能调谐和声搜索 算法搜索的广度，构建子库 B. 如果被选择的变量 xnew(i) 属于子库 B，则子库 B 能够提高算法搜索 的广度，变量 x best(i) 从 −−→ x best 中随机选择决策变量 并在它的邻域内开始搜索. 子库 B 中变量 xnew(i) 的基音调整策略按照以下方式进行：m = int(1 + (N − 1) × rand)，则 x 0 new = xnew(i) + (x best(m) − xnew(i)) × rand[0, 1]. 其中，m 是根据初始规模随机 生成的正整数，x best(m) = x best(m) × Ux(i) Ux(m) ，变量 xnew(i) 的边界为 [Lx(i), Ux(i)]，x best(m) 的范围是 [Lx(m),U x(m)]. 3.3 嵌入局部搜索的智能调谐和声搜索算法 将局部优化算法嵌入到智能调谐和声搜索算法 中能够提高算法的搜索能力，在即兴创作和声阶段 改进和声向量的质量. 和声向量和订单加工顺序都 可以应用局部搜索进行改进，本文选取以订单加工 顺序为基础的局部搜索. 局部搜索可以使每个和 声在其邻域内进行局部最优值的搜索过程. 在产生 新的和声时，对新的和声邻域展开搜索，如果某个 邻居的适应值优于这个和声，那么用这个邻居进行 替换. 常用的局部搜索策略包括互换操作、交换操 作和逆序操作. 3.4 混合算法求解订单接受问题的计算步骤 步骤 1 设置算法的参数订单和声记忆库、和 声记忆库考虑概率、基音调整概率、基音调整步长 和最大迭代次数； 步骤 2 利用 NEH LOV 启发式算法和随机搜 索确定初始订单加工序列，并计算每个订单加工序 列的目标函数值； 步骤 3 即兴创作一个新订单加工序列； 步骤 4 针对新创作的订单加工序列进行局部 搜索，更新订单加工序列； 步骤 5 将新订单加工序列的目标函数值与和 声记忆库中最差目标函数值的订单加工序列进行比 较，如果大于最差目标函数值的订单加工序列则替 换该订单加工序列，更新订单和声记忆库； 步骤 6 如果算法满足终止条件结束算法，否 则跳转到步骤 3 重新计算. 混合和声搜索算法由智能调谐和声搜索和局 部搜索算法组成，混合算法可以利用各个算法自身 的优势来计算出更好的解. 和声搜索算法利用不 要求决策变量的初始值设置、应用概率随机搜索等 优势能够在深度搜索和广度搜索之间进行很好的平 衡. 局部搜索对新创作的和声进行进一步的更新， 增强了算法的局部搜索能力. 4 数据实验 4.1 实验设计 本文采用 Microsoft Visual C++ 实现改进粒子 群算法，实验环境为 Pentium4/2.80GHZ/2.24GB/ Windows 7. 基本和声搜索算法参数设置为：初始 和声记忆库规模大小为 30、和声记忆库考虑概率为 0.9、基音调整概率为 0.33、基音调整步长为 0.01、 最大迭代次数为 100. 混合智能调谐和声搜索算法 参数设置为：初始和声记忆库规模大小为 30，和声 记忆库考虑概率为 0.99，最大基音调整概率 (PAR) 为 1.0，最小基音调整概率 (PAR) 为 0，初始和声记 忆库中的基音的最大值为 1.0，初始和声记忆库中 的基音的最小值为 –1.0，最大迭代次数为 200. 实验数据设置如下：订单数 n=10，15，20；每 个订单的合同金额在均匀分布区间 [100,1000] 内随 机产生；订单在各个节点的加工时间在均匀分布区 间 [1,10] 内随机产生；订单的交货期在均匀分布区 间 [4,40] 内随机产生；订单提前完工单位惩罚系数 为 1；订单延迟完工单位惩罚系数为 3；假设加工节
·1396 北京科技大学学报 第35卷 点为四个阶段.分别利用混合智能调谐和声搜索算 单接受数和平均订单接受率来分析模型和评价算法. 法(HITHS)和基本和声搜索算法(HS)对多节点多 4.2实验结果分析 加工路线订单接受问题进行求解，根据订单数的不 在混合智能调谐和声搜索算法和基本和声搜索 同，将两种算法求解的实验分成三组，每组生成10 算法的算例中，通过各组生成的10个算例求解出各 个算例，采用平均计算时间、平均订单收益、平均订 项指标的平均值，实验结果见表1.由表1可知： 表1具有多节点多加工路线订单接受的实验结果 Table 1 Experimental results of order acceptance with multi-nodes and multi-process routes 算法 问题规模 平均计算时间/s 平均净收益/元 平均接受订单数 平均订单接受率/% 10×4 13.26 852.7 8.8 88.0 HITHS 15×4 19.62 948.1 11.0 73.3 20×4 22.94 827.1 11.2 56.0 10×4 11.32 756.2 8.0 80.0 HS 15×4 18.47 795.3 9.8 65.3 20×4 21.9 610.6 10.6 53.3 (1)HITHS算法和HS算法都可以在较短的时 些，但是ⅢTHS算法能够始终得到比HS算法要好 间内求解出可行解，随着订单数量的增加平均计算 的近似最优解.图4说明订单数量与订单净收益之 时间逐步增加，但是平均计算时间都是在可接受范 间的关系.实验把节点数规定为4，订单数分别选择 围之内 5、10、15、20和25.关系图说明开始阶段，随着订 (②)HTHS算法三组数据中的平均接受订单 单数量的增加订单净收益逐渐增加，但是订单数达 数分别为8.8、11.0和11.2，平均净收益分别为 到20以后，订单净收益开始下降 852.7、948.1和827.1.HS算法三组数据中的平均 10007 接受订单数分别为8.0、9.8和10.6，平均净收益分 片800 别为756.2、795.3和610.6.可见，随着订单数量的 600 增加订单的平均接受数增加，平均净收益先增加后 400 HITHS 减少.因此，企业在一定时期内加工能力有限的情 200 况下，并不是接受的订单越多订单平均收益越大 0 0 10 20 30 (3)由HTHS算法和HS算法的比较可 订单数 知，HITHS算法在平均计算时间上要多于HS算 图4 HⅡTHS算法和HS算法下订单数量与订单净收益的 法，但是在求解质量上好于HS算法. 关系 图3为HTHS算法和HS算法的收敛趋势图. Fig.4 Relationship between order net income and order 实验的输入参数为订单数为10，迭代100次.纵 quantities with HITHS algorithm and HS algorithm 坐标表示订单的净收益，横坐标表示计算时间.图 5结论 3说明HTHS算法的收敛速度较之HS算法要慢一 多节点多加工路线订单接受是很多企业面对的 1000 问题，文章提出多节点多加工路线订单接受问题模 800 型，通过混合智能调谐和声搜索算法与基本和声搜 600 索算法对其进行求解，两种算法都能在有效时间内 获得近似最优解并得出订单接受状况，同时比较 400 -HITHS 了两种算法的平均计算时间和近似最优解的优劣 200 进一步的研究可以按照以下两个方向进行：(1)针 0 20 喝 对多节点多加工路线订单接受问题开发更有效的算 计算时间/s 法：（②）可考虑存储能力有限的多节点多加工路线的 订单接受问题. 图3 HITHS算法和HS算法下计算时间与订单净收益的 关系 参考文献 Fig.3 Relationship between computing time and order net income with HITHS algorithm and HS algorithm [1]Chen C S.Concurrent engineer-to-order operation in the
· 1396 · 北 京 科 技 大 学 学 报 第 35 卷 点为四个阶段. 分别利用混合智能调谐和声搜索算 法 (HITHS) 和基本和声搜索算法 (HS) 对多节点多 加工路线订单接受问题进行求解，根据订单数的不 同，将两种算法求解的实验分成三组，每组生成 10 个算例，采用平均计算时间、平均订单收益、平均订 单接受数和平均订单接受率来分析模型和评价算法. 4.2 实验结果分析 在混合智能调谐和声搜索算法和基本和声搜索 算法的算例中，通过各组生成的 10 个算例求解出各 项指标的平均值，实验结果见表 1. 由表1可知： 表 1 具有多节点多加工路线订单接受的实验结果 Table 1 Experimental results of order acceptance with multi-nodes and multi-process routes 算法 问题规模 平均计算时间/s 平均净收益/元 平均接受订单数 平均订单接受率/% HITHS 10×4 13.26 852.7 8.8 88.0 15×4 19.62 948.1 11.0 73.3 20×4 22.94 827.1 11.2 56.0 HS 10×4 11.32 756.2 8.0 80.0 15×4 18.47 795.3 9.8 65.3 20×4 21.9 610.6 10.6 53.3 (1) HITHS 算法和 HS 算法都可以在较短的时 间内求解出可行解，随着订单数量的增加平均计算 时间逐步增加，但是平均计算时间都是在可接受范 围之内. (2) HITHS 算法三组数据中的平均接受订单 数分别为 8.8、11.0 和 11.2， 平均净收益分别为 852.7、948.1 和 827.1. HS 算法三组数据中的平均 接受订单数分别为 8.0、9.8 和 10.6，平均净收益分 别为 756.2、795.3 和 610.6. 可见，随着订单数量的 增加订单的平均接受数增加，平均净收益先增加后 减少. 因此，企业在一定时期内加工能力有限的情 况下，并不是接受的订单越多订单平均收益越大. (3) 由 HITHS 算法和 HS 算法的比较可 知，HITHS 算法在平均计算时间上要多于 HS 算 法，但是在求解质量上好于 HS 算法. 图 3 为 HITHS 算法和 HS 算法的收敛趋势图. 实验的输入参数为订单数为 10，迭代 100 次. 纵 坐标表示订单的净收益，横坐标表示计算时间. 图 3 说明 HITHS 算法的收敛速度较之 HS 算法要慢一 图 3 HITHS 算法和 HS 算法下计算时间与订单净收益的 关系 Fig.3 Relationship between computing time and order net income with HITHS algorithm and HS algorithm 些，但是 HITHS 算法能够始终得到比 HS 算法要好 的近似最优解. 图 4 说明订单数量与订单净收益之 间的关系. 实验把节点数规定为 4，订单数分别选择 5、10、15、20 和 25. 关系图说明开始阶段，随着订 单数量的增加订单净收益逐渐增加，但是订单数达 到 20 以后，订单净收益开始下降. 图 4 HITHS 算法和 HS 算法下订单数量与订单净收益的 关系 Fig.4 Relationship between order net income and order quantities with HITHS algorithm and HS algorithm 5 结论 多节点多加工路线订单接受是很多企业面对的 问题，文章提出多节点多加工路线订单接受问题模 型，通过混合智能调谐和声搜索算法与基本和声搜 索算法对其进行求解，两种算法都能在有效时间内 获得近似最优解并得出订单接受状况， 同时比较 了两种算法的平均计算时间和近似最优解的优劣. 进一步的研究可以按照以下两个方向进行：(1) 针 对多节点多加工路线订单接受问题开发更有效的算 法；(2) 可考虑存储能力有限的多节点多加工路线的 订单接受问题. 参 考 文 献 [1] Chen C S. Concurrent engineer-to-order operation in the
第10期 王雷等：基于HTHS算法的多节点多加工路线订单接受问题研究 ·1397. manufacturing engineering contracting industries.Int J [10]Parsaei S,Keramati M A,Zorriassatine F,et al.An or- Ind Syst Eng.2006,1(1/2):37 der acceptance using FAHP and TOPSIS methods:a case [2]Barut M,Sridharan V.Revenue management in order- study of Iranian vehicle belt production industry.Int J driven production systems.Decis Sci 2005,36(2):287 Ind Eng Comput,2012,3(2):211 [3]Slotnick S A,Morton T E.Selecting jobs for a heavily [11]Xiao YY,Zhang R Q.Zhao Q H,et al.Permutation loaded shop with lateness penalties.Comput Oper Res flow shop scheduling with order acceptance and weighted 1996,23(2):131 tardiness.Appl Math Comput,2012,218(15):7911 [4 Ghosh J B.Job selection in a heavily loaded shop.Com- [12]Cui J S,Li T K,Zhang W X.Hybrid flowshop scheduling put Oper Res,.1997,24(2):141 model and its genetic algorithm.J Univ Sci Technol Bei- [5]Alidaee B,Kochenberger G A,Amini MM.Greedy solu- jimg,2005,27(5):623 tions of selection and ordering problems.Eur J Oper Res, (崔建双，李铁克，张文新.混合流水车间调度模型及其遗 2001,134(1):203 传算法.北京科技大学学报，2005,27(5)：623) [6 Lewis H F,Slotnick S A.Multi-period job selection:plan-[13 Nawaz M,Enscore EE J,Ham I.A heuristic algorithm ning work loads to maximize profit.Comput Oper Res, for the m-machine,n-job flow shop sequencing problem. 2002,29(8):1081 OMEGA,1983,11(1):91 [7]Slotnick S A,Morton T E.Order acceptance with [14]Tang L X,Wu Y P.A genetic algorithm hybrid flow shop weighted tardiness.Comput Oper Res,2007,34(10):3029 scheduling.Acta Autom Sin,2002,28(4):637 [8]Rom W O,Slotnick S A.Order acceptance using genetic (唐立新，吴亚萍.混合流水车间调度的遗传下降算法.自 algorithms.Comput Oper Res,2009,36(6):1758 动化学报，2002,28(4：637) [9]Cesaret B,Ogz C,Salman F S.A tabu search algorithm [15]Yadav P,Kumar R,Panda S K,et al.An intelligent tuned for order acceptance and scheduling.Comput Oper Res, harmony search algorithm for optimization.Inf Sci,2012, 2012,39(6):1197 196:47
第 10 期 王 雷等：基于 HITHS 算法的多节点多加工路线订单接受问题研究 1397 ·· manufacturing engineering contracting industries. Int J Ind Syst Eng, 2006, 1(1/2): 37 [2] Barut M, Sridharan V. Revenue management in orderdriven production systems. Decis Sci, 2005, 36(2): 287 [3] Slotnick S A, Morton T E. Selecting jobs for a heavily loaded shop with lateness penalties. Comput Oper Res, 1996, 23(2): 131 [4] Ghosh J B. Job selection in a heavily loaded shop. Comput Oper Res, 1997, 24(2): 141 [5] Alidaee B, Kochenberger G A, Amini M M. Greedy solutions of selection and ordering problems. Eur J Oper Res, 2001, 134(1): 203 [6] Lewis H F, Slotnick S A. Multi-period job selection: planning work loads to maximize profit. Comput Oper Res, 2002, 29(8): 1081 [7] Slotnick S A, Morton T E. Order acceptance with weighted tardiness. Comput Oper Res, 2007, 34(10): 3029 [8] Rom W O, Slotnick S A. Order acceptance using genetic algorithms. Comput Oper Res, 2009, 36(6): 1758 [9] Cesaret B, Oˇgz C, Salman F S. A tabu search algorithm for order acceptance and scheduling. Comput Oper Res, 2012, 39(6): 1197 [10] Parsaei S, Keramati M A, Zorriassatine F, et al. An order acceptance using FAHP and TOPSIS methods: a case study of Iranian vehicle belt production industry. Int J Ind Eng Comput, 2012, 3(2): 211 [11] Xiao Y Y, Zhang R Q, Zhao Q H, et al. Permutation flow shop scheduling with order acceptance and weighted tardiness. Appl Math Comput, 2012, 218(15): 7911 [12] Cui J S, Li T K, Zhang W X. Hybrid flowshop scheduling model and its genetic algorithm. J Univ Sci Technol Beijing, 2005, 27(5): 623 (崔建双, 李铁克, 张文新. 混合流水车间调度模型及其遗 传算法. 北京科技大学学报, 2005, 27(5): 623) [13] Nawaz M, Enscore E E J, Ham I. A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA, 1983, 11(1): 91 [14] Tang L X, Wu Y P. A genetic algorithm hybrid flow shop scheduling. Acta Autom Sin, 2002, 28(4): 637 (唐立新, 吴亚萍. 混合流水车间调度的遗传下降算法. 自 动化学报, 2002, 28(4): 637) [15] Yadav P, Kumar R, Panda S K, et al. An intelligent tuned harmony search algorithm for optimization. Inf Sci, 2012, 196: 47
