延长柔性工作车间调度模型,飞行甲板调度优先级,并行操作,和序列的灵活性

文摘

支持操作的高效调度飞机在航母飞行甲板上是至关重要的,甚至几秒钟的改善可能会导致一场完全相反的结果。在本文,我们改善的支持操作舰载飞机和调查三个同时操作关系在支持过程中,包括优先约束,并行操作,和序列的灵活性。此外,多功能飞机要起飞协同合作和参与战斗。然而,他们起飞秩序必须限制性地优先调度期间给予某些操作规定。有效地优先起飞订单同时最小化总时间预算总体上起飞时间,我们提出一种新颖的混合整数班轮编程配方(MILP)飞行甲板调度问题。出于MILP的硬度,我们设计一种改进的微分进化算法结合典型的局部搜索策略来提高计算效率。我们数值比较算法的性能与经典的遗传算法和正常的微分进化算法,结果表明我们的算法获得更好的调度方案,可以满足业务关系和起飞的优先级要求。

1。介绍

在战斗时,舰载飞机起飞一波,一波。第一波飞机起飞的操作通常是以来最复杂的几种类型的舰载飞机要起飞表现为协同作用。在起飞之前,每个舰载飞机需要一定的支持操作,例如,检查、收费,加油,武器挂载。同时可以执行一些操作,包括润滑和武器挂载。所有飞机都不需要等待他们的订单,因为这类操作可以由一些不同的处理支持组在同一时间。然而,一些其他操作不能在同一时间处理。例如,氧气和充电加油不能同时处理由于安全问题,因此飞机必须被处理。因此,后者支持业务类反过来会影响飞机的起飞的优先级顺序和进度等有效支持组织是很重要的,所有的舰载飞机起飞的时间范围最小。调度问题通常称为“甲板调度”,它可以被视为一个扩展的柔性工作车间调度问题(FJSP)结合一些实际的限制。

作业车间调度问题(JSP)属于经典的组合优化问题,是众所周知的是np困难(1]。(FJSP)的柔性工作车间调度问题是一个扩展的JSP (2]。然而,传统的JSP和FJSP模型不考虑调度的典型特征的舰载飞机在甲板上,包括以下。

首先,在大多数JSP和FJSP模型,他们通常限制在每个操作的优先工作,但不考虑优先级的工作,这意味着任何工作可以比别人早完成。然而,航空母舰的甲板上,第一波舰载飞机可能包括直升机、预警飞机,起飞和战斗机,还有严格的订单不同的舰载飞机。按照操作规定,直升机必须首先起飞,然后预警飞机,战斗机,这使得很难安排支持资源。

第二,在大多数JSP和FJSP模型,业务工作的优先级是预先确定的,不能改变。在甲板调度,一些操作的舰载飞机可以处理其他操作之前或之后,这将增加调度的灵活性。例如,甲板的航母,舰载飞机需要氧气和油,并允许电荷氧首先,然后油,反之亦然。但是为了安全,不能同时处理两个操作。

第三,业务处理在大多数JSP和FJSP一个接一个,但在支持舰载飞机的工作,它将需要很长时间才能收取石油和武器配置顺序。为了节省时间,可以同时处理两个操作。

我们所知,只有少数研究考虑上述三个典型特征在一个调度问题。我们应对这些挑战的扩展FJSP (EFJSP)优先级、并行操作,和序列的灵活性。基于FJSP,我们提出一个新颖的MILP模型问题。然而,当典型的限制纳入模型中,一些现有文献中的算法可以有效地解决它。出于硬度,我们开发一个改进的微分进化算法结合典型的局部搜索策略。通过使用一些实用的实例飞行甲板调度和随机的情况下,我们比较算法的性能与普通遗传算法和微分进化算法。此外,我们还分析了影响局部搜索策略的性能。

2。文献综述

FJSP已被广泛研究,但大多数当前的文献研究的调度问题涉及一个或两个以上三个特点,即优先级、并行操作,和序列的灵活性。Alvarez-Valdes et al。3]介绍了一些操作,可以同时处理在玻璃生产;与本地搜索启发式算法结合优先级规则提出了最小化的优化标准,基于最早完成和延迟惩罚。Vilcot和Billaut4]讨论了印刷行业的工艺特点,每个操作都有至少一位前操作,但只有一个后续行动,在一个完整的过程,一些操作可以同时进行。Ozguven et al。5]介绍了一个相对简单的整数规划模型,一份工作可以选择一个可行的一些反向路由设置。然而,一旦确定了工作的过程中,没有操作可以同时处理。Birgin et al。6]提出的MILP模型的扩展版本FJSP,允许优先被任意给定的有向无环图,而不是一个线性顺序的操作工作,并与[5),结果表明该模型的准确性。Birgin模型(6),Birgin et al。7)提出了调度算法来解决问题列表,进一步延长过滤定向搜索方法。实验结果表明,这两种方法的效率和效果都很好。

FJSP,每个操作在不同的时间可以处理一些机器。如果工作的几种工艺路线,选择其中的一个叫做工艺设计。起初,工艺设计优化的足够的资源,但事实表明,这不能充分利用资源。因此,Saygin和科里奇(8)建立结合工艺设计与生产调度的集成模型,其中包括5个阶段:灵活的流程分解,机床选择、流程优化、调度和重新安排。有一些类似的模型,如二级模型(9),两级模式10),灵活的流程选择模型(11),和混合整数规划模型5]。然而,在这些研究中,一旦选择流程路线,确定订单的操作,用JSP和FJSP没有本质区别。

也有一些研究飞行甲板调度;瑞安et al。12)设计了一个交互式局部和全局决策支持系统命名甲板操作行动策划人航母甲板调度。他们应用反向强化学习方法13基于排队网络[]和策略优化14在飞机自适应多级调度问题,并通过甲板操作仿真,基于整数的调度性能优化线性规划模型与传统的专家启发式规则(15]。根据舰载飞机支持的不同组织不同的发射模式舰载飞机需要,魏et al。16]介绍了两架舰载飞机支持调度模型的基础上,合理的假设和适当简化:舰载飞机支持调度模型的滚动地推出舰载飞机在航母(17)和延期舰载飞机模型支持基于任务(18]。这两个模型是解决基于FJSP理论和重新安排理论,分别。根据单载波飞机的支持过程的约束,多载波的多目标集成支持调度模型飞机建立了汉族et al。19),一些操作可以同时处理。

从上面的评论,可以看出,大多数研究都关注的三个特征,而很少有研究同时考虑这三个特性。因此,舰载飞机的支持过程中产生调度问题是一个新古典FJSP的延伸。

本文的其余部分组织如下。节3,将会提议一些定义;新模型形式化。节4,改进后的算法扩展的详细说明。计算结果和分析提供了部分5。最后,我们总结论文部分6。

3所示。制定EFJSP模型

舰载飞机的甲板调度安排一些支持团体完成操作准备好飞机,让他们尽快起飞。通常有一组操作完成舰载飞机起飞之前,如检验、充电、加油,武器挂载。每个操作必须由一个支持组从一组选择的候选人的效率是不同的。也有操作规则限制的顺序为不同类型的飞机起飞;比如,直升机必须在所有其他飞机起飞。此外,一些操作的顺序可以交换。例如,允许充电氧处理之前或之后加油,但不是在同一时间。调度可以分解为两个子问题:决定一个序列的测序子问题对所有操作和路由子问题,选择一个适合每个操作的支持小组。目标是找到一个最小化最大完工时间的安排。

我们可以看到比FJSP EFJSP更复杂:首先,EFJSP,不同的工作有不同的优先级,最后操作的优先级更高的工作必须完成比别人早较低的优先级。第二,可以同时处理工作的一些操作,比如操作在图1和图21。第三,一些操作的工作可以通过交换处理他们的偏好顺序,在图1可以交换,操作4和5。

一些定义将基于这些特性提出了前面提到的。

定义1(工作)。所有支持操作的舰载飞机视为工作。

定义2(优先级)。许多工作需要做,早应该完成更重要的工作。然而,对于高优先级的工作,但这并不意味着每个操作必须比别人早完成;为了充分利用支持团体,它只是要求最终的操作必须比别人早完成较低的优先级。

定义3(并行操作)。没有先例的一些操作之间的关系在一个工作,可以同时处理。

定义4(灵活性)序列。这意味着有两个操作工作;他们是邻居,可以改变先例约束但不能同时处理。

因为比FJSP EFJSP更为复杂,因此也是np难。在细节,以下假设:制造(1)所有可用的支持团体在时刻0。(2)处理所有的工作在时间为0。(3)只能处理一个操作一个支持小组。(4)必须完成每个操作不中断一旦它开始。(5)有些操作工作的优先级是预定义的,不能改变;他们可以交换一些订单的偏好。(6)支持团体的建立时间和传输时间的操作是可以忽略不计。

以下指标,设置和参数用于新模型: :就业指数 :指数操作 :指数支持组 :数量的工作 :的操作工作 :设置支持组 :操作的工作 操作:设置支持团体可以加工, 操作:立即工作的前任 :处理时间如果操作是由支持集团 :一个很大的正数

决策变量 :操作的起始时间 :操作的完成时间 如果支持组:1是分配给操作;0,否则 :1如果操作将之前操作操作都是由支持处理组在哪里;0,否则 :1如果操作前处理操作在工作;如果操作前处理操作在工作

制定成一个MILP EFJSP。数学模型如下: 如果优先级高于,然后

的目标函数是极小化问题。约束(2)确保操作不中断。约束(3)保证手术处理由一个支持小组。约束(4)描述了操作优先约束。约束(5)- (8)确保操作不能同时处理同一个支持组。约束(9)显示工作更高的优先级比别人早应该完成较低的优先级。约束(10)允许一些操作交换优先顺序,但是不会同时处理的操作。

与FJSP模型相比,EFJSP模型包括更多的约束,如约束(4),并行操作;约束(9),优先考虑;和约束(10),序列的灵活性。

4所示。提出了改善DE EFJSP模型

FJSP,当工作的数量很小,一些具体算法可以用来解决这个问题,例如,brand-and-bound [20.- - - - - -23),数学规划(24- - - - - -26),和拉格朗日松弛27- - - - - -30.]。但当就业人数上升,很难在短时间内找到最优的解决方案。许多研究人员解决FJSP启发式方法,如遗传算法(GA) [31日- - - - - -34],蚁群算法[35),粒子群优化(36),禁忌搜索(37],蛙跳算法[38],蜂群算法[39),差分进化(DE)算法(40- - - - - -44[],迷因算法45,46]。一些文献研究各种算法的组合或与本地搜索算法来获得更好的性能,如微分进化算法结合遗传算法(47),结合模拟退火粒子群优化(48),和禁忌搜索结合本地搜索49]。但是这些算法不能直接解决EFJSP模型,应该探索和新的改进算法。

德是一个Storn和价格提出的优化算法(50求解切比雪夫多项式,编码的染色体浮点矢量在连续空间。DE算法是一种基于人口、智能优化方法的搜索整个人口空间的帮助下个体差异的干扰格式化,并寻求问题的最优解在贪婪的竞争机制。DE算法控制参数少,易于理解和实现。由于其高可靠性、健壮性和良好的性能,在优化领域得到了广泛的应用。有一些作品使用DE算法解决FJSP和JSP (40- - - - - -44),这显示了DE算法与其他算法相比的优点。FJSP EFJSP问题是一个扩展,我们做了一些改进德通过整合当地的研究更有效的策略来解决我们的问题。德的基本框架是一样呈现在图2。

4.1。编码

EFJSP模型可以分解为两个子问题:测序和路由。因此,染色体包含两部分;更具体地说,第一部分(第1部分)是决定一个操作顺序的排序在工作,所有工作的操作程序;第二部分(第2部分)的路由分配每个操作一个适当的支持。一些作品51,52)已经完成测序的方法和路由。

以下4.4.1。操作程序

所有操作的数量计算。让一个数字(从1)表示每个操作的ID, ID的和一个较小的值意味着更高的优先级的工作。

EFJSP表所示的一个例子1作为一个例子,业务工作的先例约束如图11和的先例约束操作工作2和3班轮。在表1,有3个支持组:,,。输入表的每个条目表示操作的处理时间相应的支持组织。标记“-”意味着一个支持团体不能处理相应的操作。表的ID2表示表的实例1。

第1部分的代码可以随机生成的id列;第1部分的长度。在表的实例1作为一个例子,假设有一个随机的操作程序:1 =,()是直接操作的先例();很明显,工作2中的序列打破了先例约束;因此,第一部分代码应该改变。

4.1.2。支持小组作业

按照操作顺序,每个操作应该选择一个支持组在选择支持组集。实例表1作为一个例子,假设1是一部分,“7”表示操作数量,它可以处理或;如果操作处理,那么相应的基因第2部分中“2”。可能支持组分配表所示3。染色体是由第1部分和第2部分。

4.1.3。IDs的工作更高的优先级

在EFJSP模型中,一些工作有更高的优先级,必须之前完成;因此,id应该分配给优先级高的工作。染色体不能满足规则应该放弃。

4.2。解码

4.2.1。准备的染色体解码一个活跃的调度

解码是将染色体转换为一个可行的解决方案;主要有三个解码方法:活动安排,半活性调度,nondelay调度。一些作品53,54]发现,最优调度达到极小化的目标是一个活跃的调度;因此,我们的染色体解码一个活跃的调度。的步骤如下所示。

步骤1。设置。

步骤2。取第1部分中th基因并将其转换为操作;然后选择th基因在第2部分中,将它转换成支持组;处理时间是哪个操作处理的支持。

步骤3。如果操作是第一个支持集团要处理的吗,;否则我们会发现所有的空闲时间间隔支持组。

步骤4。如果空闲时间间隔的长度比根据(16),操作应该插入间隔;否则,它应该支持小组的最终分配。

第5步。重复步骤2到4,直到所有操作的第1部分已经处理。

4.3。初始种群

种群初始化是至关重要的,因为它会影响算法的收敛速度和质量的解决方案。在本部分中,我们提出一个方法来将每个操作分配给一个合适的支持小组。方法侧重于支持组织的处理时间和工作负载,即全球任务,这是一个改进的工作(52];的步骤如下。

步骤1。创建一个新的数组来记录每个支持组的工作时间;初始值设置为0。

步骤2。按照订单顺序;从第1部分手术。

步骤3。添加每个替代的处理时间支持组数组中相应的位置;那么相应的支持小组用最短的时间将会被选择操作;如果有一些支持团体与相同的最短时间,最低的一个处理时间应该选择。

步骤4。选择支持组的顺序选择支持组的设置将被添加到相应的基因第2部分。

第5步。数组中,修改选择支持集团的总工作时间,让其他人不变。

步骤6。继续第1部分中,重复步骤3到6,直到所有操作处理。

4.4。突变

突变,德不适合离散问题;以下两种方法应用:痘(优先级操作交叉,痘)[55)和MPX(多个点交叉,MPX) [56]。痘继承的特点从父母染色体孩子染色体操作程序;MPX凌日的功能支持从父染色体组分配孩子染色体。

4.1.1。痘

优先级操作交叉过程交叉操作在父染色体序列,和支持小组作业对孩子染色体保留。这个过程如下。

首先,工作的集合分为两组随机互补和非空的:,。

第二,岗位设置的所有操作从“父母与他们分配支持组复制1”“孩子1”染色体,染色体和所有岗位的操作集与他们的支持分组从“家长2”染色体复制到“孩子2”染色体。

第三,岗位设置的所有操作与分配支持组复制从“家长2”“孩子1”染色体,染色体和岗位设置的所有操作与他们的支持分组从“家长1”染色体复制到“孩子2”染色体。

把表1作为一个例子,痘如图的过程3。

10/24/11。MPX

多点交叉过程的支持小组作业在父染色体,操作程序是保留给孩子染色体。这个过程如下。

首先,一个整数集包含0和1是随机生成的,等于长度的染色体的半身像。

第二,分配的操作及其支持组织的位置对应于0从“家长1”染色体复制到“1”孩子染色体。

第三,选择在“父1”染色体的位置对应于1集这些操作和分配支持团体“父2”染色体复制到“儿童1”染色体。

同样,“孩子2”的染色体,分配的操作及其支持组织的位置对应于0从“家长2”染色体复制。然后,选择在“父2”染色体的位置对应于1集“父母,这些操作和分配支持团体1”染色体复制到“孩子2”染色体。把表1作为一个例子,MPX如图的过程4。

染色体的变异是由 在哪里,是th染色体的th人口,是th染色体的th突变的人口,比例因子,是十字架的象征;的计算(17)是由两部分组成:18)和(19)。

方程(18)表示两个父染色体之间的差别向量;是一个0到1之间的随机数。当排序的操作,将交叉痘。当分配支持团体,将交叉在MPX方式。

方程(19)表示父染色体交叉的过程差异向量。我们计算使用的方式。

4.5。交叉

突变后,交叉算子应用于生成试验向量如下: 在哪里是一个交叉参数控制人口的多样性,表示0和1之间的一个随机数,和交叉的过程如图5。当我们获得,有些工作需要做重复数据删除和完成的解决方案。新染色体的结构应保证一定的优先级操作。

4.6。选择

选择算子是试验来决定是否使用向量的成员的人口是下一代,可以被描述为哪一个 在哪里目标函数是最小化。因此,试验向量将取代相应的目标向量在下一代如果其目标函数值不大于目标向量;否则,目标向量仍在人口。

4.7。局部搜索算法

在本部分中,提出了一种基于社区的本地搜索算法结构,提高调度。和社区结构是基于关键路径的析取图,这是一种表示调度。

4.7.1。析取图

析取图(25FJSP)是一个重要的公式,表示一组的所有节点,每个节点代表一个操作在EFJSP(包括虚拟起始和终止操作);代表了连接弧连接两个相邻操作在一个工作,和方向代表了加工顺序之间的两个连接操作;表示所有分隔连接两个相邻弧操作由同一处理支持组和他们的方向显示处理订单。每个操作的处理时间一般标注在相应的节点和被视为节点的重量。在图6,,支持集团的处理,,,,支持集团先后执行的吗,,,,支持集团的执行。

EFJSP的调度是可行的,如果没有对应的析取图中循环路径。如果一个析取图是无环,起始节点之间的最长路径和结束节点被称为关键路径的长度定义为极小化的调度。关键路径上的操作是至关重要的操作。例如,析取图见图6是一个可行的调度和无环,其关键路径是什么最大完工时间,48。在这里,我们定义从节点的最长路径到节点。

4.7.2。社区结构

社区结构是本地搜索的关键,能有效指导算法的搜索,避免盲目搜索。JSP的社区结构旨在充分利用空闲时间在支持组。FJSP,应该考虑另一个因素,这是支持的任务组。EFJSP,优先级的工作,并行操作,操作顺序会影响社区结构的灵活性。因此,一个新的本地搜索算法将基于工作(57]。从关键路径定义的时间安排,所以只有关键操作应该用于搜索空闲时间选择支持组的设置和实现本地搜索。

本地搜索算法中使用以下符号: :关键的操作 :设置直接操作的先例 :立即成功操作 :最早的起始时间 最早的完成时间 :最新的起始时间 :最新完成的时间

选择支持组的空闲时间可分为两种类型:(1)当前支持组的空闲时间处理和(2)的空闲时间在其他支持组织替代支持组的组。因此,移动的也是两种类型:(1)在当前支持组和其他支持组(2)。每种类型的空闲时间对应于一种本地搜索。

第一级本地搜索是移动在当前支持组。

众所周知,每个操作开始之前,必须完成的,必须在每个操作的开始之前完成吗。的最大时间间隔处理是。

假设操作和是邻居,处理相同的支持组。最大的空闲时间间隔和是;如果集的交集和不是空的,它可以减少时间的插入吗之间的和。所以移动状况在当前支持组(22)[33]:

第二级本地搜索是移动到其他支持组。

同样,操作,是邻居;处理的支持不过程。处理时间如果吗处理。如果集之间的交集和比,那么它可以减少插入的时间之间的和。因此,移动状况其他支持组是(33] 移动后的调度可能不是可行的关键操作;重要的是要找到能保证调度的可行性的条件,当我们正在关键操作。工作(58)提出了两个规则的调度,确保FJSP移动关键操作时是可行的;我们将改善这些规则EFJSP模型。

4.7.3。为移动操作规则在当前支持组

定理5。对于EFJSP的可行调度模型,操作,处理同样的支持组和有先例;如果满足下列条件之一,那么当成为了立即的成功操作调度仍然是可行的:(1)最后操作的工作,准备好了吗是空的;(2),,,一组非空的;(3)如果和操作的工作,他们可以交换。
的证明(1)和(2)可以指(58]。(3)条件下,当操作和交换,不影响其他操作,工作还可以加工,所以调度是可行的。

定理6。对于EFJSP的可行调度模型,操作,处理同样的支持组和有先例;如果满足下列条件之一,那么当立即成为先例的操作调度仍然是可行的:(1)第一个操作的工作,准备好了吗是空的;(2),,,一组非空的;(3)如果和操作的工作,他们可以交换。
的证明(1)和(2)中可以看到58)和(3)是一样的证明定理5。

4.7.4。其他支持团体规则移动操作

定理7。对于EFJSP的可行调度模型,操作,是邻居,处理相同的支持小组,然后呢直接操作的先例吗;支持组是另一种支持组将之间插入和;如果同时满足以下两个条件,那么调度仍然是可行的:(1)最后操作的工作,准备好了吗是空的,或,,,一组非空的;(2)第一个操作的工作,准备好了吗是空的,或,,,一组非空的。
证明可以称为(58]。

4.7.5。局部搜索算法

移动后的三个定理,获得的调度的关键操作是可行的。详细的过程从描述的社区结构是获得可接受的调度算法1。

4.8。改善与本地搜索

本地搜索的改进DE是描述如下。

步骤1。设置大小的人口,比例因子,交叉概率和最大数量的后代。

步骤2。初始化种群,当分配支持团体,染色体的数量选择支持小组与全球分配的方法,和其他人支持组随机选择他们。

步骤3。评估每一个染色体。

步骤4(突变)。生成捐赠者向量,。

第五步(交叉)。生成试验向量,。

步骤6(选择)。确定目标向量,下一代,通过一对一的选择运营商。

步骤7(本地搜索)。选择考的染色体是最大的一个,染色体,执行本地搜索,如果找到一个新的染色体的考比一个小,那么它将会被新的取代染色体。

步骤8。如果,然后重复步骤来;否则,停止。

5。实验设计和计算结果分析

为了改进微分进化算法的性能分析与局部搜索策略(IDE&LS)提出了部分4,我们通过一些实际的测试算法实例从飞行甲板调度。所有实例也解决了普通遗传算法(GA),差分进化(DE)算法和改进的微分进化算法(IDE)没有本地搜索策略;他们的计算结果相比,该算法。编码的遗传算法和德,支持集团是随机选择的,和染色体不解码一个活跃的调度。

5.1。实验设计

所有的方法都是在MATLAB中实现2013 (a) 2.50 GHz Intel Core i5 - 3210 m CPU, 4 GB内存,Windows 7.0。有五个实例的基础上,飞行甲板调度。在每个实例中,有5种舰载飞机,其中包括一架直升机(1号),一个警告飞机(2号),一个护航战斗机(3号),一个反潜飞机(图4),和一些攻击战士。在不同的情况下,攻击战斗机的数量是不同的。

实例1。有四个攻击战士(数字5 - 8)。

实例2。有六个攻击战士(数字5 - 10)。

实例3。有八个攻击战士(数字5 - 12)。

实例4。有十个攻击战士(号码为5 - 14)。

例5。有十二个攻击战士(数字5-16)。

飞机起飞的直升机,警告,护航战斗机,反潜飞机和攻击战士。支持操作如图的舰载机7;有12个操作(l,数字1 - 12)支持舰载飞机,但一些舰载飞机是不同的;例如,直升机和飞机警告没有武器挂载,直升机不需要弹射器。

有30个支持组织;每个支持组的操作过程和处理时间(分钟)如表所示4。

不同的种群大小和迭代测试和计算结果表明,算法收敛快,人口规模和迭代。其他参数的算法,59)提出了一些经验值交叉概率,变异概率,和GGAP GA,60]显示比例因子的值和交叉概率在大多数情况下德。根据他们的研究,我们进行了一些参数值的灵敏度分析,帮助我们找到合适的价值在我们的问题。

图8介绍了为解决IDE&LS实例计算结果3,当比例因子的值从0.1到0.9不等。考是结果的平均值100倍的运行算法。可以看出,当获得最好的解决方案是。图9礼物的价值的结果变化从0.1到0.95,我们可以看到,获得最佳的解决方案。同样,我们估计其他参数的值。因此,对于德、IDE和IDE&LS,我们集,,,,而对于GA,我们组,,,,。

5.2。实验结果和分析

每个方法在每个实例运行100次;计算的平均结果,实验结果如表所示5,“考”的对象(分钟)。

表5总结四种方法的平均表现在五个实验实例。最好的结果提出了大胆。最好的结果的显著改善竞争对手用星号表示(两个示例t以及在默认0.05显著性水平),紧随其后价值在括号中(61年]。从表中我们可以看出5,IDE&LS总是最低的平均值和统计比GA和德在所有设置。较先进的IDE, IDE&LS(81.10)仍然有统计值低于IDE(83.40)在第五。这些结果表明了该方法的好处。

例如5,每个方法实验结果之一是选择随机从100年及其收敛曲线如图10。

从上面的计算结果,我们可以看到IDE&LS比遗传算法可以获得更好的解决方案,德,没有本地搜索和IDE,它也收敛速度远远超过其他方法在相同的迭代次数。这是因为IDE&LS在初始化过程中,我们利用一些启发式策略来生成更好的和可行的染色体,这些都会增加开始算法的搜索效率。此外,本地搜索策略集成方法有助于改善质量的每一代的染色体,而提高搜索质量。

军事行动,支持组不同情况下的调度计划通常由在战斗开始之前,指挥官关注更多的最优方案。因此,在上面的分析中,我们比较了算法的平均时间而忽略了计算时间。我们的计算实验表明,即使是规模最大的实例,IDE&LS的计算时间不超过11分钟,这是合理的,可以满足军事行动的要求。

5.3。一个可行的调度方案

为了检查优先级、并行操作和顺序的灵活性,一个调度甘特图的实例5是由IDE&LS;如图11,纵轴代表支持组的数量,水平轴代表处理时间,第一或前两位数字表示的舰载飞机的数量,和后两个代表的数量操作:例如,“507”表示操作7操作(G)的舰载飞机5和“1203”表示操作3(操作C)的舰载飞机12。

结果在图11显示如下:(1)有一些垂直的线,这意味着舰载飞机没有操作:例如,“112”表明,1号舰载飞机没有操作12(操作G),这是符合现实:直升机不需要弹射起飞。(2)起飞时间排序操作(G)是根据直升机(1号),预警飞机(2号),护航战斗机(3号)、反潜飞机(4号),和战士(数字5 - 12),因为战士具有相同的优先级,所以任何人的允许首先起飞。(3)在每一个舰载飞机的维护,同时有一些操作正在处理。(4)对舰载飞机与更高的优先级,并不是所有的操作都必须提前完成这些较低的优先级,只要最后一个手术可以早些时候完成。例如,(1)应该起飞的直升机首先,然后警告飞机(2号),但在图11、操作的预警飞机比直升机早处理。(5)操作操作4 (D)前处理操作5(操作E)对于一些舰载飞机,如数字2、6、8、12、13和14;其他人是相反的。总之,调度是可行的。

6。结论

在本文中,我们研究了一个复杂的调度问题来自舰载飞机甲板调度支持业务,优先约束,并行操作,应考虑序列的灵活性。这样的调度问题也经常出现在巨大的生产和维护项目,像飞机,船,它的引擎。EFJSP模型建立了制定调度问题,并提出了一种改进的微分进化算法来解决这个问题。首先,与最短的时间被初始化的代码和负载平衡策略,随机产生的和优先级策略也集成。其次,解码完成的活动安排,反映了并行,灵活的操作的特点,POX交叉和氧化物十字架被用于制造染色体突变。基于实际的甲板调度实例用于测试该模型和算法。计算结果表明,我们的解决方案的方法可以在合理的计算时间提出更好的解决方案。

除了典型的飞行甲板调度问题,本文发展的方法还可以扩展到其他类大项目生产、维修调度问题,如飞机,船,它的引擎。

本文研究的问题是一个新的,我们解决它通过改进的微分进化算法。然而,许多其他的算法可能改善,用于解决甲板调度问题,比如蚁群算法,粒子群优化、蛙跳算法,和蜜蜂蜂群算法。因此,它是一个重要的扩展工作这些算法的改进,使它们能够解决该甲板调度问题和与IDE本文算法相比,这可能有助于在未来找到更高效的算法。

相互竞争的利益

作者宣称没有利益冲突。

确认

这项研究得到了国家自然科学基金。61273322。

引用

1. m·r·Garey d·s·约翰逊,r·塞提“flowshop和jobshop调度的复杂性,运筹学的数学,1卷,不。2、117 - 129年,1976页。视图:出版商的网站|谷歌学术搜索|MathSciNet
2. p·布鲁克和r . Schlie作业车间调度与多功能机器,”计算,45卷,不。4、369 - 375年,1990页。视图:出版商的网站|谷歌学术搜索|MathSciNet
3. r . Alvarez-Valdes要塞,j . m . Tamarit g .,, r·拉莫斯“启发式调度灵活的作业车间在一个玻璃工厂,”欧洲运筹学杂志》上,卷165,不。2、525 - 534年,2005页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
4. g . Vilcot J.-C。Billaut”,禁忌搜索和遗传算法求解bicriteria一般作业车间调度问题,“欧洲运筹学杂志》上,卷190,不。2、398 - 411年,2008页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
5. c . Ozguven l . Ozbakır, y•“作业车间调度问题的数学模型和路由和处理计划的灵活性,”应用数学建模,34卷,不。6,1539 - 1548年,2010页。视图:出版商的网站|谷歌学术搜索|MathSciNet
6. e . g . Birgin p . Feofiloff c·g·费尔南德斯·e·l . de Melo m . t . Oshiro和d . p . Ronconi”MILP模型柔性工作车间的一个扩展版本问题,“优化信,8卷,不。4、1417 - 1431年,2014页。视图:出版商的网站|谷歌学术搜索|MathSciNet
7. e . g . Birgin j·e·费雷拉,d . p . Ronconi”列表调度和定向搜索方法测序的柔性工作车间调度问题的灵活性,”欧洲运筹学杂志》上,卷247,不。2、421 - 440年,2015页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
8. c . Saygin和s·e·科里奇”,将灵活的过程计划与调度在柔性制造系统中,“国际先进制造技术杂志》上,15卷,不。4、268 - 280年,1999页。视图:出版商的网站|谷歌学术搜索
9. a . n . y . f . Zhang萨拉瓦南,j . y . h .,“集成的流程规划和调度通过研究工艺设计的灵活性,”国际期刊的生产研究第41卷。。3、611 - 628年,2003页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
10. a . Jain, p . k . Jain和i . p .辛格,”一个集成方案流程规划和调度在FMS,”国际先进制造技术杂志》上,30卷,不。11 - 12,1111 - 1118年,2006页。视图:出版商的网站|谷歌学术搜索
11. 李x y、x y邵和l .高,“灵活的工艺规划的优化遗传编程,”国际先进制造技术杂志》上,38卷,不。1 - 2、143 - 153年,2008页。视图:出版商的网站|谷歌学术搜索
12. j·c·瑞恩·m·l·卡明斯:罗伊,a . Banerjee和a·舒尔特”设计一个交互的本地和全球航母甲板调度决策支持系统”张仁学报信息技术在航空会议和展览美国圣路易斯,小姐,2011年3月。视图:谷歌学术搜索
13. b . Michini和j.p.”航空母舰甲板上操作的人机交互的行动计划,”张仁学报信息技术在航空会议和展览美国圣路易斯,小姐,2011年3月。视图:谷歌学术搜索
14. r . g . Dastidar和大肠Frazzoli”,基于排队网络的分布式航空母舰甲板调度方法,”张仁学报信息技术在航空会议和展览美国圣路易斯,小姐,2011年3月。视图:谷歌学术搜索
15. j·c·瑞安,a·g·巴纳吉·m·l·卡明斯和n .罗伊”比较的性能专家用户启发式和整数线性规划在航母甲板上操作,“IEEE控制论,44卷,不。6,761 - 773年,2014页。视图:出版商的网站|谷歌学术搜索
16. c .问:魏c . l。陈和Br。王”,研究舰载飞机的飞机调度模型支持基于发射模式下,“海军航空和航天大学学报,27卷,不。1,第114 - 111页,2012。视图:谷歌学术搜索
17. 陈c, c, b . Wang”韦弗利推出飞机飞机支持调度的研究载体,“中国控制工程,19卷,第111 - 108页,2012年。视图:谷歌学术搜索
18. c .问:魏c . l。陈和Br。王”,重新安排飞机的研究支持运行启动飞机运营商基于任务,”命令及控制仿真,34卷,不。3,汽车2012页。视图:谷歌学术搜索
19. w·汉苏x, j·陈,“综合维护支持调度方法研究基于飞机,”系统工程与电子技术,35卷,不。2、338 - 344年,2014页。视图:谷歌学术搜索
20. Ashour和s . r . Hiremath”和作业车间调度问题的方法,”国际期刊的生产研究,11卷,不。1,47-58,1973页。视图:出版商的网站|谷歌学术搜索
21. p·布鲁克,b . Jurisch和b·西弗斯”的分支定界算法作业车间调度问题,“离散应用数学卷,49号1 - 3、107 - 127年,1994页。视图:出版商的网站|谷歌学术搜索|MathSciNet
22. 费尔南德斯和h . r . Lourenco”,抓住并和metaheuristic的作业车间调度,”进化计算在组合优化:7日欧洲会议2007年EvoCOP,瓦伦西亚,西班牙,2007年4月11 - 13日,。诉讼卷,4446在计算机科学的课堂讲稿施普林格,页60 - 71年,柏林,德国,2007年。视图:出版商的网站|谷歌学术搜索
23. n . Melab Chakroun, m . Mezmaz, d . Tuyttens”一个GPU-accelerated和流水车间调度问题的算法,”《IEEE国际会议对集群计算集群(12)10到17岁,页,北京,中国,2012年9月。视图:出版商的网站|谷歌学术搜索
24. a . s .曼勒“作业车间调度问题,”运筹学,8卷,第223 - 219页,1960年。视图:出版商的网站|谷歌学术搜索|MathSciNet
25. e .红晶石”机通过析取图测序:隐式枚举算法,”运筹学,17卷,不。6,941 - 957年,1969页。视图:出版商的网站|谷歌学术搜索|MathSciNet
26. m . Van Hulle“目标规划网络混合整数线性规划:一个案例研究的作业车间调度问题,“国际期刊的神经系统,卷2,不。3、201 - 209年,1991页。视图:出版商的网站|谷歌学术搜索
27. m·l·费雪”,使用拉格朗日乘数法调度问题的最优解:第一部分,“运筹学,21卷,不。5,1114 - 1127年,1973页。视图:出版商的网站|谷歌学术搜索|MathSciNet
28. c . h . Chen楚和人类。Proth”,更高效的作业车间调度问题,拉格朗日松弛方法”诉讼的IEEE机器人与自动化国际会议上,1卷,页496 - 501,爱知,日本,1995年5月。视图:谷歌学术搜索
29. 赵p·b·Luh x, y,和l . s . Thakur”作业车间调度、拉格朗日松弛神经网络”IEEE机器人和自动化,16卷,不。1,第88 - 78页,2000。视图:出版商的网站|谷歌学术搜索
30. r .成矿,m·A。Piera, p . b . Luh“改进生产调度的拉格朗日松弛收敛。”IEEE自动化科学与工程,9卷,不。1,第147 - 137页,2012。视图:出版商的网站|谷歌学术搜索
31. Kacem,美国拿,p .承担“本地化和多目标进化优化方法的柔性作业车间调度问题,“IEEE系统,人,控制论,一部分C(应用程序和评论),32卷,不。1,1-13,2002页。视图:谷歌学术搜索
32. h . z, A . y . c . Nee j . y . h,和y . f .张”修改后的遗传算法对分布式调度问题,”《智能制造,14卷,不。3 - 4、351 - 362年,2003页。视图:出版商的网站|谷歌学术搜索
33. j .高、l .太阳和m . Gen”混合遗传和变量附近下降算法柔性工作车间调度问题,“电脑和运筹学,35卷,不。9日,第2907 - 2892页,2008年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
34. f . Pezzella、g . Morganti和g . Ciaschetti“柔性作业车间调度问题的遗传算法,”电脑与行动研究,35卷,不。10日,3202 - 3212年,2008页。视图:出版商的网站|谷歌学术搜索
35. l . n, p . Wang y . w . Chen问:赵,j .熊,“知识型蚁群优化柔性工作车间调度问题,“应用软计算,10卷,不。3、888 - 896年,2010页。视图:出版商的网站|谷歌学术搜索
36. b . s . Girish和n . dina”粒子群优化算法对柔性工作车间调度问题,”《IEEE自动化科学与工程国际会议(09年),页298 - 303,班加罗尔,印度,2009年8月。视图:出版商的网站|谷歌学术搜索
37. m . Saidi-Mehrabad和p . Fattahi柔性工作车间调度与禁忌搜索算法,”国际先进制造技术杂志》上,32卷,不。5 - 6,563 - 570年,2007页。视图:出版商的网站|谷歌学术搜索
38. l . k . Lu Ting, w .崔克明z Hanbing, t . Makoto y本,“一种改进打乱frog-leaping柔性工作车间调度问题的算法,”算法(巴塞尔),8卷,不。1胜38负页。2015。视图:出版商的网站|谷歌学术搜索|MathSciNet
39. J.-Q。李,Q.-K。锅,m . f . Tasgetiren”一个离散人工蜂群算法在多目标柔性作业车间调度问题和维护活动,“应用数学建模,38卷,不。3、1111 - 1132年,2014页。视图:出版商的网站|谷歌学术搜索|MathSciNet
40. Q.-K。锅,l . Wang和b .钱”,一本小说微分进化算法解决无等待流水车间调度问题,bi-criteria”电脑和运筹学,36卷,不。8,2498 - 2511年,2009页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
41. Q.-K。l .高锅、l . Wang和w·d·李”的有效混合离散微分进化算法流车间调度与中间缓冲区,”信息科学,卷181,不。3、668 - 685年,2011页。视图:出版商的网站|谷歌学术搜索
42. l . Tang y赵,j·刘,“一种改进的微分进化算法实际动态调度steelmaking-continuous铸造生产,”IEEE进化计算,18卷,不。2、209 - 225年,2014页。视图:出版商的网站|谷歌学术搜索
43. 邓和x顾”,混合离散微分进化算法不是无所事事的置换流水车间调度问题的标准,“电脑和运筹学,39卷,不。9日,第2160 - 2152页,2012年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
44. 徐和h y元,”柔性工作车间调度使用混合差分进化算法,”计算机与工业工程,卷65,不。2、246 - 260年,2013页。视图:出版商的网站|谷歌学术搜索
45. t . c .蒋介石和h·j·林”,使用多目标柔性作业车间调度迷因算法”国际会议智能计算的程序页49-56 Springer,柏林,德国,2011年。视图:谷歌学术搜索
46. y元,h .徐”,使用迷因多目标柔性作业车间调度算法”,IEEE自动化科学与工程,12卷,不。1,第353 - 336页,2015。视图:出版商的网站|谷歌学术搜索
47. Y.-W。赵,H.-Y。王,X.-L。徐,w l。王”,一个新的混合并行算法consistent-sized批分裂作业车间调度替代机器禁止间隔,”国际先进制造技术杂志》上,48卷,不。9 - 12,1091 - 1105年,2010页。视图:出版商的网站|谷歌学术搜索
48. w·夏和z吴”,一种有效的混合优化方法进行多目标柔性作业车间调度问题,“计算机与工业工程,48卷,不。2、409 - 425年,2005页。视图:出版商的网站|谷歌学术搜索
49. n . Liouane萨阿德,美国拿,p .承担“蚂蚁系统和局部搜索优化柔性工作车间调度生产,”国际计算机通信与控制杂志》上,卷2,不。2、174 - 184年,2014页。视图:出版商的网站|谷歌学术搜索
50. r . Storn和k .价格“微分进化简单和高效的自适应全局优化方案在连续空间,“技术。众议员tr - 95 - 012,国际计算机科学研究所,1995年伯克利,加州,美国。视图:谷歌学术搜索
51. j . c . n . b . Ho泰,大肠M.-K。赖”,一个有效的学习和发展的柔性作业车间调度架构,”欧洲运筹学杂志》上,卷179,不。2、316 - 333年,2007页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
52. h·刘,A·亚伯拉罕和c . Grosan”小说可变邻域粒子群优化的多目标柔性作业车间调度问题,”第二届国际会议上数字信息管理(ICDIM ' 07),卷2,里昂,法国,2007年10月。视图:出版商的网站|谷歌学术搜索
53. z Guohui,柔性工作车间调度问题的研究方法、华中科技大学、武汉,中国,2009。
54. m . Pindeo调度:理论、算法和系统,Prentice Hall,纽约,纽约,美国,2002年。
55. c . Zhang y . Rao,刘x”一种改进遗传算法的作业车间调度问题,“中国机械工程师,15卷,不。23日,第2153 - 2149页,2004年。视图:谷歌学术搜索
56. g .史”,遗传算法应用于一个典型作业车间调度问题,“国际系统科学杂志》上,28卷,不。1,25-32,1997页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
57. 美国赵”,上下两层的邻居搜索柔性工作车间调度问题的混合算法,”机械工程学报,51卷,不。14日,第184 - 175页,2015年。视图:出版商的网站|谷歌学术搜索
58. 研究。赵,S.-L。方,X.-J。顾”,空闲时间附近搜索遗传算法的作业车间调度,“计算机集成制造系统,20卷,不。8,1930 - 1940年,2014页。视图:出版商的网站|谷歌学术搜索
59. l·f·史,h . Wang, f·胡,MATLAB智能算法分析30例北京航空航天大学出版社,2014年。
60. c .张理论和应用:微分进化算法,北京理工大学出版社,2014。
61. j . Derrac s·加西亚·d·莫利纳,f . Herrera”实用教程使用非参数的统计检验的方法比较进化和群体智能算法,”群与进化计算,1卷,不。1,3-18,2011页。视图:出版商的网站|谷歌学术搜索

版权

版权©2017余Lianfei et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。