具有等级约束的三台机排序问题的可中断在线算法

研究具有等级约束的三台机在线排序问题．机器和工件的等级数均为1或2,工件只能在等级数不超过自身等级的机器上加工,且加工允许中断,目标是极小化最大工件完工时间．如果有两台机器等级为1,给出竞争比为3／2的在线算法,并证明算法是最好可能的;如果只有一台等级为1的机器,也给出竞争比为3／2的在线算法．     

具有优先约束的不完全恒速机排序问题

讨论了任务具有优先约束的可中断不完全恒速机排序问题,若处理机具有不同开始加工时间的可中断排序问题存在最优算法,则相应的不完全恒速机排序问题也有最优算法。     

处理机具有准备时间的Qm,aj｜pj=1｜Cmax排序问题

讨论了处理机具有准备时间的Qm,aj|pj=1|Cmax排序问题,通过这一问题的一个下界,给出了一个最优算法,算法的复杂性为O（m^2）。     

各机器具有相同加工时间的Flow Shop 成组排序问题

本文讨论了m台机器的Folw Shop成组排序问题，工件在不同机器上的加工时间相同，目标函数为极小化完工时间和。给出了一个多项式时间可解的最优算法。     

一特殊情形不可中断的两台可拒绝同型平行机在线排序问题

讨论一特殊情况的两台可拒绝同型机在线排序问题的近似算法.设有两台同型机,工件逐个到达,可以被接受加工,消耗一定的加工时间tj,也可以被拒绝,但要付出一定的罚值pj,目标是要使被加工工件的最大完工时间(makespan)和拒绝工件的罚值之和最小.假设每个工件的罚值和加工长度成固定的比例α∈[0,+∞),即pj=αtj,针对工件加工不可中断情形,设计出算法NPRL,证明其参数竞争比,同时又给出问题下界,它们均为α的分段函数.算法NPRL在α∈0,2 2∪[1,+∞)已达到最优.     

工件可转包加工的排序问题研究

研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS).     

一类加工时间依赖资源的单机排序问题

讨论了一类有准备时间且任务的加工时间依赖资源的单机排序问题.目标函数为最大完工时间与分配给各任务资源消耗量的加权线性组合.给出了问题的若干相关性质.在此基础上,对于任务之间无优先约束和有任意优先约束的情况.分别给出了最优排列算法和最优资源分配方法.并用数值例子作了说明.     

问题1｜pmtn,dj｜hmax的一个最优算法

给出并证明了求解问题１｜ｐｍｔｎ,ｄｊ｜ｈｍａｘ的一个最优算法。     

可中断的多任务平行机排序问题

Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51)研究了如下问题: 有 n 个订单, 其中每个订单 i 含有 n_i 个不同的工件. 所有的订单在零时刻已经到达, 并且工件的加工是可中断的. 每个订单 i有一个权重 \omega_i, 定义订单 i 的完工时间 C_i 为订单 i 最后一个完工工件的完工时间. 目标是找到一个可行排序使得加权总完工时间\sum\limits_{i=1}^n \omega_iC_i 最小. Leung等证明了这个问题是NP-难的, 给出了一个近似算法, 并且分析了该算法的最坏情况界. 但是定理2的证明存在一些错误. 证明了尽管定理2的证明过程存在错误, 但是其结论仍然正确. 另外, 对上述模型的一种特殊情形给出了更好的近似算法.     

具有线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题.在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数.考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量.第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间.对两类问题讨论了最优排序的某些特征.基于对问题的分析,分别给出了求解最优资源分配的方法.结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立.     

带强制工期的可中断平行机排序问题

讨论了在m台同型平行机上,加工带强制工期的n个可中断工件,在机器可空闲条件下,确定一个工件排序,使得提前完工时间和最小.先考虑了问题的复杂性,通过3-划分问题归约,证明了其是强NP-hard的.而后,讨论了强制工期相等的特殊情形,由于工件不允许延迟,问题可能会无可行排序.先讨论了可行性,接着针对可行问题,提出一个算法在多项式时间内获得最优排序.     

带机器准备时间的平行机排序问题

研究了带机器准备时间的m台平行机排序问题,设计出了一个多项式时间近似方案(PTAS),并给出了一个机器数m为固定常数的情形下的全多项式时间近似方案(FPTAS).     

转包且具有不同费用时间段的排序问题

本文研究制造商可以将工件转包给承包商加工的排序模型,承包商仅有一台机器,转包费用由分配给转包工件的不同时间段费用确定.本文分别研究制造商有一台单机及两台自由作业机器环境情形,需要确定被转包工件集及全部工件的加工顺序,使得工件最大完工时间与转包费用和最小.本文利用归约方法对制造商每个机器环境,证明问题NP困难性,并提出动态规划算法.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

机器加工能力受限制的排序问题

本文研究上海港长江口深水航道大型重载船舶的通行问题.利用排序论的理论和方法,把这个问题转换成机器加工能力受到限制的新型排序问题,提出解决这个问题的两个算法,并证明其中一个算法的最优性.     

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

此文考察工时依赖于开工时间的排序问题．文章证明：(1)即使准奋时间完全相同，判断工时与开工时间相关的单台机排序问题是否有可行解也是NP完全的．(2)即使只存在两个不同的截止期，判断工时与开工时间相关的单台机排序问题是否有可行解仍然是NP完全的．(3)当所有工件有相同截止期时，问题是否有可行解可在多项式时间内判定．     

带广义偏序约束的Flow—shop排序问题

本文研究了一种新的排序问题：带“广义偏序”约束的ｆｏｌｗ－ｓｈｐｏ排序问题。如工件Ｊｊ与工件Ｊｋ之间有广义偏序，则Ｊｊ→Ｊｋ，且Ｊｊ的完工时间与Ｊｋ的开工时间的间隔洋小于ｌｊｋ和不大于ｕｊｋ，０≤ｌｊｋ≤ｕｊｋ。问题的目标函数是最大完工时间。     

机器具有学习效应的供应链排序问题

研究了机器具有学习效应的供应链排序问题.有多个客户分布在不同位置,每个客户都有一定数量的工件需要在一台机器上进行加工.每个客户的工件在机器上加工时具有学习效应,即后面加工的工件实际加工时间是逐渐缩短的.工件生产完后需要运输到相应的客户处,每一批配送需要花费一定的时间和费用.这里研究了供应链排序理论中主要的四个目标函数,分析了这些问题的复杂性,对于一些情况给出了它们的最优算法.