考虑时差电价机器能耗的非等同并行机调度研究

梁鹏 郝刚 郭建华 吴玉婷 何娃

摘要：利用时差电价减少能耗损失的同时保证最大化生产效率，是高能耗制造企业急需解决的问题之一。将其生产调度过程抽象为一种考虑时差电价机器能耗的非等同并行机调度问题，对此提出一种基于右移局部搜索的蚁群优化方法以实现求解方案。最后根据仿真实验得到蚁群优化算法的最优参数用于实验对比，从对比实验结果的分析表明，算法可以减少生产过程的能耗成本和拖期成本.

关键词：能耗成本;拖期成本;非等同并行机;蚁群算法

中图分类号：TP301     文献标识码：A

文章编号：1009-3044（2019）20-0272-03

开放科学（资源服务）标识码（OSID）：

Abstract： Aiming at hugeous machine warm-up energy consumption and serious waste product switching in aluminium extrusion workshop， we abstract it as a class of unrelated parallel machine scheduling problem with energy and tardiness cost，and an ant optimization algorithm based on product switching energy consumption heuristic rule is presented.Optimal parameters of algorithm are defined via a split-plot design for generating test data.A lot of simulation experiments prove the proposed algorithm decrease energy consumption effectively.

Key words： energy consumption; Total tardiness; Unrelated parallel machine

在现实生产制造中，不同效率的机器（非等同并行机）往往同时运行，这给生产计划制定带来了极大的困难。因此，在保证企业正常生存条件下，降低非等同并行机生产过程的能源消耗和降低生产成本，是制造业关注的核心问题之一[9].早在2004年，Pfund[3]等人就证明了最大化完工产品数的非等同并行机调度问题属于NP难问题.Allahverdi等[4]在2008年的带准备时间的调度综述文献对单机、并行机、流水车间调度进行了研究，研究发现以最小化拖期成本的调度方案倾向于将同种类型的产品成批处理.Liaw等[5]和Rocha[6]等使用分支界限法优化带准备时间的非等同并行机调度问题，然而求解方法计算复杂度过高，难以适用于数量较大的调度问题.Weng等[7]使用7种启发式规则对带准备时间的非等同并行机调度进行求解[22]。

综上所述，上述以非等同并行机能耗调度為研究目标的文献，通常将机器调度和工件调度分开独立进行以降低计算复杂度，大大减少了解空间的搜索范围，然而单纯将解空间分割会导致算法性能的下降。为此，本文提出一种右移邻域搜索策略的蚁群算法，用于求解考虑时差电价机器能耗的非等同并行机调度问题，实验结果表明，该方法减少了解空间的搜索范围的同时，提升了算法的精度。

1问题描述与数学模型

对于本文研究的非等同并行机调度问题描述如下：有n个工件由m台非等同并行机中任一台完成加工，安排在第j台机器上加工的工件数量为Hj，每个工件i都有独立的到达时间ri和交货时间di，并根据不同的加工机器有不同的加工时间tij，第i个工件的单位时间拖期成本为pi1，第j台机器的单位时间运行能耗成本和单位时间待机能耗成本分别为pj2和pj3，w1和w2分别表示工件拖期成本系数和机器能耗成本系数，f（t）表示不同时间段的电力价格。给出下面假设条件：机器在开始加工第一个工件时开启，加工过程不允许抢占或中断，每台机器任一时间只能加工一个工件。该问题的数学模型描述如下：

决策标量：

2求解算法

2.1信息素及其初始化

根据蚂蚁的两阶段寻径过程，信息素分为τj和τij两部分，τj表示机器Mj上的信息素，初始值为[τj=1M];τij表示机器Mj和工件[i]之间的信息素，初始值τij=0。

2.2解的构建

首先选择最早可以获取的机器[j*]，然后选择在机器上工件拖期成本最小的工件[i*]，最后根据工件[i]选择机器能耗成本最小的机器 ]。通过机器再选择的过程将拖期成本子目标与机器能耗成本子目标联系起来，提升算法性能。

1. 选择机器

为了增加搜索随机性，给定参数[gm0∈[0，1]]和随机数[gm]，如果[gm

2. 选择工件

根据工件个数，用禁忌表tabuk （k=1，2，…，n）记录当前蚂蚁所选择的工件，禁忌表随着蚂蚁寻径作动态调整。给定参数[gi0∈[0，1]]和随机数[gi]，如果[gi

（t）]是启发式函数，反映机器[j*]上加工工件[i]的拖期成本，优先选择综合成本最小的工件在该机器上生产;α是信息启发因子，反映了蚁群运动过程积累信息对当前蚂蚁选择的影响;β是期望启发因子，表示启发式信息在蚂蚁选择中的重视程度.

3.选择机器

对于工件 而言，最早可以获得的机器[j*]并不一定是加工该工件能耗最小的机器，因此采用迭代的方法，再次根据机器加工能耗最小选择机器

为蚂蚁一次寻径的结果，即选择工件[i*]在机器[j**]上进行加工。蚂蚁反复进行寻径，直到所有的工件加工完成，工件的加工序列即是解的序列。

2.3邻域搜索

研究表明，在蚁群算法中加入邻域搜索算法，不仅可以提高解的精度，并且可以大大减少蚁群计算的循环次数.对于具有时差电价的并行机调度问题，提出一种右移邻域搜索策略（Right-Shift Local Search），策略如下所示：

2.4 信息素更新

当蚂蚁遍历完所有的工件后，需要对当前寻径的结果上的信息量进行调整k，根据下面规则式（11）进行调整：

其中，1-ρ是信息素残留因子，表示当前迭代的寻径结果对整个蚁群寻径的影响程度，Δτij（t）表示本次迭代中信息素增量。Q表示信息素强度，在一定程度上影响算法的收敛速度，E（t）表示蚂蚁本次迭代的寻径结果。

3 數值仿真实验

3.1算例设计

影响算法性能的影响因子有：机器数量m、工件数量n、工件的加工时间tij、工件的到达时间ri、工件交货时间di和单位能耗的比率（单位时间机器开关机能耗成本与单位时间机器待机能耗的比值），每个因子的设置如表1所示。

工件的加工时间tij服从均匀分布，记为tij=U[2，30]和tij=U[2，50]两种，工件的到达时间ri、交货时间di可根据加工时间计算得到：[ri=j=1mtij/m]，[di=cj=1mtij/m]，其中c表示交货宽裕系数。本文采用单位时间机器生产能耗成本与单位时间机器待机能耗的比值pj2/pj3来反映机器能耗比例.单位时间拖期成本pi1和单位时间能耗成本pj2取从1到10之间的随机整数randi（10，1），工件拖期成本系数w1和机器能耗成本系数w2取从0到1之间的随机数且w1+ w2=1。根据表1的影响因子共组成24种仿真算例。时差电价f（t）用下式表示：

3.2仿真结果及分析

本节实验所用算法参数为[α=1]，[β=4]，[Q=80]，[ρ=0.75]，[m=100]。为了验证右移邻域搜索策略的有效性，将蚁群算法（ACO）、右移邻域搜索策略（Right-Shift Local Search RSLS）组合进行比较，每个算例进行10次仿真实验取其平均值来评价算法的有效性.以上所有算法采用Matlab R2012b仿真软件，并在CPU为Intel Core i5 2.30GHz，内存4G的计算机上进行仿真试验，能耗结果[Emin]作为结果评价指标。

从表2中可以看出，单纯使用蚁群算法的效果不如使用了右移邻域搜索策略的蚁群算法，右移邻域搜索策略方法提升了约20%。

4 结束语

针对生产中机器开关能源消耗大、拖期严重等问题，建立了以综合能耗成本和拖期惩罚成本最小化为目标的非同等并行机优化调度模型，提出了基于右移邻域搜索策略的蚁群优化算法，对算例的仿真及结果分析表明算法的有效性。

参考文献：

[1] 侯彬. 考虑机器开关的并行机调度研究[J]. 工业工程与管理， 2011， 16（2）：60-64.

[2] Keskinturk T， Yildirim M B， Barut M。An Ant Colony Optimization Algorithm for Load Balancing in Parallel Machines with Sequence-Dependent Setup Times [J]。Computers & Operations Research， 2012， 39（6）： 1225-1235.

[3] Pfunda M， Fowler J W， Guptac J N D。A Survey of Algorithms for Single and Multi-Objective Unrelated Parallel Machine Deterministic Scheduling Problems [J]。Journal of the Chinese Institute of Industrial Engineers， 2004， 21（3）：230-241.

[4]Allahverdi A， Ng C， Cheng T， Kovalyov MY。A survey of scheduling problems with setup times or costs。European Journal of Operational Research 2008;187：985–1032.

[5]Liaw C， Lin Y， Cheng C， Chen M。Scheduling unrelated parallel machines to minimize total weighted tardiness。Computers&Operations Research 2003;30：1777–89.

[6]Rocha PL， Ravetti MG， Mateus GR， Pardalos PM。Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setuptimes。Computers&Operations Research 2008; 35：1250–1264.

[7]Weng MX， Lu J， Ren H。Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective。International Journal of Production Economics 2001; 70：215–26.

【通联编辑：梁书】