文摘

塑料生产的平行机调度问题进行了研究。在这个问题上,处理时间和到达时间是不确定的,但躺在各自的时间间隔。此外,每个作业时必须一起处理模具工作属于一个家庭可以共享相同的模具。因此,时间需要改变模具两个连续的工作,属于不同的家庭,这是被称为顺序相依设置时间。本文旨在确定一个健壮的时间表在min-max后悔标准。证明每个可行解的情形导致最大的遗憾在于有限的极端情况。构造了一个混合整数线性规划模型,提出了一种精确算法来解决这个问题。此外,修改后的人工蜂群算法解决大规模问题。提出算法的性能评估通过广泛的计算实验,结果表明,该算法超越客观价值的确切方法方面和计算时间。

1。介绍

平行机系统广泛采用于各种各样的生产环境,如半导体制造行业(1)和电子行业(2]。最大完工时间最小化的一个常用的目标生产调度问题(3,4]。平行机调度问题都有理论和实际意义。许多文献(即假定的参数问题。,the processing time and job release time of jobs) are known in advance precisely before production process begins. However, the results of the solution derived under the deterministic assumption may deviate considerably in real situations [5]。在实践中,很难得到准确的参数生产过程开始之前由于一些不确定因素,如机条件,生产环境,和乔布斯的特征6- - - - - -9]。描述和克服不确定因素的影响,提出了几个强大的调度方法来提高质量和派生的解决方案在实际情况下的稳定。

不同于典型的平行机系统,对塑料产品的并行机器系统涉及模具更改在生产的过程中,也就是所谓的设置要求。在塑料生产系统中,工作分配给一个平行的注射机和相应的注塑模具需要安装到前的注射机注射过程。工作属于一个家庭可以用相同的模具加工和换模过程花费一段时间。生产计划会安排工作,这样的工作,属于同一家庭一起处理,以避免额外的模具更改流程和提高效率。两个工作计划要处理连续但属于不同的家庭,模具改变之前,必须进行可以执行下一份工作。因此,减少换模时间在塑料生产调度是至关重要的。

探讨均匀平行机问题在塑料生产系统,其中包括不确定的处理时间,模具工作释放时间,安装时间。这是一个扩展的问题研究[5]。初步目标是最小化最大完工时间的。场景是首先定义为一个可能的实现处理时间和释放时间工作工作。由于工作的不确定性处理时间和释放时间,考一个给定的解决方案可以是不同的在不同场景。提出了确定一个最优解与最稳定在所有场景。给定的性能(或稳定)解决方案的主要问题是其最坏的情况下鲁棒调度。对于一般性,它假定处理时间和释放时间躺在各自工作间隔下界和上界值。相应的时间间隔参数被认为是已知的但不属于任何统计分布由于信息不对称5,9]。然后采用健壮的偏差标准来评估每个候选人的健壮性安排。健壮的偏差标准也被称为min-max后悔准则,旨在找出一个解决方案与最小最大偏差在所有可能的场景。这一标准有其优势的高度竞争的环境原因,健壮的决定执行在任何一组潜在的可实现的场景(5]。健壮的偏差标准范围的大小错失机会通过确定一个时间表,具有性能接近最优(或接近最优的)决定在任何场景。

最好的知识,作者,并行机器调度问题与不确定的处理时间,准备时间,模具改变考虑尚未覆盖的其他研究人员在并行机器调度问题。本文构造了一个混合整数线性规划(MILP)模型介绍了识别一个健壮的时间表以最小最大遗憾在所有场景。关键的概念机提出了(5]是修订,采用问题消除最坏的情况到有限数量的极端点的场景来评估给定的解决方案的健壮的偏差计算最大遗憾。精确算法迭代松弛过程,以及修改后的人工蜂群算法的研究问题。证明的有效性和效率提出了启发式算法,进行了一系列的测试问题。

本文的贡献如下所示:(1)的平行机调度问题考虑不确定的处理时间,工作释放时间,换模时间进行了研究。普遍性,认为躺在不确定数据的间隔,在实际环境中捕获的情况。(2)群体智能算法解决np难的问题。计算结果表明该算法的稳定性和有效性。我们所知,本研究首次采用人工蜂群算法鲁棒优化的并行机器调度问题。本文的其余部分组织如下。部分2提供工作相关的文献回顾平行机以及鲁棒调度方法。部分3介绍了描述和提出问题的数学模型。提供了精确的算法基于迭代松弛部分4。修改后的人工蜂群算法对大规模问题提出了部分5。广泛的计算实验的结果和比较提供了部分6。部分7提供了进一步的结论和方向在相关领域工作。

2。文献综述

随机方法解决调度问题在不确定性是可用的(10),但这些方法有其局限性,由于严格的前提和假设5]。例如,随机方法需要某些信息的概率分布处理时间和释放时间的每一份工作,可以推断,条件是大量的历史数据是可用的(9,11]。然而,这样的历史数据不可用在高度不确定的环境和唯一的信息推测下界和上界的一些参数,如处理时间和准备时间12]。对于一些一次性的工作,决策者更感兴趣的是获得一个健壮的时间表,这是对最坏性能在所有场景,而不是获得一个预期的预期情况下最优性能。健壮的偏差的方法,被称为min-max后悔(13),适用于这些情况下获得解决方案(14,15]。健壮的偏差的方法是广泛采用各种组合优化问题提出了输入数据时的间隔,如最短路径(16,17),生成树(14,17- - - - - -19),和生产问题5,20.]。这种方法在一个不确定的环境中产生了一个满意的结果。此外,强大的调度方法也采用其他问题,如海上运输问题[21,22],路由问题[23),和公共卫生服务部门的调度问题24]。最近,min-max遗憾最小化在相同的平行机调度环境下极小化最大完工时间间隔数据研究[5];特别是,他们认为工作在于各自的处理时间间隔。努力解决这个不确定性多项式时间np难问题,机器和极端临界点的概念提出了场景和两个属性来避免访问无限可能的场景和消除坏的情况到有限数量的极端点的场景。处理时间与间隔时间最小化问题工作在相同的并行机器处理5第一次在相关领域。此外,健壮的偏差的方法采用一个统一的平行机调度问题(12)最小化总流程时间不确定的处理时间,在于各自的间隔。最糟糕的情况下用于识别的概念,一个可行的解决方案的最大遗憾是采用(5,12),然后提出确切的和启发式算法找到的时间表在所有场景。

顺序相依设置时间调度问题是一个非常活跃的研究领域25- - - - - -28]。在塑料制造过程,注射操作是一个典型的单级制造过程,这就需要指定的塑料注入到模具生产塑料制品在不同的形状。几个工作是由一台机器制造与各自的模具(29日]。模具的安装所需产品生产的注射操作,而设置sequence-depending操作和参数,如模具的时间和安装时间变化取决于两个连续工作(30.]。如果连续两个工作由不同的模具,加工成本设置手动模具过程中诱导改变操作。因此,模具的时间变化以及重新安装中不容忽视的一个大规模生产形势和规划师会安排这些工作由同一模具加工在一起为了减少在生产过程中模具的数量变化。为代表的家庭顺序相依设置时间间隔的数据在一个机器调度问题最小化总流程时间被认为是在20.]。

提出了精确和启发式算法来解决min-max后悔问题。min-max遗憾最小化总流程时间的问题在单个机器上(6),然后由其他研究人员进一步研究这个问题。为了减少计算工作量,min-max后悔模型提出了不同的方法。证明最优调度中点的情况下保证2-approximation的最优解15]。启发式方法是附近的一个近似算法获得最优结果min-max后悔模型。典型的例子所示(5]。一些启发式算法基于工作交换移动和插入研究者提出的举措。配料混合禁忌搜索算法和排序决策在一个单独的机器调度问题提出了苏皮亚达和奥马尔31日]。工作交换和插入方法应用于生成社区解决方案,采用弧的解决方案的形式出现在禁忌列表中的弧线代表工作在单个机器上的序列;此外,他们还实现了一个搜索深度战略的过程中,社区一代消除无效的动作,以减少计算负担,同时获得最终的进度和表现质量。舱底水等的工作。32)指出,社区情况的解决方案是在大量或其元素是昂贵的评估,必须限制解决方案的数量检查给定迭代屏幕上社区,专注于前途的举措在每个迭代。三个候选人名单策略提出了限制社区解决方案的数量计算的效率。

各种平行机问题的研究,分别考虑不确定的处理时间,任意的准备时间,换模时间模型发展阶段而没有研究涉及这些因素完全集成的健壮的调度模型。因此,探讨这些因素,制定一种新的模型在塑料生产环境。纸是一个扩展版的上一篇文章中,包含了更多的不确定因素和功能在实际的制造系统。

3所示。问题公式化和数学模型

它开始通过描述的问题和最大遗憾的定义一个可行的时间表。然后给出了MILP。

3.1。问题描述

这个问题正在考虑处理的并行机器调度分配的规划周期以最大完工时间最小化。这项工作由机器和模具加工,每一个工作都可以只处理一次。在前面的假设下,问题可以建模为一个混合整数线性规划公式如下所述。

3.2。MILP配方

符号 :工作,,在那里是总数量的就业岗位, :机器,,在那里机器的总数, :模具安装时间的工作 :模具拆卸时间的工作 :工作的处理时间下的场景, :工作场景下的到达时间, :机器的处理速度 :场景这是一个可能实现的处理时间和到达时间的工作, :一个很大的正数

决策变量 :1如果工作将上处理机器吗和0,否则 :1如果工作将处理后的工作吗在同一台机器上和0,否则 :工作的开始时间处理机器在安排在场景中 :工作的完成时间安排在机在安排在场景中 :机器的完成时间在安排在场景中一个可行的解决方案应该满足和,,。也就是说,每个工作应该在并行处理完全一次机系统,存在一个处理序列在同一台机器上处理工作。让是一组可行的时间表。

工作完成时间在安排在场景中可以定义如下: 完成时间的计算机器在场景中:

机器的完成时间在安排在场景中等于工作的完成时间,预计要处理的机器吗 也就是说, 工作的开始在机等于或大于到达的时间工作吗在场景中: 此外,如果工作和之前的工作处理不同的模具,模具的时间变化是涉及之前的工作吗开始处理: 考的时间表在场景中等于机器的完成时间,完成最后的平行机系统: 或 我们定义场景下的最大完工时间最小作为和相应的最优调度: 对于一个给定的时间表下,遗憾的场景被定义为 最大的遗憾是 健壮的平行机调度间隔处理时间和到达时间和模具改变可以制定 提出的问题是一个经典的概括调度问题和最优解决方案来自于(11)对应的时间表在所有可能的场景。

平行机强大的调度与不确定的处理时间和到达时间(RS)可以制定如下: 我们注意到上述配方非线性是由于目标函数的两个操作。然而,原始RS模型可以转化为一个混合整数线性规划模型: 线性化后的原始RS模型问题,制定直接仍不能解决由于无限可能的场景。为了解决这个问题,最初的目标是识别每个可行解的最大遗憾,然后选择最低的解决方案在所有解决方案中最大的遗憾。因此,两个属性提出了识别和限制最糟糕的情况有限数量的极端点的场景,这意味着我们不需要访问所有可能的情况下获得最大的遗憾一个给定的解决方案。为了捕捉真实生产环境的不确定性,我们假设每个工作的处理时间和到达时间是不确定的,躺在各自的时间间隔。因此,在这种假设可能的场景的数量是无限的,它是不切实际的枚举所有可能的场景让最坏的情况对于一个给定的解决方案。派生属性用于缩小几个极点场景最坏的情况。

定义1。一台机器据说是一个时间表的关键在场景中,如果是机器的最大完成时间下:

定义2。一个极端点的场景的时间表定义如下:

属性1。对于任何时间表,让是一个最坏的情况中机是至关重要的。然后一个场景存在的时间表这样(一)机也很重要的下;(b)场景是一个最坏的情况呢。假设一个给定的解决方案有一个坏的情况满足条件(a)和(b)的财产1。因为机器是至关重要的在场景中,时间和最大遗憾的解决方案可以计算如下。
注意,设置包含所有工作机器在安排表示为,。如果,然后。

证明。最糟糕的情况可以转换成场景通过减少来和来对所有并通过增加来和来对所有,也是关键的机器下。让表示时间的增加。让是最优时间表的场景。因为考不能增加超过在场景中相比,,我们得到 从上述不等式,我们有,这表明最大遗憾不能减少如果我们取代与,这也是最坏的情况。

属性2。一个给定的解决方案的最大遗憾可以表示如下:

证明。方程的性质2显示, 矛盾的假设存在一个机器这样 自,在那里,

4所示。具体的算法

RS是一个min-max问题,可以解决使用一般迭代松弛(IR)提出的过程33- - - - - -35]。首先,所有可能的场景代替在RS与一组有限的场景吗,导致放松混合整数规划(RS-relaxed): 请注意。在这个迭代松弛方法,我们替换所有可能的场景(),和场景的最糟糕的情况是可行的解决方案中确定最后的迭代。

最大完工时间最小和可以解决通过求解混合整数规划如果场景是固定的。

我们指的是约束和与为减少遗憾。

迭代松弛算法。红外程序停止时,在那里当前的最大遗憾是轻松的解决方案吗。

步骤0。集(后悔值)和下限吗(是后悔值上限);选择一个初始解。

步骤1。确定解决方案的最糟糕的情况及其各自的通过属性1和财产2。如果,然后,。如果请转到步骤。

步骤2。添加后悔削减和;RS-relaxed场景。

步骤3。和通过解决RS-relaxed标识。集;去一步。

步骤4。停止。

5。群体智能方法

5.1。改进人工蜂群算法

5.1.1。改进人工蜂群算法的描述

ABC算法已经被充分研究过的平行机调度(36- - - - - -38]。ABC算法是一种很有前途的群体智能优化问题的算法,模拟蜜蜂的觅食行为。三种类型的蜜蜂提供不同的功能为饲料收购蜂巢的蜜蜂社会结构。收集到的花蜜将存储作为一个食品供应短缺的花蜜。蜜蜂蜜蜂和旁观者回应得到花蜜从附近的植物,虽然军的主力蜜蜂采集花蜜信息指导的觅食行为采用蜜蜂蜜蜂和旁观者。ABC算法的设计是一个递归搜索过程有四个主要阶段,包括初始化阶段,采用蜜蜂阶段,旁观者蜜蜂阶段,和侦察蜂阶段。过程流程图如图1。

的大小等于蜜蜂殖民地,其中包括采用蜜蜂,蜜蜂旁观者,一个侦察蜂。大约一半的蜜蜂蜜蜂一样工作,剩下的是旁观者的蜜蜂。解决方案的数量等于ABC算法,在那里。每个解决方案由一个雇佣蜂代表一个被占领的食物来源。因此,解决方案是由人口。采用蜜蜂的作用是收集花蜜回到蜂巢;食物来源的信息将被共享蜂巢。旁观者蜜蜂将选择一个食物来源,进一步利用基于丰富的花蜜。侦察蜂将寻找一个新的解决方案一旦耗尽食物来源。

5.1.2中。初始化阶段

初始化阶段,传统的方法是生成一个随机分配和顺序优化问题。这延长收敛到全局最优,未能达到全局最优,作为有前途的地区融合的过程涉及到某些不成功的社区搜索空间大尺寸下的解决方案。解决方案时将废弃的某些成功搜索后没有改善。因此,建设性的启发式的初始化阶段坚持在初始阶段开发最好的解决方案,以减少搜索工作的ABC算法收敛于全局最优。最大完工时间最小的构成在经前综合症模型的目标是获得一个解决方案最少的总长度的平行机调度完成所有可用的工作。最初的解决方案质量解决方案,按升序排序每个工作的准备时间预计将最好的选择相比,及时随机分配。同时保持一定质量的初步解决方案,解决方案应考虑之间的多样性。否则,某些解决方案空间无法访问。同时,对基于人群的metaheuristics很难逃离的过早收敛39]。减少的可能性的一个方法收敛于一个相同的但不是全局最优解决方案基于metaheuristics依赖于随机初始建设解决方案。在我们的初步研究,它是有效开发一个公平的解决方案通过随机机器作业质量排序序列。

5.1.3。采用蜜蜂阶段

每个雇佣蜂执行社区搜索解决方案生成一个社区解决方案由三个社区运营商提高质量的客观价值的解决方案。贪婪的选择是应用在此,不断提高解决方案之间进行比较客观的值和。如果社区解决方案的解决方案质量比原来的更好,社区解决方案将取代以前的解决方案。附近的运营商包括交换算子,插入算子和交叉算子如图2,3,4相应地,。附近搜索是不受限制在相同的或另一个跑道上通过随机选择两个或两个以上的元素。累计试验不成功的改进解决方案将增加1如果一个社区的客观价值的解决方案是比前面的解决方案。交叉算子将选择一个单一的解决方案完成时间最长的跑道,选择另一个解决方案的适应性选择概率结合和发展一个后代的解决方案。

5.1.4。旁观者蜜蜂阶段

每个旁观者蜜蜂将进一步充当社区运营商指定解决方案基于概率选择关于健身价值。的健身价值的解决方案是衡量(33)。更多的健身价值意味着一个更好的解决方案的质量。计算后的健身价值的解决方案,(34)能够获得个人选择性每个解决方案的可能性。一个累积概率计算通过聚合前个人的概率。选择标准遵循轮盘赌选择的方法。一个随机数将为每个旁观者蜜蜂生成进一步搜索社区运营商的选择一个解决方案:

是5.1.5。侦察蜂阶段

在附近搜索,不成功的累积数量更新将被记录。大量的意味着一个可能的解决方案绊倒在一个局部最优。侦察蜂阶段的就业是放弃解决方案一旦达到搜索的最大公差。如果一个解决方案不能进一步提高了若干次迭代,达到最大的宽容,侦察蜂将取而代之的是一个疲惫的解决方案由一个初步的解决方案。

5.1.6。Min-Max后悔方法使用人工蜂群算法

min-max后悔的设计方法是获得一个健壮的pm计划来最小化最大后悔值通过考虑的场景。两个主要阶段需要优化技术解决min-max后悔模型,在最坏的情况下最优考,考下健壮的时间表。ABC算法推导过程工作流使用最坏最优考和健壮的时间是相同的,除了客观价值和健身价值的计算。最坏的情况下最优的目标函数极小化在强劲的高山,而目标函数极小化通过考虑所有最坏的场景(28)和(29日)。

6。数值实验和结果

在本节中,修改后的ABC算法的性能评估随机健壮的PMS实例并与使用混合整数规划的结果。MIP计算IBM ILOG 12.6.3最大化策略优化工作室进行比较。所有算法都写在c#语言与visual studio 2015在电脑上用英特尔酷睿i7 3.60 GHz CPU和16.0 GB内存下窗口7企业64位操作环境。为了评估算法的性能,两种方法被认为是在数值实验中,如表所示1。方法1在解决RS和使用混合整数规划被认为是一个比较的基线。方法2,RS和优化技术提出了人工蜂群算法。在这方面,收敛性和计算速度的性能提出了人工蜂群算法可以测量通过比较中获得的值的方法。

测试运行在初步研究获得的参数进行设置。最大迭代麦克斯特等于。的最大公差等于成功更新。殖民地的大小设置为80,和解决方案的数量是40。这些结果也一起评估MIP测量偏差的最优解之间的精确算法和群体智慧。最大MIP和提出的ABC算法计算时间是7200秒。

两种算法评估的测试实例工作和机器。对于每个工作,下界和上界的准备时间和加工时间分为随机均匀分布间隔的整数,,,相应的,值被认为是(0.2,0.4,0.6,0.8,1.0)。测试实例的数量是45的任意组合,。的处理速度等于一个随机均匀分布从1到10,在哪里。假设只有三种类型的注塑模具,模具安装时间和模具删除时间注塑模具的每一组被定义为(30、60、90)和(10年,20年,30)。工作岗位的数量为每个组是均匀分布的。

后悔上界值和遗憾下界值记录用MIP表示迭代松弛算法的性能。如果后悔差距等于0%,健壮的最优值意味着一个真正的最佳记录。否则,模型未能确定最优解7200秒内如果后悔差距大于0%。为了比较MIP算法的性能与MABC算法的性能,偏离最著名的解决方案表示平均最优和最优值之间的偏差使用最大化策略和有限的计算时间。

表2显示了平均计算性能强劲的平行机调度使用修改后的10 ABC算法的运行时间。结果表明,计算时间是指数级增加了两种算法当问题规模的增长。问题的大小,获得的鲁棒最优解MIP执行比结果使用MABC算法的最优值和计算时间。这意味着MABC算法的某些计算开销小尺寸的实例。当问题规模增加,MIP并不能够确定最优解决方案在一个合理的时间内,尽管MABC算法能够获得接近最优值。为了衡量算法性能的变化,最好的解决方案的数量表示的最优值(10)的最大数量,超过MIP表获得的结果3。这些结果可以提供证据证明的可变性MABC算法性能的测试实例在低水平对质量的解决方案。更好的解决方案的数量#最能代表的数量修改ABC算法找到的解决方案在10运行多少次优于MIP获得的解决方案与时间限制。至于大型实例,修改后的ABC算法能够获得更好的解决方案与计算工作量低于确切的方法。

7所示。结束语

平行机模型已被广泛采用的制造环境及其调度问题是广泛研究文献,最大完工时间最小化的共同目标并行机器调度问题。然而,大多数文献都假设的参数工作,如处理时间和准备时间精确,这是应对的工作集的实际情况是第一次处理。不确定加工时间和准备时间并行机器调度是生产调度中的普遍现象。在实践中,工作的准备时间是不确定的,无法估计准确的概率分布由于外部因素的影响,如交付可变性,外资物流延误,劳工问题,运输安排。工作的处理时间可能偏离标准操作时间,这是由腐蚀引起的操作事件,纠正措施和返工。

为了描述参数的不确定性,假定处理时间和准备时间的精确值的每一个工作是未知的和可用的信息是每个参数的绑定。解决这个健壮的版本的问题,介绍min-max遗憾的方法获得一个健壮的平行机调度,考虑所有可能的场景。我们首先介绍了一个混合整数线性规划模型来描述这个问题,然后提出两个属性来消除坏的情况提出了两个属性允许模型获得的最大遗憾每个可行的时间表有有限数量的极端点场景。

基于通用的精确算法迭代松弛算法来解决提出的问题。然而,很难获得一个解决方案从大尺寸情况下的精确算法识别每个可行的最糟糕的情况是需要大量的计算。因此,修改后的人工蜂群算法解决大规模并行机器调度与不确定性。实验结果表明,最优解附近一个健壮的可获得一个合理的时间。人工蜂群算法的强度是获得最优解附近的三个主要特性,利用分散的蜜蜂,在群性能、自组织和集体行为的算法结构。拟议中的广泛采用人工蜂群算法在静态平行机调度和其他相关问题。为了提高该算法的开发,探索实现高水平的优化技术,强大的造型,某些修改提出了人工蜂群算法。

未来的工作可以总结如下:扩展的平行机调度与现实的不确定性,约束和目标保持在实际操作和可行的解决方案与其他已知的优化算法结构和迭代过程优化技术来实现最优计算量小。

人工蜂群算法的符号

:	蜜蜂的殖民地的大小
:	殖民地的数量的解决方案
:	最大迭代次数
:	维度的一个独立的解决方案
	每个解决方案的位置在蜜蜂的殖民地
:	的客观价值的解决方案
:	的健身价值的解决方案
:	单个解决方案的可能性在整个殖民地的健身价值
:	一个单独的解决方案的累积概率在升序整个殖民地的健身价值
:	你的邻居个体解决方案的解决方案
:	个人积累的试验值的解决方案,不能提高解决方案的质量的客观价值
:	最大的宽容
:	随机数,。

相互竞争的利益

作者宣称没有利益冲突有关的出版。

确认

这项研究得到了国家自然科学基金的支持。71201099上海市教育委员会、创新计划。14 yz111东部、上海年轻学者计划QD2015041江、上海聚氨酯程序(没有。13 pjc066)、上海(没有青年教师的基础。ZZshhs13021)和香港理工大学。作者的感激也扩展到研究委员会和香港理工大学工业及系统工程的支持这个项目(RUF1和RU8H)。