时间相关的单机排序的最坏竞争比分析 (运筹学与控制论)

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题。工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工。本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比。进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法。     

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

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

两个代理的单机排序问题的多项式时间算法

考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.     

具有延迟时间的自由作业排序问题——最坏性能比分析

研究一类具有延迟时间的自由作业问题，证明在机器台数任意的情况下，一个简单的贪婪算法的最坏性能比不超过2。特别当m＝2时，证明了该算法的最坏性能比为3／2，其中m为机器的台数。     

具有相关调整时间的排序问题

讨论任务具有相关调整时间的排序问题，首先把[2]中关于LPT算法的结论推广到一般算法，然后又进一步将新的结论推广到处理机为恒速机的情况。     

具有维修时间的两台平行机在线排序

在排序问题中,机器可能出现故障或其他原因而需要维修,因此,在加工工件时把维修时间考虑进去是很必要的.对机器维修时间完全重合、可中断的两台平行机排序问题,本文考虑它的在线情形.通过分析不同情形,给出其任意在线算法竞争比的下界为2,并给出一个最好可能的在线算法.     

工件具有指数学习效应的流水作业排序问题

讨论了工件具有学习效应的流水作业排序问题.目标函数为极小化最大完工时间和极小化总完工时间和.利用Gonzalez和Sahni提出的STPT算法规则估计了此两目标函数的最坏情况界,同时举例说明了对于两台机器流水作业的Johnson规则对于本研究问题并不适用.另外,对所讨论的问题的一些特殊情况分别给出了多项式时间算法.     

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

具有传递时间变工时的单机排序问题

确定了具有传递时间变工时的单机排序问题是ＮＰ－完全的，且讨论了它的一些特殊情况。     

加权总完工时间有限的资源约束单机排序问题

讨论工件加工时间依赖于分配给它的一类资源，且加权总完工时间有限，目标函数为极小化资源总量的单机排序问题，对问题1，给出了一个有关最优解中最优资源使用的重要性质并利用该性质，对于bj=b，wj=w,aj=a这种特殊情况给出了最优算法．     

单位操作长度的自由作业问题多项式时间算法

研究了工件操作长度为1或0的自由作业问题.在不同目标函数下,用数学规划及组合方法设计相应的多项式时间算法.     

工件尺寸不同的平行机分批排序

研究了工件有尺寸大小在平行机上的分批排序问题，这里目标函数为工件的极大完工时间，这类问题是m完备的，对同型机情况，给出了它的近似算法PM，并运用了拆分的技巧，证明它的最差性能比不超过11/4-1/m。     

一类具有学习效果的单机排序问题

讨论一类具有学习效果的单机排序问题.在这类问题中,由于学习效果的作用,工件加工时间将逐渐减少.学习效果通过工件正常加工时间的分段线性函数来描述.基于对问题的分析,把目标函数为极小化总惩罚的工期确定问题转化成指派问题,从而得到问题的多项式算法.对于极小化完工时间和与完工时间偏差的双目标问题,其一般情况同样可以转化成指派问题.此外,对于某些特殊情况,给出了极小化最大完工时间问题与完工时间和问题的简便算法.     

求解AFS问题的两种启发式算法在最坏情况下性能比上界的可达性研究

对文献[2]中提出的求AFS问题的次优解的两个简单易行的启发式算法及其品性进行了进一步的研究。由于已证明了其在最坏情况下性能比Cmax（H）／Cmax的上界不去超过2,本文用两个典型的例子证明：对这两种算法,这一上界是可达的。     

平行机问题中GKK算法性能比界的改进

将n个工件分配到m台平行机上加工，在工件的加工不中断及目标函数是极小化最大完工时间的条件下，对其GKK算法的最坏情形性能比界作了改进，并用实例表明了所得新上界的可达性。     

无容量限制的批处理机时间表问题

研究无容量限制的批处理机时间表问题，在工件有到达时间和工期约束下，证明了当工件的到达时间和工期，或到达时间和加工时间一致单调时，该问题是多项式时间可解的；当加工时间和工期一致单调时，该问题是NP困难的。