英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

加工时间不确定的随机作业车间调度的进化算法

摘要：在本文中，提出了一种在顺序优化(OO)中嵌入进化策略(ES)的进化算法（简称ESOO）来解决随机作业调度问题，以在有限计算时间内最小化存储费用和延迟惩罚为目标。首先，用一个短仿真长度的随机仿真模型作为进化策略中适应值的大致估计，从搜索空间中选出N个近似好的调度方案。然后，从被选择的N个调度方案入手，以柔化调度过程为目标，选出一个足够好的调度方案。最后，运用提出的ESOO算法来解决如下随机作业车间调度问题：在8台机器上加工8个工件，加工时间分别服从截尾正态分布、均匀分布、指数分布。并比较五种类型的派工法则在ESOO算法中的仿真测试结果，结果表明，所选择的调度方案在求解质量和计算效率方面都是成功的。

关键字：随机作业车间调度、进化策略、顺序优化、仿真优化、派工法则

1.引言

在过去的二十年，人们已经对作业车间调度问题（JSSP）进行了大量的研究。许多方法被用来解决作业车间调度问题，例如解析法、基于规则的算法、元启发式算法(Chakraborty, 2009).。解析法可以得到最优解或近似最优解，但是不能描述生产系统的随机属性(Fattahi, Mehrabad, amp;Jolai, 2007)。基于规则的算法，由于它的简洁性和有效性而被广泛地运用在实践中(Sule, 2007)。然而，并没有一个单一的最优法则适用于所有可能的情况。元启发式算法可以得到近似最优解，但是当调度问题变得复杂的时候，该算法消耗大量的计算时间(Zhang amp; Wu, 2010)。

在现实生产系统中，大多数作业车间调度问题都是随机的。随机作业车间调度问题（SJSSP）是一个NP-hard问题，它反映了真实世界的情况并且具有不确定性。关于随机作业车间调度问题的文献明显要比确定性作业作业车间方面的文献少。由于柔性生产系统的需要，调度问题中关于随机加工时间的研究已经成为人们所感兴趣的最新问题之一。Zandieh等(Zandiehamp; Adibi, 2010)提出了一种基于变领域搜索(VNS)的调度方法来描述一个考虑了工件随机到达和机器故障的动态作业车间调度问题。Renna(Renna, 2010)通过基于信息素的方法创造了一种调度方法，并通过多智能体结构将其实施。为了解决动态车间调度问题Zhou et al. (Zhou, Nee, amp; Lee, 2009)提出了蚁群优化算法对三种不同水平的机器利用率、三种不同的加工时间分布和三种不同的性能指标进行了研究。Tavakkoli-Moghaddam等(Tavakkoli-Moghaddam,Jolai, Vaziri, Ahmed,amp;Azaron, 2005)利用神经网络法提出了一种混合算法来产生初始可行解，然后运用模拟退火算法(SA algorithm)来提高初始解的质量和性能从而获得近似可行解。Lei(2010)提出了高效分解-集成遗传算法来最小化最大模糊完成时间。Gu et al. (Gu, Gu,Cao, amp; Gu, 2010)提出了竞争协同进化量子遗传算法来解决随机作业车间调度问题，以最小化预期最大完工时间为目标，但是由于概率分布并不是反映加工时间随机性的最好的方式，服从正态分布时，可能会出现负的或者零加工时间。Gholami和Zandieh(Gholamiamp;Zandieh, 2009)将仿真整合到遗传算法中来解决柔性作业车间的动态调度问题，以最小化最大完工时间和平均延迟期望为目标。Gu等 (2009)提出了并行量子遗传算法来处理SJSSP，以最小化最大完工时间为目标，其中加工时间服从独立正态分布。

上述的各种方法都需要冗长的计算时间，因为评估一个调度方案的目标就很消耗时间，更不用说在巨大空间范围搜索时启发式技术极度缓慢的收敛性。为了克服处理复杂调度问题时耗时太多的缺点，我们提出了一种在有序优化中嵌入进化策略的进化算法，简称ESOO，来在合理计算时间内寻找一个足够好的可行解。ESOO算法的关键在于一步步缩小了搜索空间，或者说通过有序算法的迭代使用来逐渐限制搜索范围(Ho,Zhao, amp; Jia, 2007; Shen, Ho, amp; Zhao, 2009)。这就像传统的爬山一样，所不同的是，ESOO算法在搜索空间中不是从一个点移动到另一个点，而是从一个子集移动到另一个子集。SJSSP问题被定义为约束随机模拟优化问题，搜索空间巨大，能够充分展现所提出的ESOO算法的有效性。为了克服概率分布带来的负加工时间或者零加工时间问题，我们将从截尾正态分布、均匀分布、指数分布这三个方面来考虑SJSSP的随机加工时间。同时使用提前和延期惩罚会提高非正规性指标（nonregular performance measure），所以我们选择提前和延期惩罚的从年初费用作为我们优化问题的目标函数。所以，本文的目的就是在有限的计算时间内，以最小化期望存储费用和延期惩罚为目标，来确立一个良好的调度方案。文中建立的数学公式是本文的第一个贡献，这些公式同样适用于具有随机加工时间、不同成本惩罚方案和费用消耗的作业车间生产系统。

本文所提的ESOO算法是又一贡献，它由探索与开发两个时期组成。在探索时期，运用进化策略来有效地从搜索空间中选择Ｎ个良好的解决方案，目标函数由一个粗略的模型来评估。为了确保能产生可行方案，在利用进化策略的过程中，我们采用了基于优先级的置换编码和修复算子。开发时期由多个阶段组成，这样通过迭代和适应性地选择候选解集来分配计算资源和预算。在每一个阶段，对遗留下来的解决方法进行评估，并剔除不好的那些，在最后阶段获得的解决方案就是我们要寻找的。

本文的其余部分按如下内容组织。在第二部分，我们提出了对于一般SJSSP问题的数学公式，并描述了问题的难点。在第三部分，我们阐述了从搜索空间中得到最优调度方案的ESOO算法。在第四部分，将提出的算法运用到如下形式的SJSSP问题：8个工件在8台机器上完成，加工时间分别服从截尾正态分布、均匀分布、指数分布。我们展示了算法得到的结果，并且通过比较已有的五种典型的派工法则论证了解决方案的质量。我们也提供了我们方法的性能分析来正式所得到的解决方案的普遍适用性。最后在第五部分，我们得出了相关结论。

2.随机作业车间调度问题

2.1问题描述

　　我们考虑机器调度问题，通常被称之为随机作业车间调度问题（SJSSP）。给定ｎ个工件，标记为Ｊ_ｉ，１le;ｉle;ｎ。每个工件由一系列操作组成，每项操作都在一个机器上在连续时间内完成。给定ｍ台机器，标记为Ｍ_ｋ，１le;ｋle;ｍ。每台机器在同一时间最多能加工一道工序。在第Ｍ_ｋ台机器上加工第Ｊ_ｉ个工件被标记为Ｏi,k，１le;ｉle;ｎ，１le;ｋle;ｍ。我们将Ｏi,k的加工顺序标记为ａi,k，这是提前给定的。Ｏi,k的随机加工时间被标记为ｐi,k，加工时间是服从以theta;i,k为均值，以delta;²i,k为方差的概率分布的随机变量。为了描述的简洁性，定义一个操作环境矢量，标记为［ａi,k，theta;i,k，delta;²i,k］，用来描述作业车间环境。交货日期，标记为di，对每个工件Ｊ_ｉ来说都是固定的。如果一个或者多个工件要在一台固定的机器上加工，并且机器是空闲的，该工件将会被立即送往机器。由于调度决策的原因，将给工件Ｊ_ｉ设定一个完工时间Ci，Ci是最后一项操作完成的时间。令Ti = max {0,Ci－di} and Ai = max {0,di－Ci}分别代表工件Ｊ_ｉ的延期和提前。

　　一个调度方案可以确定在机器上执行每项操作的顺序，并且可以由所有Ｏi,k的随机全排列（１le;ｉle;ｎ，１le;ｋle;ｍ）来表述。令Theta;表示工件间没有空余时间的一系列可行的和不可行的方案。可行方案S应该满足加工操作限制，每个工件都需要完成一系列的操作，并且满足顺序限制从而保证在给定时间在一台机器上最多加工一个工件。SJSSP的目标就是找出一个可行解Sisin;Theta;来最小化给定的目标，并满足以下条件：１）每台机器在同一时刻最多只能处理一个操作；２）每个工件在同一时间只能在一台机器上加工；３）在不同工件的操作之间没有优先约束；４）操作一旦开始不能被抢占。

2.2数学公式

　　在这一节，我们建立了描述随机环境中的一般作业车间生产系统的数学模型。如果工件Ｊ_ｉ的完成时间晚于交货期di，由于延迟将会付每单位时间ai的惩罚成本给顾客。如果工件早于交货期完成，顾客直到截止日期才会收到产品。所以系统被迫储存产品直到交货期，并且每单位时间花费beta;i的存储费用。将经济因素考虑其中，这样的模型覆盖了一系列受随机干扰影响的作业车间生产系统。

给定操作环境矢量［ａi,k，theta;i,k，delta;²i,k］的SJSSP模型可以描述为

　　　　　 　　　　　　　　　　　（１）

满足约束：

Oi,j满足加工顺序ａi,k ；

forall;Oi,jisin;S；　　　　　　　　　　　　　　　　　　　　　　　　　　　（２）

其中，f(S)表示延迟惩罚和存储费用的总和；参数ai gt; 0表示工件Ｊ_ｉ的延迟惩罚权重，aiTi表示工件Ｊ_ｉ的延迟惩罚；参数beta;i gt; 0表示工件Ｊ_ｉ的提前惩罚权重，然后beta;iAi表示工件Ｊ_ｉ的存储费用。决策者可以根据经济情况决定延迟惩罚和提前惩罚权重的值。机器利用率高的情况下，存储费用相对于未利用的生产能力造成的成本来说就是一小部分了。然而，机器利用率低的情况下，有意延迟工件完工时间将是更经济的。所以，延迟惩罚和存储费用的预期总和E[f(S)]将作为我们优化问题的目标函数。优先限制（２）确保了每个工件的工序加工顺序与预定顺序相符。任何满足约束（２）的解均为可行解。

优化问题的目标是从满足优先约束的搜索空间Theta;中找到一个可行解S，能最小化存储费用与延迟费用总和。显然，上述优化问题是一个拥有巨大搜索空间Theta;的受约束的随机仿真优化问题。由于仿真能够有效地描述操作特性，我们可以用仿真方法论来评估目标值。仿真方法的原则就是分析目标函数被仿真模型所取代。然而，为了评估可行解Sisin;Theta;的真正的目标值，需要进行无限次重复的随机模拟。虽然无限次重复模拟会使目标值稳定，但事实上，对于实际来说这是不可能的。所以，依赖于重复的次数，（１）式可以用如下形式来描述：

　　　　　　　　　（３）

Ｌ代表仿真的长度，也就是重复的次数。T_i^l和A_i^l分别代表可行解S中重复第ｌ次时工件Ｊ_ｉ的延迟与提前。目标值的样本均值F(S)，为可行解S中仿真长度为Ｌ时延迟惩罚和存储费用总和的平均值。所以。足够大的Ｌ将会使目标值F(S)的样本均值足够稳定。令Le = 10⁵表示足够大的仿真长度。在后文中，关于（３）建立的模型的仿真长度被定义为L = Le。为了描述的简洁性，令表示Fe(S)确定模型中可行解为S时目标值的样本均值。

2.3问题的难点

由于在SJSSP中，在每台机器上工件的加工时间是随机波动的，所以工件在每台机器上的加工顺序不能提前定义。即使顺序被提前定义了，由于工件实际加工时间的变动该定义将无效。分析技术只能被用来处理具有随机加工时间的作业车间调度问题的具体的情况(Fattahi et al., 2007)。仿真优化具有有效的建模能力和优化能力，所以它适用于解决这类受约束的随机仿真优化问题(Keskin,Melouk, amp; Meyer, 2010; Li, Sava, amp; Xie, 2009)。由于目标值计算的顽固性，在有效时间内优化解决SJSSP问题是不切实际的。最近一些启发式搜索方法被成功的运用在了SJSSP问题中，其中包括有蚁群优化法(ACOl) (Zhou et al., 2009),、模拟退火法(SA) (Tavakkoli-Moghaddam et al., 2005)、遗传算法(GA) (Gholami amp; Zandieh, 2009; Gu et al., 2009, 2010; Lei, 2010)等。除了上述几种启发式算法的成功运用外，Dreo等(Dreo, Petrowski, Siarry, and Taillard 2006)提出了对于更广泛的运用来说存在的技术障碍。其中最主要的障碍就是速度，因为对于一个给定的调度方案来说运用仿真来评估目标值计算量就已经很大了，更不用说在搜索空间巨大时去搜寻最优方案了。SJSSP问题的难点使得对于传统的搜寻方法来说在有效的时间内找出近似最优方案是非常困难的。另外，仿真通常碰到问题具有变异性的情况。所以，随机因素进一步完善了仿真优化问题。本文的目的就在于快速有效地解决这类受约束的随机仿真优化问题。将在下一节介绍结合了仿真和元启发式算法优势的ESOO算法。

3.在顺序优化中嵌入进化策略

像顺序优化理论(OO theory) (Ho et al., 2007; Shen et al., 2009)所表明的那样，为了以很大的概率确定好的设计方案，可以在广泛的搜索空间中迭代地抽取相适应的子空间，来分配计算资源和预算。使用进化策略(ES)迭代性地从广泛的搜索空间选出N个备选解决方案是迭代有序优化的方法。获得N个备选解决方案的启发式方法可能会依赖于一个人对于所研究系统的知识储备情况。例

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[151919]，资料为PDF文档或Word文档，PDF文档可免费转换为Word