基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为0.411 7,分支定界算法的效率比较高,处理100个工件所用的最大时间不超过460s。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。     

带指数学习效应和凸资源分配的单机排序问题研究

【目的】研究在全部工件加工时间可变的情况下具有指数学习效应和凸资源分配的单机排序问题,其中工件的实际加工时间具有指数学习效应,并依赖于分配它的不可再生资源数量。目标是确定资源的最优分配和工件最优排序,使得最大完工时间和资源消耗费用的3种组合最优,即最大完工时间和资源消耗费用的加权和最小、资源消耗费用限制下的极小化最大完工时间和最大完工时间限制下的极小化资源消耗费用问题。【方法】对给定排序,用约束优化和无约束优化问题的最优性条件能够求得其最优资源分配。【结果】分析最优解满足的性质,证明最优解能够通过多项式时间得到,并给出了具体求解算法。【结论】算法分析表明求解算法的时间复杂度为O(nlog n),其中n为工件个数。     

带准备时间的任务单机学习效应排序问题

具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容,它们对任务的完工时间有重要影响。研究了具有学习效应且带有准备时间的任务单机排序问题,其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数,目标函数为最小化总完工时间。这个问题是NP-难问题。用分支定界法给出了此问题的最优解,为了提高分支定界法的运行效率,同时给出了一个启发式算法、几个优势性质和两个下界。计算结果表明分支定界法和启发式算法求解此问题非常有效。     

带准备时间的任务单机学习效应排序问题

具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容,它们对任务的完工时间有重要影响．研究了具有学习效应且带有准备时间的任务单机排序问题,其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数,目标函数为最小化总完工时间．这个问题是NP-难问题．用分支定界法给出了此问题的最优解,为了提高分支定界法的运行效率,同时给出了一个启发式算法、几个优势性质和两个下界．计算结果表明分支定界法和启发式算法求解此问题非常有效．     

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。
     

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。     

具有恶化效应的双代理单机最优调度算法

针对单机床加工环境中待加工任务具有恶化效应且来自2个具有不同需求的代理时,无法快速求解出满足要求且成本最低的最优加工序列的情况,提出了可在特定约束条件下的具有恶化效应的双代理单机最优调度算法。首先提出优化目标为:保证一个代理的任务均不延迟完工的前提下,使得另一个代理的总加权完成时间或总加权折扣完成时间最小;其次指出该优化问题具有NP难度,并给出其在一般及特殊情况下最优解的结构性质;此后对于特定约束条件下的情形,提出多项式时间优化算法。该算法中首先将2个代理的任务分别按照所证明的最优策略排序,然后再按照使得2个代理能得到最小总加权完成时间和给定约束关系的算法将2个序列合并在一起,并证明得出的序列即为所求调度问题的最优解。实验结果表明,该算法作为确定性算法,计算时间与最优解平均误差率大于0.3%的模拟退火算法相似,远远低于可求解出最优解的分支定界算法。     

具有学习与退化效应的单机排序问题

研究了具有学习效应与退化现象的单机排序问题,给出了目标函数为最大完工时间、总完工时间的多项式时间算法;并证明工件的权重与加工时间一致时加权总完工时间问题、工期与加工时间一致时最大延迟问题均有多项式时间算法.     

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

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

带拒绝和到达时间的单机排序问题

研究了一个单机带拒绝的排序问题,目标函数是最小化接受工件的最大完工时间与所有被拒绝工件的拒绝费用之和。首先给出了此问题的混合整数规划模型,并得到了最优解的一些性质。最后给出了一个分支定界算法,并给出了数值模拟的结果。