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

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

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

研究一类工件加工时间和位置有关的单机排序问题．在这一问题中。全部工件有一个待定的共同工期d，目标函数是提前时间，延误时间和工期的加权和达到最小，即惩罚函数最小．通过对问题的分析，将其转化为指派问题，从而证明该问题具有多项式算法．并用一个例子作了说明。     

加工时间依赖工件位置的链约束单机排序问题

讨论了工件加工时间依赖工件位置的链约束单机排序问题．对于链可中断和不可中断两种情形．证明了目标函数为最大完工时间和总完工时间时该问题仍然多项式时间可解．     

加工时间依赖工件位置的树约束单机排序问题

讨论了工件的加工时间依赖于工件位置的树约束单机排序问题,给出了目标函数为最大完工时间的多项式算法.结果表明,最大家庭树中的工件优先于其它家庭树中的工件加工,并且其工件要连续加工所得到的排序为最优排序.     

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

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

加工时间可控的单机排序问题

研究带有学习效应和恶化效应的单机排序问题。在此模型中,工件的学习效应是与工件加工位置相关的减函数,工件的恶化效应是与其开始加工时间相关的线性函数。在无资源约束的情况下,分别讨论了目标函数为最大完工时间、总完工时间及总完工时间的绝对差之和的排序问题,证明了这些问题都是多项式时间可解的。对于带有资源约束问题,若分配一定的资源,工件加工时间会减少。讨论了在线性资源分配情况下,带有学习效应、恶化效应和资源分配量的交货期排序问题,其中所有工件有一个共同的交货期。目的是确定最优交货期、资源分配及工件的加工顺序,使交货期、提前、延误和资源分配量之和最小,通过将其转化为指派问题,证明问题是多项式时间可解的。     

带有可控加工时间和准备时间的单机排序问题

为考察资源分配和退化效应对工件排序的影响,在连续可分但不可再生的资源分配下,工件具有可控准备时间和加工时间的单机排序问题。工件的加工时间是关于退化效应和资源分配的函数,并且在每个工件加工之前,都有一个准备时间,它是有关资源分配的凸函数。本文给出一个最优算法来求解最小化最大完工时间问题。     

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

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

线性加工时间单机成组排序问题

讨论一类线性加工时间成组排序问题．在这一模型中，工件的加工时间是其开工时间的线性函数，全部工件分成若干组．工件的加工必须满足成组技术限制，同组工件间没有安装时间，各组间有与顺序无关的安装时间．目标函数为极小化最大完工时间．基于对问题的分析，给出了多项式算法。     

带准备时间和强制工期的单机排序问题

讨论了带准备时间和强制工期的单机排序问题. 在工件可中断、机器可空闲的条件下,确定一个工件排序,使得最大提前完工时间最小. 由于工件不允许延迟,首先考虑了问题的可行性. 通过将问题转化为一个带容量限制的有向图,并运用求解最大网络流的算法,提出了判定问题可行性的方法. 对于可行问题,给出了一个算法在多项式时间内获得最优排序.     

同时带有安装时间和送出时间的单机排序问题

在实际生产,如钢铁和冶金工业生产过程中,工件在加工之前需要预热或安装必要的夹具和固定装置,在加工之后工件需要进行冷却处理等,也就是工件在进行加工时常常带有安装时间和送出时间。讨论带有学习效应、安装时间和送出时间的单机排序问题。在这一模型中,工件的实际加工时间是与工件的基本加工时间和工件的实际加工位置相关的一般函数。工件的安装时间和送出时间均依赖于已加工完的工件的实际加工时间,即p-s-d形式。目标函数分别为最大完工时间、总完工时间、加权总完工时间、总延误时间、最大延误时间和最大延迟时间,提出了上述问题的最优排序规则。     

带有交货期和加工时间可控的单机排序问题

讨论了带有交货期和工件的加工时间可控的单机排序问题.本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序.然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的.最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nlogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序.     

带有准备时间和退化维护的单机排序问题

研究带有可变加工时间、准备时间和退化维护的公共交货期与凸资源分配的单机排序问题.工件的实际加工时间是关于所分配的不可再生资源量和与工件位置有关的退化效应的函数,并且在每个工件加工之前都有一个准备时间,它是有关资源分配的凸函数.为了消除机器的退化,在规划时间内最多允许执行一次维护活动.在资源总量有限的条件下,确定最优工件排序、最优公共交货期、最优维护位置和最优资源分配方案,使得由工件的提前惩罚、延误惩罚、公共交货期和最大完工时间构成的总费用最小.根据优化的相关知识,将问题转化为匹配问题,给出了该问题的启发式算法.     

加工时间恶化的单机成组排序问题

讨论了一类在成组技术条件下，工件的加工时间恶化的单机排序问题。工件的加工时间是开工时间的线性函数，同时工件组的安装时间也是开始安装时刻的线性函数，同组工件间必须连续加工且没有安装时间，不同组工件间连续加工时有安装时间。基于对问题的分析，给出了多项式算法。     

工时依赖位置的宽容期单机排序问题

研究了共同宽容交货期的单机排序问题,即加工时间是位置的函数,所有工件的提前/延误费用相同,共同宽容交货期的开始时间和大小待定,目标函数最小化的总惩罚费用(包括提前、延误、宽容交货期的定位和大小费用四部分).并给出了最优排序的性质,提出了一个多项式时间算法.     

时间相关的单机排序的最坏竞争比分析

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

任务到达时间依赖资源的单机排序问题

讨论了任务到达时间依赖于分配给它的一类资源约束问题,对问题1|rj=fj(uj),∑^ujj=1≤U^A|Cmax,将已有的一个算法做了改进,对问题1|rj=fj(uj),Cmax≤C^A|∑uj给出了在任意给定排列的条件下求最优解的算法。     

加工时间服从均匀分布的单机随机排序问题

讨论了工件的加工时间服从均匀分布的单机随机调度问题,目标是使拖后工件数的数学期望最小.采用理论分析的方法,研究了工件的最优加工顺序.结果表明:在(1)工件的权重相等(2)工件的权重与工件的平均加工时间成比例的两种情况下,最短期望加工时间优先规则的不可中断静态优先策略和不可中断动态优先策略是确定使拖后工件数最少的优先策略,并对算法的最优性进行了证明.该成果对非正规目标函数的单机随机排序问题的解决具有一定的参考价值和指导意义.     

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

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

工件带运输时间的单机分批排序问题

主要考虑了在线和离线两种模型下的工件带运输时间的单机分批排序问题.工件一但被加工完将会被马上运往目的地.我们考虑了三种限制模型:(1)在线模型:批量B无穷大,工件的加工时间和运输时间一致,即:若工件Ji的加工时间Pi大于等于工件Jj的加工时间pj,那么它们的运输时间有qi≥qj.(2)在线模型:批量B无穷大,工件的最大运输时间和最小的运输时间的比小于等于1 平方根5/2.对于(1),(2)这两种模型我们给出了一个竞争比为1 平方根5/2的在线算法,并且这个结果是最好的.(3)离线模型:批量B有限,当工件的到达时间是整数并且加工时间P=1时,我们给出了一个时间复杂性为O(n2lnn)的多项式时间算法,当工件的加工时间不是1,但工件的到达时间的个数是一个常数m时,我们给出了一个时间复杂性为O(2m-1nlnn)的多项式时间算法.