带准备时间的同类机半在线问题的近似算法

研究了带机器准备时间的两台同类机已知工件最大加工时间的半在线排序问题,讨论了极小化最大工件完工时间这个目标函数,并给出了一个竞争比为分段函数的近似算法.     

机器带准备时间的平行机排序问题的并行阈值算法

针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε＝1/4时,此线性时间算法的最坏情况界为3/4.这是到目前为止最坏情况界最小且时间复杂性为线性时间的算法.进一步通过计算实验,表明并行阈值算法对于3台至50台机器、5至50 000个工件数量的规模下,具备很高效率.     

带准备时间的两台同类机半在线排序

针对机器速度和准备时间不同,探讨了带机器准备时间的两台同类机半在线排序问题,以达到优化工作效率的目的.目标为极小化最大机器完工时间,对于所有工件中最大工件的加工时间已知的这种半在线情形,给出了一个竞争比不少于(s+1)/(2s+1)的MIN半在线算法.     

两台带准备时间的同类机的半在线排序

研究了带机器准备时间的两台同类机的半在线排序问题,这里目标函数为极小化最大机器完工时间.对于所有工件总的加工时间已知的半在线情形,我们给出了一个竞争比为max{52 1,1 bb}的半在线算法,其中b为机器速度.并且算法对于对于机器加工速度b<2时的同型机情形是最好的.     

带机器准备时间的两台机器半在线排序

研究了两台机器的两个半在线排序问题.当机器为有准备时间的同类机时,总加工时间已知;当机器为有准备时间同型机时,最大加工时间已知.对这两个问题,给出了各自的半在线算法,证明了他们的竞争比分别至少为b 1/2b 1和2/3,其中b,为机器速度,b1=1,1＜b2=b.     

复合两信息的同类机半在线排序问题

研究了两台同类机的一个半在线排序问题，当预先知道所有工件的加工时间总和（sum）与最大工件的加工时间（max）及目标为极大化最小机器完工时间的情形时，证明了此问题的竞争比为（3s＋2）／（2s＋2）的半在线算法．     

机器带准备时间的平行机分批排序

首次研究了机器带准备时间的平行机上的分批排序问题,这里的目标函数为极小化工件的最大完工时间,这类问题是NP-难的.我们根据FBLPT算法、Multifit算法和LPT算法,分别对机器是同型机和同类机的两种情形设计出两个近似算法,并证明它们的最差性能比分别不超过(2-1B)[97 (12)k]和53(2-1B).     

工件可拒绝的在线同类机排序

针对带有惩罚费用的工件在同类平行机上的在线排序问题,目标函数为极小化被接收工件的最大完工时间加上被拒收工件的总拒绝费用,给出了一在线算法,证明了该算法的竞赛比不超过,有Z^on/Z^OPT≤1＋ρ。     

带约束的平行机排序问题

讨论了带资源约束和机器准备时间的平行机排序问题，资源约束是指每个机器最多加工κ个工件．首先对一般情况下的同型机的PLPT排序进行了讨论；并首次对同类机排序进行了研究，给出了一个FLPT近似算法，同时对m=2时证明了PLPT排序的最坏情况紧界是2．     

预先知道工件最大加工时间的带机器费用的排序

对大多数排序问题来说，机器集往往是事先给定的，而且在算法进行过程中，机器集是不变的。Imreh和Noga第一次提出了在排序中考虑机器费用的模型。他们研究了所谓的List Model problem，并给出了竞争比为（1＋5的平方根）／2≈1．618的在线算法，同时证明了该模型的任意在线算法的竞争比至少是4／3。本文研究List Model problem的一个半在线情形，我们假设工件的最大加工时间预先知道，我们将给出一个竞争比为19／12≈1．583的半在线算法，同时证明对该问题的这一半在线情形，任意半在线算法的竞争比至少是4／3。这表明部分信息有利于设计更好的算法。     

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

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

关于模糊工期平行机调度问题的若干结果

研究工件工期是模糊数的平行机调度问题,给出最优调度目标函数值在不同分布下该问题的4个性质,证明了Pm|di~=d~|Fmin问题是NP-难的.特别地,分析了当所有工件的dj与ej都相同时,LPT算法所得到的最小满意度相对于最优调度所对应的最小满意度的界.     

平行机上有优先约束的工件的排序问题

考虑有优先约束的单位工件在m台同型机上的排序问题，目标函数是使工件的完工时间之和最少，当机器的台数不确定时这个问题已经得到了解决．该文中指出当机器的台数确定为m(m≥3)时该问题是NP-完备的。     

带有资源约束的两台机器流水作业排序问题

本文研究了带有资源约束的两台机器流水作业中的最小排序长度问题,并证明了[4,5]中提出的F2|pmtn、res 111|C_(max)是强NP—困难的。     

具有相同加工时间单机调度最优交货期和最优排序的确定

研究了工件加工时间相同的确定单机调度最优交贷期和最优加工顺序的问题,且目标函数基于交货期和工件交货时间不准的情况。利用HLP不等式提出了时间复杂度为O（n^2）的最优算法。     

具有不同初始开工时间的P∥Cmax问题

在每台处理机的初始工时间不同的情况下讨论平行机调度问题的Ｍｕｌｔｉｆｉｔ算法。分析了Ｍｕｌｔｉｆｉｔ算法的可行性并证明其最差民政部性能指标界足Ｒｍ（ＭＦ「ｋ」≤１．２９＋１／２＾ｋ。     

各机器上具有相同加工时间F1oW Shop 调度问题

由m台机器构成的Flow Shop，当工件在各机器上加工时间相同时，直觉上，等价于单机问题。本文推测单机情形最优解的性质及其确定策略也应适合此调度模型。本文就一些目标函数验证了这一推测。     

最小化时间表长的平行机调度近似算法研究

讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.     

连续滚动生产作业安排中初始状态非平凡的P//C_(max)问题

以实际中连续滚动生产为背景,研究了一类新的平行机作业安排问题,即初始状态非平凡的Ｐ∥Ｃ_ｍａｘ问题。基于经典的Ｂｉｎ－ｐａｃｋｉｎｇ（装箱）理论和技巧,提出改进的Ｍｕｌｔｉｆｉｔ算法及相应的ＩＦＦＤ装法,并分析算法在最坏情况下的性能指标上界为４／３．最后,提出连续生产中周期滚动式作业安排的实施算法,实现了设备不空闲而连续运行。