一种用于PFSP节能优化的混合禁忌搜索算法

张雨晨, 熊福力

(西安建筑科技大学 信息与控制工程学院，西安 710055)

0 引言

随着绿色制造的全球化与生产力的提高，能源需求量日益增加，能源消耗造成的环境问题日益突出[1]。通过节能与环境保护的手段可有效地推进可持续发展政策，具有显著的经济效益和社会效益。为了满足绿色生产和客户满意度的要求，企业必须同时考虑订单接受和生产计划。订单接受与调度(OAS,order acceptance and scheduling)问题决定接受哪些订单并决策接受订单的加工顺序，根据文献[2-3]的研究，它有着与大多数车间调度问题相同的特点。置换流水车间调度问题(PFSP,permutation flow shop problem)是流水车间调度问题中一类典型的子问题，也是调度问题的研究热点[4]。它通常侧重于优化生产效率指标，如总完成时间、拖期、加权完工时间等[5-6]。而能源效率优化是企业实现可持续发展的关键因素之一，因此，进行订单选择与生产调度的统一决策，使企业能够获得更加稳定有效的决策方案。车间能效优化相关研究已有杰出成果，文献[7-8]提出同时优化能源消耗与总完工时间的多目标数学规划模型。刘向[9]提出一种混合遗传算法求解面向节能降耗的调度模型。Shabtay[10-11]提出了集成提前/拖期惩罚和交货期分配的数学模型。优化PFSP的方法有很多，如精确求解算法、构造启发式算法与智能优化算法。其中智能优化算法更适合优化PFSP，尤其是禁忌搜索[12]、遗传算法、迭代局部搜索、粒子群算法等。

本文突破了传统PFSP的角度，建立了置换流水车间订单接受与调度(PFSOAS,permutation flow shop order acceptance and scheduling)问题，旨在最大化企业生产总净利润(TNR,total net revenue)。本文于传统禁忌搜索的基础上，提出了一种节能混合禁忌搜索算法(EHTS,energy-saving hybrid tabu search)，它整合了一种能耗调整策略与交货期配置策略，实现对能耗的二次降低，加入了一种订单接受与拒绝(OAR,order acceptance and rejection)的编码方式，并设计了NEH构造启发式算法产生禁忌搜索算法的初始解，以改善算法优化质量。通过上述改进，提高了算法解决本文所提出的特殊的PFSOASP的寻优能力。通过大量实际算例的统计实验，分析了该算法的优异性能，接着描述了所提出的PFSOAS模型，并且通过实验分析了EHTS算法求解PFSOAS问题的有效性与优越性。

1 问题描述

由客户提供一批订单集合I，与订单i相关的指标分别是固定收入Ri，相同的截止日期D与交货期d，拖期惩罚权重wi，客户期望的交货期区间。PFSOAS问题通过决定接受那些订单，决策已接受订单的加工顺序与确定订单开始加工时间使总利润最大化。

1.1 相关假设与参数说明

相关假设：每台机器上每个订单的处理时间为已知且恒定的；每个阶段在同一时刻只能处理一个订单；生产过程中无抢占，即某订单只有在上一个订单完工后才可被加工；任何接受的订单只有当前阶段的完成处理后才能在下一阶段处理，准备时间为0；工作台之间缓冲区无限大；每台机器在调度开始时处于空闲状态，并且一次最多可处理一个接受的订单；机器上订单的建立时间和释放时间忽略不计。

表1 模型参数说明

1.2 PFSOAS模型

目标函数：

maxTNR

(1)

(2)

其中:TEC为对接受订单进行加工的总能源成本，ECi为加工订单i时所需的机器能耗。

(3)

(4)

s.t.：

(5)

2≤i≤n,2≤k≤m

(6)

(7)

si,k=max(ci,(k-1),c(i-1),k), 2≤i≤n,2≤k≤m

(8)

ci,k=si,k+pi,k·xi

∀i∈I,k∈K

(9)

Ci=ci,m,∀i∈Io

(10)

(11)

(12)

ci,k≥ci,(k-1)+xipi,k,∀i∈I,k∈K

(13)

ci,(k-1)≤si,k,∀i∈Io,k∈K

(14)

c(i-1),k≤si,k,∀i∈Io,k∈K

(15)

(16)

(17)

βi,k,t+γi,k,t≤1,∀i∈I,k∈K,t∈T

(18)

yi,k,t=γi,k,t,∀i∈I,k∈K,t∈T

(19)

式(5)计算拖期惩罚权重。式(6)与式(7)计算机器空闲时间。式(8)与式(9)分别计算开始时间与完工时间。式(10)表示订单i的总完工时间。式(11)表示生产效率的约束。式(12)表示交货日期的约束。式(13)表示只有在第k-1阶段处理了接受的订单后，才能在第k阶段处理接受的订单。式(14)和式(15)表示任务不可中断和机器不可被抢占，式(16)表示对订单集中每个订单进行一次接受与拒绝，式(17)确保每个阶段的所有订单仅处理一次，式(18)确保每台机器一次只能处理一个订单，式(19)表示若γi,k,t=0，则第k个机器在t时刻关闭；否则γi,k,t=1。

2 节能混合禁忌搜索算法

本文提出的EHTS算法以NEH构造启发式算法产生初始解，提出了一种OAR编码方式，同时设计了一种能耗调整策略，在保持加工所有接受订单的最大完工时间不变下，使算法在求解的过程中利用分时电价的特点，实现对能耗的二次降低，与一种交货期配置策略相结合，实现TNR的提高。

2.1 EHTS算法流程

根据以上描述，EHTS算法总体为三阶段优化过程，第一阶段用于优化总净利润，第二阶段作为节能调整阶段，降低能耗成本，第三阶段配置最佳交货期，使总净利润得到上升的空间。EHTS算法流程如图1所示。

图1 EHTS算法流程图

针对相同交货期下FPFSOAS问题的EHTS算法流程描述如下：

1)以总净利润作为目标值，采用NEH启发式算法生成初始解，初始化禁忌表；

2)对步骤1)后产生的初始解进行禁忌搜索，每次迭代计算目标值时使用订单接受与拒绝方法重新编码，更新局部最优解和禁忌表；

3)检验是否满足终止准则，若满足则终止算法迭代，解码得到相应解决方案，否则返回步骤2)进行下一次迭代；

4)解码并保存最大总净利润近优解，并计算该解决方案中每个订单每道工序的完工时间；

5)根据能耗调整策略，对高峰期两边的工序加工时间进行二次调整。

6)在交货期有效区间内进行交货期配置。

2.2 节能调整

第一阶段提出的基于OAR编码方式与NEH产生初始解的改进禁忌搜索方法，能够以较低的耗电成本生成最大总净利润的调度，但某些订单仍会产生较高的电能消耗。使用能耗调整策略调整了第一阶段优化生成的解决方案，从而避免某些订单的生产仍处于用电高峰期。

调整规则：从最后一个接受的订单的最后一道工序开始，并以逆序的方式从最后一个订单调整到从用电高峰期开始生产的第一个订单，使用这种调整策略对非高峰期的所有订单的加工顺序重新调度，并将这些工序从高峰时段移开，直到非高峰期的所有订单完成调度。节能调整流程如图2所示。

图2 节能调整流程图

2.3 交货期配置策略

本文以最大化考虑能耗成本与拖期惩罚的总净利润目标，组成总净利润的两个指标；能耗成本与拖期惩罚均与时间有关，企业可以根据总净利润的优化情况，向客户提交不超过最晚交货期的交付时间，因此交货期配置策略会对总净利润的再次提高具有一定很大的可能性。交货期配置策略从上一阶段已经调整好的非高峰期生产的第一道工序开始，保持非高峰期时段的工序不变，整体在交货期区间内移动，根据设置好的移动时间长度，寻找到使得总净利润增长的交货期。交货期配置策略的流程如图3所示。

图3 交货期配置策略

2.4 编码方式

订单接受与拒绝的编码方式为π=(πOAS,πREJ)，即拒绝订单的编码拼接于接受订单的编码之后，其中πOAS,πREJ∈{1,2, ,n}。在每一次迭代中检验每条解上各订单的完工时间是否超过交货期上限，最初I为根据针对最大完工时间和能耗成本的编码方式产生的一条解，πOAS为一个空集合，πREJ为一个空拒绝订单集，调度I中所有工件并检验每一个订单的总完工时间；若订单i在交货期上限之前完工，则从I删除订单i，并将订单i的编码从πOAS集合中的第一个有效位置开始添加；否则将订单i添加到πREJ；重复该过程，直到检测到I编码集合变为空集合。

例如6订单2工序的情况，且每个订单具有相同交货期，判断每一个订单的最大完工时间是否超过交货期上限后，拒绝最后2个订单，则该解表示为π={6,5,2,4,3,1}，其中接受订单集合为{6,5,2,4}，拒绝订单集合为{3,1}。

2.5 初始解的产生

对于置换流水线调度问题，NEH 算法是目前最有效的启发式算法之一[13]，它最早由文献[14]提出。本文使用NEH算法产生初始解。初始订单集的订单按目标值的降序排序，调度排序前两个的订单以获得部分解决方案，依次将其余订单插入当前排序中所有空位，保留目标值最优的当前排序，直至未排序的订单数为零为止。NEH算法流程如图4所示。

图4 NEH算法流程

2.6 邻域移动方式

假设π为当前解，通过两点交换或插入方式获得一定大小的当前解邻域N(π)。本文中选择两点交换和插入操作的概率相等。

两点交换：随机生成两个位置，直接交换π中两个位置上的个体以获得N(π)；

前插/后插：将随机位置上的个体插入到另一位置上的个体之前或之后。

2.7 禁忌表

禁忌表作为禁忌搜索的存储结构，可防止搜索过程中出现循环和避免陷入局部最优。禁忌表的主要指标为禁忌对象和禁忌长度。为了避免算法迭代中出现重复移动，将每次迭代的局部最优解的邻域操作放入禁忌表中，这些元素在下次搜索时将不会被考虑；禁忌表长度为禁忌表中禁忌对象的最大值，其大小会影响算法效果，通过Taguchi方法调整禁忌表长度。

2.8 藐视准则与终止准则

在本文中，当禁忌搜索算法中出现候选解全部被禁忌，或者某个禁忌候选解的适应度值优于当前最好解的适应度值，则解禁某个禁忌候选解作为新的当前最好解。

本文将最大迭代次数设置为终止准则。

3 实验结果与分析

所有实验在环境Intel® CoreTMi5-4300U，主频为2.2 GHz，内存为16 GB的个人电脑上运行，编程环境为Matlab R2017a。实验设定订单数量n为10、20、30、40或50，工序数m为6、8、10，组成15种例如10/6，20/8，30/10等形如n/m的订单规模，15种规模对应150个随机算例，每个算例运行30次。根据文献[15]，订单加工时间pi,k在[0.3, 2,5]中随机生成的，机器的不同运行方式的能耗在[2,20]内随机产生。工厂为24小时轮班式工作制，分时电价如表2所示。每种规模里所有订单的相同固定收入Ri在[1 000,2 000]内随机产生。本文用于测试同一算例的所有算法的终止条件为最大迭代次数Max_Iter=200。

表1 电铃故障模式

交货期根据所有订单的总加工时间平均值产生，如式(20)所示：

(20)

3.1 算法性能对比

大量研究表明，遗传算法(GA,genetic algorithm)、禁忌搜索算法(TS,tabu search)、迭代局部搜索算法(ILS,iterated local search)等用于求解传统PFSP是有效的。通过对比本文所提出的EHTS算法、仅加入OAR编码方式的改进禁忌搜索(ITS-OAR,improved tabu search-OAR)与传统TS算法在优化PFSOAS模型下的算法性能，分析EHTS算法的优势；并且通过EHTS优化随机实例，分析节能调整与交货期配置策略的有效性。

由于元启发式算法的性能对参数敏感，因此使用Taguchi正交实验设计法对EHTS、ITS-OAR、TS进行算法调参。调整后参数如表3所示，其中n为订单总数量，max{}为取最大值函数，round{}为取整函数，sqrt{}为开平方函数。

表3 算法调整后的参数

表4给出了15种规模实例问题在传统TS、ITS-OAR、EHTS的优化性能对比，指标分别为总净利润平均值、拒绝订单数、能耗成本平均值以及相应的总净利润增长率、能耗成本降低率。TNRbest为EHTS优化后的订单总净利润值，TECbest为加工EHTS优化解决方案所耗费的电费成本。总净利润增长率(IRTNR)与能耗成本降低率(DRTEC)分别如式(21)和式(22)。其中，TNR与TEC分别为TS、ITS-OAR优化后的总净利润值与能耗成本值。考虑到算例总数和规模总数较大，对150个算例运行30次后的优化结果取平均值进行统计实验。根据表4所绘制的不同工序下三种算法性能对比如图5所示。

(21)

(22)

从图5可以看出，在优化PFSOAS问题方面，EHTS算法的优化性能更优于传统TS算法和ITS-OAR算法。根据表4，从订单总利润的角度来看，EHTS算法对比传统TS算法，其总净利润值可以提高5%～11%左右，平均提高大约8%；EHTS算法比ITS-OAR算法优化得到的总净利润值高1%～7%左右，平均提高大约4%；说明通过能耗调整和交货期配置策略，可以使得企业订单总利润值显著提高。由于该目标中带有拖期惩罚项，会与总净利润增长相互制约，随着订单规模的增长，某些订单的生产仍处于高峰时段，总净利润增长幅度一直保持在5%左右。从能源消耗成本的角度来看，EHTS算法比前两种算法具有显著优势，能耗成本减少大约9%。拒绝订单数也相应减少。因此EHTS算法有着较好的有效性和稳定性。

图5 3种算法的性能比较

表4 不同规模下不同算法的优化结果

4 结束语

本文在传统能效优化的置换流水车间调度能耗模型角度上加入了订单接受与调度，针对问题的特殊性，提出了一种新型的节能禁忌搜索算法，提高传统算法对企业总净利润和能耗成本的优化效果，订单总净利润平均提高了13%，拒绝订单数与能耗成本也相应减少。通过NEH构造启发式产生初始解、节能调整策略的改进，可提高算法搜索效率，改善初始解质量，通过多种算法的性能对比，较单一算法相比，该EHTS算法具有较强全局搜索能力的优势，具有一定的实用价值。本文的研究内容和结论将推动绿色制造领域通过科学可行的调度方法，实现节能降耗、高效益的生产目标，具有一定的实践意义。