LS排序的界

讨论任务的加工是不可中断,处理机是同速机的排序问题Pm,ai||Cmax,证明了用Ls算法求解该问题的误差界是2-1/m．     

具有学习效应的平行机排序问题

针对具有学习效应的平行机排序模型,讨论了两类问题。在这一模型中,工件的实际加工时间不仅与其所在排序中的位置有关并且与其本身的学习率有关,对于在同一台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。第1类问题的目标函数是极小化提前与延误的加权和;第2类问题的目标函数是极小化提前与误工工件数的加权和。对这两类问题分别给出了多项式算法。     

一个多物资网络流问题的逼近算法

给出最小满意率最大双标准最大多物资网络流问题,并证明其解存在.建构辅助网络,运用Korte和Vygen于2000年在Young, Garg和Knemann等工作的基础上给出的求最大多种物资网络流问题的ε-逼近解的完全多项式算法作子程序和二分收索方法做出一个求所给问题的解的拟多项式逼近算法.分析算法的复杂性,给出并证明算法的逼近程度.     

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

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

一类资源约束排序问题1|p_j=b_j-a_ju_j,∑u_j≤U|∑W_jC_j

讨论了一类资源约束排序问题１｜ｐｊ＝ｂｊ－ａｊｕｊ，∑ｕｊ≤Ｕ｜∑ＷｊＣｊＷ＊的性质给出了一个求 该类问题的下降算法．这个方法是非常有效的．     

一类安装时间受资源约束的单机成组排序问题

讨论了具有连续资源的单机成组排序问题。在这类问题中,同一组内的工件不允许分开加工,各工件组的安装时间是所消耗资源的线性非增连续函数,同一组内的工件具有同位置有关的学习效应。考虑三类问题,第一类问题的目标函数是在满足最大完工时间限制条件下,极小化资源消耗总量;第二类问题是在满足资源消耗总量限制条件下,极小化最大完工时间;第三类问题是在满足资源消耗总量限制条件下,极小化最大完工时间与资源加权消耗总量的加权线性组合。对三类问题分别给出了求解最优资源分配的方法,并通过数值例子进行了说明。     

带有维修活动和交货期窗口的单机排序问题

【目的】带有维修活动和交货期窗口的单机排序问题在现实生活中有着广泛的应用。每个工件都有属于自己的交货期窗口,工件在交货期窗口外完工,就会产生相应的提前、延误惩罚。因此,确定交货期窗口位置具有重要意义。【方法】考虑了 2 种维修活动:依赖于时间、资源的维修活动;依赖于位置、资源的维修活动。针对不同的维修位置,将问题转化为指派问题。【结果】给出了计算复杂性是 O ( n4 )的多项式时间算法。【结论】证明了该问题是多项式时间可解的。
     

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

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

带有维修活动和工件可拒绝的单机排序问题

讨论了带有交货期、维修活动和工件可拒绝的单机排序问题,这一问题是将所有的工件分成2个集合,分别是被接受的工件集和被拒绝的工件集。规定每个被接受的工件都有一个待定的交货期,且所有工件的交货期的大小相同。如果工件在交货期内完工,则不产生任何费用,否则工件提前或延误,会产生相应的提前或延误的费用。而对于拒绝工件而言,它的费用只与工件有关。维修活动需要在一个固定的时间长度内完成,排在维修活动之后的工件的加工时间将会减少。这类问题的总费用是2个工件集的费用之和,目标函数是确定被接受工件的最优排序,极小化接受工件和拒绝工件的总费用,该问题在多项式时间可解,在今后的应用中能发挥作用。     

一类带有安装时间的单机成组排序问题

针对一类带有准备时间和安装时间的单机成组排序问题,给出了求解最优排序的多项式算法。其中每个工件都具有自己的准备时间,组和组之间具有安装时间,并且安装时间和已经加工完工件的加工时间有关。所有工件在机器上加工时,一次只能加工一个工件,工件不可中断,组内工件连续加工,组和组之间需要安装时间。对目标函数为极小化最大完工时间的单机成组排序问题,给出了求解最优排序的多项式算法。原问题不是成组问题,为此在原问题的基础上添加了工件的成组问题且组内每个工件都具有自己准备时间,其结果是依然能给出求解最优排序的多项式算法。