Number of Tardy Jobs of Single Machine Scheduling Problem with Variable Processing Time

The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.

基于位置权重的窗口指派单机排序问题

研究了基于位置权重的窗口指派排序问题,机器限定为一台,其目的是在准时制环境下极小化窗口指派的窗口开始时间、窗口大小以及总延误的加权之和,以找到其最优工件加工序列以及窗口开始时间d_(k)^(1)(结束时间d_(k)^(2)),其中权重只和位置有关,而与工件无关。在共同、松弛和不同窗口指派下,通过相应最优解性质,证明此问题能够多项式时间可解。对于共同以及松弛窗口指派,算法的复杂度为O(n^(2)log n),而对不同窗口指派,问题可在O(n log n)时间内求解,其中n为给定工件数量。

基于单机排序问题的降落飞机分组排序方法

为使单跑道降落飞机排序结果在实际操作时可行、简单,首先限制同一航路段上的飞机按照先来先服务的原则排序,在最终的排序中,其拓扑次序不变;其次提出了将飞机分组排序的思想,对同一航路段上刚好满足最小安全间隔的飞机做为一个飞机组参与排序。使用1|chains|∑wjcj做为排序模型,通过求解各飞机链的ρ因子可以快速得到排序结果。将本方法用于对双流国际机场和其它几个机场的实际航迹数据进行计算,得到的排序序列完全符合实际管制需要,具有很高的推广应用价值。

一种求解变速机调度问题的混合蚁群优化算法

针对一类变速机总加权拖期调度问题,提出一种混合蚁群优化算法。引入单机拖期调度问题中性能良好的修正预计完成时间的一种修改版本启发式规则,计算信息素初值,有利于算法跳出局部极值,并在局部搜索阶段,采用单亲遗传算法基因移位算子,有效优化当代最优解。通过均匀试验设计和统计分析,确定算法的关键参数组合,将算法应用于随机生成的不同规模的40个算例,并将其结果与同类文献中算法的优化结果进行对比分析。结果表明,在相同迭代次数下,混合算法优于对比算法。

改进蚁群算法求解单机总加权延迟调度问题

单机总加权延迟调度(SMTWTS)问题是一类由于任务完工时间超过交货期从而优化目标为加权延迟成本最小的单机调度问题,已被证明是NP难题。蚁群算法受自然界蚁群觅食机理启发而来,也曾被用于其它类型的单机调度问题研究,但SMTWTS被认为是实际生产中面临的主要问题。本文提出一种改进蚁群算法求解SMTWTS问题,该算法对信息素更新策略进行了改进,引入信息扰动及变异策略,并对参数进行了合理设置,对比实验表明搜索效率好于遗传算法。

求解大规模车间调度问题的一种分解优化算法

针对以最小化加权拖期和为目标的大规模作业车间调度问题,提出了一种基于操作的分解优化算法。该算法采用迭代优化的框架,从原问题对应的操作集合中依次分解出部分操作,并确定其加工顺序。在每一次迭代过程中,首先用模拟退火算法搜索较优的操作分解方案,并形成子问题,然后用遗传算法求解该子问题。针对随机生成的测试问题,以及某减速器厂实际生产数据的计算实验表明,该算法能够在合理的计算时间内获得满意的优化质量。

具有窗口交货期的单机E/T调度问题

工件完成时间与交货期差的绝对值加权和最小化单机调度是典型的E/T(Earliness/Tardiness)的调度模型,是NP-hard问题.然而,当工件权值与加工时间成正比时,LPT(LargestProcessingTime)工件调度最优.本文讨论了上述问题具有窗口交货期且工件权值与加工时间成正比的情形,结果表明LPT工件调度仍然最优.

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。

带无向环优先级的单机总加权完成时间调度问题

单机调度是生产调度领域的一个经典问题,研究了工件间有加工优先级要求的单机总加权完成时间调度问题,考虑了若将工件优先级关系构成的优先级图视为无向图,包含有环的情况。针对该问题,设计了结合双向动态规划的拉格朗日松弛算法进行求解,使得可以求解一个工件可能有多个紧前或紧后工件的情况。大量实验测试结果表明,该算法能够在较短时间内得到令人满意的近优解。

学习型混合差分进化算法优化月台调度问题

为提高配送中心的管理水平,减少物流园区中等待作业的配送车辆的排队时间,研究了配送中心中的月台调度问题。首先,考虑月台—车辆兼容性约束和车辆作业时间窗约束,建立了以最小化总加权提前、拖后惩罚为目标的数学模型;然后,提出一种学习型混合差分进化算法,根据问题特征设计了月台调度问题的编解码方法,设计了一种学习型算子选择机制为算法在线选择交叉、变异算子,采用变邻域搜索算法作为局部搜索算法增强算法的搜索能力;最后,通过正交试验,确定了算法参数水平,进行对比实验,证明了所提模型和算法能够有效求解月台调度问题,从而帮助配送中心更好地进行月台调度管理。

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。

单台机器排序问题关于加工时间的反问题

本文研究单台机器总完工时间排序问题关于加工时间的反问题,研究尽量"小"地调整工件的加工时间使给定工件的加工次序成为最优的排序。我们考虑尽量"小"地调整是分别使最大带权相对离差的绝对值为最小、使总的带权相对离差的绝对值为最小或者使总的带权相对离差的平方为最小等三种情况。通过把问题转化成数学规划,我们分别指出这三种情况下的三个反问题都可以在多项式时间内求解。

具有链式约束的单机随机排序问题

研究具有链式约束的单机随机排序问题,目标函数为加权总完工时间的数学期望.分别对于链可中断和链不可中断两种情况,通过理论分析,给出了该问题的优先策略.

一致性条件下的一类排序问题的算法研究

这篇文章研究了在一致性条件下,具有一般学习效应的一类超前有奖延误受罚的排序问题.由于1‖∑jn=1(αjTj-βjEj)是NP-困难的,这篇文章研究了该模型的3类多项式时间可解的特例,并给出了相应的算法.

禁忌搜索的单机总加权拖期最小化问题

总加权拖期最小化(SMTWT)的单机调度问题是一个NP难问题,特别是当问题规模较大时,其求解时间面临巨大的挑战。提出采用禁忌搜索(TS)算法进行求解。首先介绍了禁忌搜索算法的原理及影响其性能的关键因素,进而针对本问题设计了定制化的禁忌搜索算法。最后通过60组基准问题对算法的性能进行了测试。实验结果证明本算法可行且所得结果质量较高。

加工时间与位置有关的一类排序问题

研究单机具有递减率的加工时间成组排序问题,目标函数为超前有奖延迟受罚排序问题.研究了该问题的3种特殊情形,给出了相应的最优算法和计算复杂性的分析.

工件加工时间为非线性分段函数的单机排序问题

讨论工件加工时间是开工时间非线性分段函数的单机排序问题,目标函数为极小化最大完工时间,总完工时间和加权总完工时间.对于目标函数为极小化最大完工时间和总完工时间的问题,给出了求解最优排序的多项式算法,对于目标函数为加权总完工时间的问题,给出了工件间的一致关系.

考虑设备可用性约束的单机调度问题

针对某转子生产车间设备可靠性低导致的工件加工质量差这一问题,研究带有设备可用性约束的单机调度问题.通过设备的可靠性定义其可用性,而设备可靠性可以通过预防性维护得以恢复.在建模时考虑了多种不同改进效果的预防性维护,以最小化总拖期时间为优化目标,并设计了遗传算法对模型进行求解.算例结果表明,所提出的决策模型能够有效应对设备可用性对生产调度带来的影响.通过敏感性分析为实际车间调度提供决策支持.

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。

带准备时间的单机调度问题的混合进化算法研究

提出了一种混合进化算法(HEA)用于求解具有序列相关依赖且带准备时间的单机调度问题,其优化目标为最小化总延迟。该混合进化算法由局部搜索和进化算法框架混合而成。HEA具有一些新的特点,例如在局部搜索中采用了一种新提出的基于块移动的邻域结构,这种邻域结构合理地限制了搜索空间,提高了算法的搜索效率;在HEA中采用了一种新的组合算子———块顺序交叉算符(BOX)来产生新的子代工作序列。用本算法对当前国际文献中公开的两组共64个算例进行了测试,HEA改进了9个算例在当前文献中的最优解,表明了所提出的HEA算法的优越性。与之前的国际文献中最好的四个启发式算法进行了详细比较,表明了HEA算法的优势。