英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates
Li Nie · Liang Gao · Peigen Li · Xinyu Li
[摘要]：柔性作业车间调度问题（FJSSP）是作业车间调度问题（JSSP）的推广，使得一个工序可以在多个具有相同的功能的机器上进行作业。以往关于FJSSP的研究认为所有工序在调度期间的开始就都存在。然而假设总是与实际生产不同，因为作业经常会随着时间推进而到达，并且在达到之前无法预测。本文将研究基于实时信息的动态柔性作业车间调度问题(DFJSSP)，提出了一种解决动态调度问题的启发式算法。还提出了基因遗传算法来对动态调度进行自动反应。为了评估GEP在各种处理条件下构造的反应调度策略的性能，提出了三种评估因素来对它进行模拟实验：车间利用率，到期日紧性和问题的灵活性。在模拟中调度性能指标分别是最小完工时间，平均完工时间和平均延迟时间。在大范围加工条件及性能措施上，GEP与之前的方法相比可以对基于有着作业发布日期的DFJSSP构建更有效的调度策略。
[关键词]：反应调度、动态调度、柔性作业车间调度、作业发布日期、基因表达式编程。
[引言]：作业车间调度（JSSP）是应用最广泛的典型调度类型，是一个典型的 NP 难题（Garey等人，1976），是实际车间生产调度的简化问题（Jain和Meeran，1998）。在经典的JSSP上，每个作业的每个操作必须在已经安排好的机器上处理(Baker1974; Pinedo 1995)。在实践中，经常有几个部分由于操作时间过长或是机器繁忙成为关键工序上的瓶颈。因此，操作可以在具有相同的功能的多台机器上进行。这将产生一个更复杂的问题，通常被称为柔性作业车间调度问题(FJSSP)(Ho et al. 2007)。FJSSP是JSSP的一般化，而且明显地比它更加复杂。许多随机局部搜索方法被提出来解决FJSSP，如禁忌搜索(Saidi-Mehrabad and Fattahi 2007)，遗传算法(Jensen 2003; Zandieh et al. 2010)，粒子群优化算法(Zhang et al. 2009)或蚁群算法(Li and Wang 2009; Arnaout et al. 2010)。然而，这些关于FJSSP的研究都忽略了在实际环境中的动态因素。例如，通常假定所有要处理的作业在调度开始时可用。但为了解决现实情况中的FJSSP问题，应该将可能改变系统状态和影响系统效能的实时事件考虑在内(Mavrikio-
setal.2011)。基于实时信息的动态调度研究被分为两大类：与资源相关、与工作相关的实时事件(Vieira et al. 2003)。因为在大多数的实际生产中，作业会随着时间的推移而陆续到来，而我们不能进行预测。在本文中，我们将着重研究基于实时信息的动态作业车间调度问题(DFJSSP)，其中实时事件是随着时间的推移到达的。
由于调度模型可以捕捉到与作业相关的动态因素，所以无论在理论还是实际上，伴有作业发布日期的DFJSSP都不能很好地被提前求得最优解。即使找到近似最优解都非常困难。Vieiraetal(2003) 描述了两种常见的策略来控制在有着不确定作业到达的动态环境中的生产，第一种策略是预测反应调度。他们先在最开始生成一个生产计划，然后更新原计划来对中断或其他事件做出反应，让系统性能的伤害降至最低。另一种是反应调度，会基于当前紧急的系统状态和本地信息进行部分调度。一些学者也称这种反应调度为在线调度或动态调度(Aytuget al. 2005; Potts and Strusevich 2009; Vieira et al. 2003)。应用预测—反应调度的报告研究显示，要想得到比较好的近似最优解，需要付出巨大的计算成本，尤其是在需要求解的问题规模较大的时候。因此，由于许多实际的优点，反应型调度策略在工业中的应用越来越频繁。例如，它的计算负担一般是非常低的(Aytug et al.2005)。
DFJSSP涉及到两个问题，一个是如何给作业分配合适的机器（路径问题），另一个是如何确定作业的加工顺序（排序问题）(Pezzella etal. 2008)。对于路径问题，Ho and Tay (2004)提出了基于最小等待时间的机器分配规则，这样的设置可以优先处理当前作业。对于排序问题，筛选合适的待加工工序给加工机器经常应用的是派工法则(JDRs)。很多经典的派工法则(JDRs)都是在人类经验的基础上提出的。例如，先进先出(FIFO)，最短加工时间(SPT)，最早交货期(EDD)等(Blackstone et al. 1982; Ramasesh 1990)。 Panwalkar and Wafik (1977)和Blackstone et al. (1982) 对这些人为调度规则进行了全面的调查。关于这些调度规则的一般结论是，没有适用于所有车间类型，操作条件和性能目标的规则。同时，对于人为调度规则应对环境变化的鲁棒性还知之甚少(Tay and Ho 2008)。调度程序很难确定应该使用哪些派工法则JDR来为变化的系统进行有效调度。根据特定动态环境下调度问题的特点，使用基于人工智能的方法开发定制JDR是最近的热点研究课题之一(Aissani et al. 2011)。基于GP的机器学习方法是文献中流行的方法之一。Dimopoulos和Zalzala (2001)构建了用于静态单机调度的派工法则JDR; Geigeretal（2006）和Jakobovic和Budin（2006）构建了JDRs的考虑随时间到达的实时事件的动态单机调度;Yin等（2003）考虑了单机调度中JDR构造的机器随机故障; Atlan等人（1994）和Miyashita（2000）主要考察了经典的作业车间调度; Tay和Ho（2008）着重于多目标弹性车间问题的JDR。
在本文中，我们提出了一种启发式算法来实现作业随时间达到的柔性车间的反应调度，并提出基于基因表达规划（GEP）的方法，同时构建反应调度策略来解决DFJSSP中的路径问题和排序问题，它结合提出的启发式算法生成DFJSSP调度表。本文具有以下结构：下一节将给出具有工作发布日期的DFJSSP的正式定义；“DFJSSP的启发式”介绍了具有作业发布日期的DFJSSP的启发式； “基于GEP的反应调度策略构建方法”中详细描述了基于GEP构建该问题的反应调度策略的方法；“实验和结果”对所提出方法的性能进行了评估；最后，在“结论和未来工作”一节进行总结。
问题描述
具有作业发布日期的DFJSSP描述如下：J = {|1 le; i le; n}是一组要处理的n个作业。每个作业由独立于其他作业（优先约束）的个工序（，，...，O）的预定序列组成表示作业的第j个工序，M = {| 1le;kle;m}是车间中的一组m台机器。每个工序可以在一组机器的一台机器F（）上不间断地处理。用于表示在机器Mk上的的处理时间。待处理的作业随时间到达，并且在抵达之前不能进行处理。作业的属性，例如每个工序的处理时间，发布日期，到期日，重量等，在作业到达之前是不确定的。所以有以下几个假设：
1. 工序的准备时间与工序前后顺序无关，且包含在处理时间内。
2.单独工序不进行优先处理。
3.所有机器都不出现故障。
4. 一次只能在一台机器上处理作业的一个工序。 此外，每台机器最多可以一次处理一次工序。
5.机器具有无限的库存缓冲。
6. 工作的到来时间被视为遵循泊松分布。因此，每两个工作到达之间的时间间隔遵循指数分布。
7. 机器之间没有转换时间，在一台机器上完成作业处理之后，可立即在机器上进行下一项作业的处理。
8. 每个工作都有自己的发布日期和到期日。
9. 每个作业的操作顺序都是预先设定和不变的。
调度的目标是将作业分配给适当的机器，并对分配给机器的作业进行排序，以便在满足所有约束条件的同时最小化特定性能标准。 在本文中，分别考虑了三种测量标准：
（1）
（2）
（3）
其中，，和分别表示完成时间，作业i的到达期日和截止日期。，和分别表示制造时间，平均流程时间和平均延迟时间。
DFJSSP的启发式算法
DFJSSP有两个问题涉及到作业发布日期：（1）当作业被发布时，应选择哪个候选机器来处理已发布作业的当前操作（路径问题）；（2）当机器空闲时，哪个候选工作应在机器上顺序处理（排序问题）(Pezzella et al. 2008)。DFJSSP的调度过程可以用以下启发式描述：
DFJSSP启发式工作发布日期：
CT = 0；
While (有未完成的工作) do
If (有工作被发布) do
在MAR的帮助下计算集合F（）中所有机器的优先级值；
选择具有最佳优先级值的机器；
该作业进入所选机器的队列；
End if
If (有机器空闲) do
借助JDR计算集JS（Mk）中所有作业的优先级值；
在机器上载入具有最佳优先级值的作业；
更新机器并为作业的下一个工序做好准备；
End if
CT = 1；
End while
在启发式算法中，CT抑制当前时间。MAR和JDR分别用作路径问题和排序问题的反应调度策略。MAR用于计算集合F（）中所有机器的优先级值，该集合表示可以处理作业当前工序的候选机器的集合。JDR用于计算集合JS（）中所有作业的优先级值，表示要在机器上接下来要处理的候选作业集。值得注意的是，机器的候选作业可以在当前机器上准备加工，也可以在上一台机器完成加工之后进行加工。因此，候选作业的调度选择仅限于那些，到达机器不晚于最短可用作业完成时间的作业。
在下一节中，我们将介绍一种基于GEP的方法，同时为DFJSSP构建MAR和JDR。所提出的方法简化了设计和评估候选反应调度策略的繁琐过程。
基于GEP的反应调度策略的构建方法
基于GEP的反应调度策略的构建方法框架
构建方法包括两个模块，学习模块和仿真模块。 在学习模块中，GEP被用作推理机制。模拟模块作为绩效评估者，负责对GEP中个体的评估。 首先由Ferreira（2001）提出，GEP是基于进化原理创建计算机程序的新技术。作为GAs（Goldberg 1989）和GP（Koza 2007）的继任者，它也是一个进化算法，因为它使用个人群体，根据适应性选择他们，并使用一个或多个遗传算子引入遗传变异（Ferreira，2001）。GEP使用固定长度的染色体线性串（基因组）来表示不同形状和大小（phenome）的表达树（ET），这使得GEP比以前的进化算法更加通用（Ferreira 2001）。
GEP开始于初始种群，其由随机生成的多条染色体组成。这些个体被传递到描述生产环境的模拟模块，并且使用一个或多个性能的定量测量来评估。然后，从每个个体获得的绩效指标的价值作为其适应度被传回。 根据适应度，通过一系列进化搜索运算符（参见“遗传运算符”），对上一代群体中的个体进行了复制和修改，形成了新的群体。新一组个体再次传递给模拟模块，从而可以评估新个体的表现。重复这一周期，直到终止条件得到满足为止。基于GEP的方法框架如图1所示。
图1.基于GEP的反应调度策略构建方法框架
定义元素集
GEP的每个染色体在搜索开始时随机生成，并在与特定问题域（即论文中的DFJSSP）相关的功能集（FS）和终端集（TS））的元素的进化过程中进行修改。元素集合所能构建的所有染色体组成搜索空间。可用元素的集合是先验定义的。 GEP使用这个预定义的元素来发现现有问题的可能解决方案（即本文中的MAR和JDR）。因此，FS和TS的适当要素的选择是实施学习过程的关键一步，对GEP的学习能力有显着的影响。根据文献中的MAR和JDR (Blackstone et al. 1982；Ho and Tay 2004；Holthaus and Rajendran 1997；Ramasesh 1990) 以及我们的工作成果，本文中使用的FS和TS构建了DFJSSP的反应调度策略，如表1所示。TS被分为TS-R和TS-S两个子集。TS-R与FS一起用于建立路径问题的MAR。TS-S与FS一起用于构建用于排序问题的JDR。
表格1.本研究中使用的功能和终端的定义
含义
FS
, –, *, 分别表示相应的算术功能
/ 有保护机制的除运算，当被零除时，返回1
TS-R
CT (a) 当前时间，特定作业被释放的时间，需要选择一个机器来处
TWKf (b) 在机器上处理的作业的总工作内容
NOPf (h) 在机器上处
全文共7455字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144255]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
