最小化时间表长的平行机调度近似算法研究

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.

具有周期维护最小化时间表长的两台平行机调度问题(英文)

本文讨论了具有周期维护的两台平行机调度问题,目标函数为最小化时间表长.设T为维护周期,t为每次对机器维护需要的时间,当t≤T/3时,本文证明了对于该问题由LPT算法得到的最坏误差界为2.

极小化时间表长的无等待流水车间调度

针对以时间表长最小为目标函数的无等待流水车间(No-Wait Flow Shop,NWFS)调度问题,提出了一个混合禁忌搜索算法(Hybrid Taboo Search,HTS),以启发式算法产生的解作为初始解,通过禁忌搜索进一步提高解的质量。大量随机产生实例的实验结果表明:提出的HTS算法在总体性能上优于经典的RAJ、VNS和GASA算法,因此该算法具有可行性和优越性。

具有禁用区间的平行机排序时间表长问题的全多项式近似方案

近几年来,排序问题由于其深刻的实际背景和广泛的应用前景而受到关注,其自身也在不断的发展变化当中。传统模型通常假设机器是可以连续使用的,但实际上机器在加工期间也需要维护,所以有许多人考虑了机器具有禁用区间的排序模型,并指出了当机器具有多个不可用区间时是强NP-难的问题。对于普通NP-难的问题,他们提出了有效的动态规划算法或多项式时间近似算法。研究工件在两台平行机上加工的排序问题,其中第一台机器上有一段禁用区间,另一台机器是可以连续使用的。在整个加工过程中,工件不允许中断,目标函数是极小化时间表长,该问题是NP-难的。给出这一问题的一个全多项式时间近似方案,算法的时间复杂性是O(n4/ε3),其中n是工件的数量,ε是误差界。

一个求分批排序最小时间表长的多项式时间近似方案

给定一个批处理系统 {pi,ri:i=1,… ,n} ,pi,ri 分别代表工件i的加工时间和释放时间 ,该系统至多可以同时处理B(批容量 )个工件 .一个批次的加工时间是此批次所包含所有工件的加工时间的最大者 .最后一个被加工完工件的完工时间常被称为时间表长 (makespan) ,主要给出了一个求分批排序最小时间表长的多项式时间近似方案 (PTAS) .

同时最优化时间表长与总完工时间的双代理单机序列分批排序问题

本文研究在一台序列分批处理机上同时最优化A代理的时间表长和B代理的总完工时间的双代理排序问题.在序列分批的背景下,工件被分批加工(但不同代理的工件不能在同一批中加工,且每个代理都希望最小化仅依赖于各自工件完工时间的费用函数)且一批的加工时间等于这一批中所有工件的加工时间和.而且在一个新批开始加工前,机器有一个常数的安装时间.此外,根据批容量,序列分批模型又被分成有界模型和无界模型.在本文中,我们对所研究问题的有界模型和无界模型分别给出了一个多项式时间算法.

加工时间线性恶化的成组加工流水作业问题

文章讨论了m台机器的Flow Shop成组加工问题,工件在不同机器上的加工时间以相同的系数(斜率)线性恶化,目标函数分别为极小化时间表长和总完工时间.对于目标函数为极小化时间表长的Flow Shop成组加工问题,再进一步细分为组间无调整时间和组间有相同调整时间的两种情形来讨论,都得到了最优调度(排序).对于目标函数为总完工时间的Flow Shop成组加工问题,只要组内按q(?)单调递增(SPT)序加工,组间按S_i单调递增序加工可得最优调度.

基于加工时间之和学习效应下的单机成组排序问题(英文)

研究具有加工时间之和学习效应下的一个新型成组排序问题,工件的学习效应是之前工件加工时间之和的函数,组学习效应是成组加工所在的位置的函数.考虑最大完工时间和总完工时间两个问题,证明了这两个问题都是多项式时间可解的,并提出了相应的多项式时间算法.

机器使用时间受限的线性恶化成组排序问题

讨论了单机成组加工问题,工件加工时间是开工时间的简单线性恶化函数,并假设机器在某一时间段内不能进行工件的加工,目标函数为极小化时间表长。给出了该问题的一种0-1整数规划解法。

带到达时间的单机排序中的资源分配问题

讨论两个单机排序的资源分配问题1|rj,pj=bj-ajuj,Cmax≤^C|∑uj和1|rj,prec,pj=bj-ajujCmax≤^C|∑uj并给出求其最优资源分配的多项式算法。

维护时长依赖于机器负载和机器空闲的单机调度问题

考虑一个含有单次维护的单机调度问题,其中工件不可中断,维护的开始时刻给定但维护时长是维护之前机器负载和机器空闲时长的线性增函数,目标是最小化时间表长。分3种情况进行讨论,对前2种情况分别给出了一个多项式时间最优算法,对最后一种情况分析了LPT算法的性能并给出了通过经典背包问题的任意一个FPTAS来获得该情况的一个FPTAS的方法。

具有可控和依赖位置负荷处理时间的资源约束单机排序问题

本文研究具有与任务和位置有关的可控处理时间的凸资源单机排序问题。任务的实际加工时间是所获得的资源量、与任务所在位置有关负荷的函数。考虑两个问题。第一个问题是在资源总量有上界限制条件下,确定任务排序、资源分配方案,使得时间表长最小。第二个问题中资源总量没有限制,目标是求出最小资源总量、任务排序和资源分配方案,使得由时间表长和资源总量加权和取最小值。分别证明了上述问题可以在多项式时间内求出最优解,并给出了求解相应问题的多项式时间最优算法。

具有负载依赖型维护时长的平行机调度问题

本文考虑具有工具更换的平行机调度问题,机器的维护时长依赖于维护前的负载,目标为最小化时间表长.首先,基于维护时长函数为单调不减函数得到最优调度方案应有的两个性质——单台机器加工的工件个数最多相差一个;每台机器在最后一个维护间隔应尽可能多地加工工件.其次,对维护时长函数为凹函数、凸函数和线性函数的情况分别给出算法MNJF, SJF和SLE.最后,证明算法MNJF, SJF以及SLE均为对应情况的最优算法,且算法MNJF对于维护时长函数为线性函数的情况也是一种最优算法.

具有学习效果的两机流水车间调度启发式算法研究

以最小化时间表长为目标函数,对具有学习效果的两机流水车间调度问题进行研究.由于工序加工时间引入了学习效果,传统的Johnson法则和NEH启发式算法不再适用.针对该问题的NP-hard特性,提出了JNEH和MNEH两种求解问题的多项式启发式算法.计算机数据实验证明了新的启发式算法求解问题的可行性和有效性;表明了JNEH启发式算法和MNEH启发式算法对小规模问题求解的精度更高、稳定性更好;同时证明MNEH启发式算法对求解大规模问题具有比传统算法更好的寻优性能和鲁棒性.

蚁群优化结合变邻域搜索求解NWFS调度问题

针对NP-难的最小化时间表长为目标的无等待流水车间调度问题,将此问题转化为旅行商问题。采用蚁群优化求得初始工件排序。在提出的一种新的邻域结构基础上,迭代进行集中和分散的变邻域搜索以改善解。用Rec系列及hel1和hel2共计23个Benchmark算例进行计算验证,并与RAJ算法进行了比较。结果表明所提出的方法是有效的。

求解流水车间调度问题的瓶颈指向启发式算法

针对最小化时间表长的流水车间调度问题,提出一种根据工件加工时间特征构建工件调度的瓶颈指向启发式算法。首先,为构建初始工件排序,充分利用各机器负荷一般不相等的特点,瓶颈阶段前加工时间较短而之后加工时间相对较长的工件优先开始加工;其次,当有工件等待加工时,根据工件在瓶颈机器前或后加工时间的特征调整工件加工顺序;最后,采用邻近工件成对交换和插入的方式改进初始调度。当瓶颈机器趋于中间阶段,或瓶颈机器上工件的加工时间趋于增加时,求解效果较好。数据实验表明算法是有效的。

带有一般性位置依赖影响的分组调度研究(英文)

为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的.

允许中断的同速机调度问题的一个最优算法

讨论工件有不同准备时间,加工允许中断的同速机调度问题,目标函数为最小化时间表长.提出了一个算法,并证明了该算法为最优算法,该算法中工件中断的次数至多为Nn次,计算的复杂度为O(Nnlogn).最后给出一个实例加以说明.

两台同型机多阶段维护调度问题的若干结果

研究了2种类型的机器维护:一种为周期性维护,另一种为决策维护.对于周期维护最小化时间表长问题,证明了经典的FFD算法是一个很好的启发式算法,并且得到了该算法的一个上界.对于决策维护最小化总完工时间问题,分析了SPT算法的界.特别地,对于单机并且机器仅需要2次维护的情况,给出SPT算法的界不超过11/9.

带有退化维护和退化工件的单机排序问题

对带有维护活动和工件退化的单机排序问题进行研究。机器需要在某一个时间段内进行维护以提高其加工速度,且在这段时间内机器不能加工任何工件。机器维护后恢复到初始状态,工件的退化效应重新开始,其中机器的维护时间是维护开始时间的线性非减函数,工件的实际加工时间是与其特定位置有关的退化函数。目标是找到机器的最优维护位置、极小化时间表长。对于单机情形,给出了最优排序的一些性质。在特定条件下,证明了最优排序与工件排序无关,最优维护活动排在给定排序的中间位置。