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

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

问题1｜prec｜max{h1（S1）,…,hn（Sn）}的一个最优算法

文中给出并证明了求解问题１｜ｐｒｅｃ｜ｍａｘ｛ｈ１（Ｓ１），…，ｈｎ（Ｓｎ）｝的一个最优算法。     

加工时间和工期一致的单机主次指标排序问题1｜｜∑U｜Tmax

本研究了单机主次指标排序问题1||∑U|Tmax。在加工时间和工期具有一致性的情形下，给出了该问题的多项式时间算法。     

几类任务到达时间受资源约束的单机排序问题

本研究了任务到达时间受资源影响的，与时间表长有关的几个问题。对问题1|rj=bj-ajuj,∑j=1^nju≤U|Cmax的一种特殊情况给出了求任务的最优排序的算法，对问题1|rj=fj(uj),pj=p,Cmax≤C|∑j=1^nuj给出了最优算法；还给出了问题1|rj=fj(uj)|∑j=1^nujΛCmax的一个算法。     

一类资源约束排序问题

引入与研究 1| pj=fj( uj) ,∑uj U| ∑ ( wj Cj+ uj)型资源约束排序问题 .针对系统中加工顺序确定的情况 ,给出三个寻求最优资源分配的算法 ;就 fj=f和 fj=bj+ g,wj=w等情况研究系统的最优排序 .     

复合并行机F''''2|m1≥2,m2=1|Cmax排序问题的归并算法研究

在文献[1]中,已经证明了排序问题F2|m1≥2,m2=1|Cmax是NP完全问题,没有好算法.本文提出了复合并行机F'2|m1≥2,m2=1|Cmax排序问题的一个启发式算法--归并算法,并证明了该算法在最坏情况下的性能比(Performance Ratio)是2m-1/m,且优于文献[2]中算法.     

单机排序问题|r_j,prmp| ∑w_j(1-e~(-ac_j)) 的动态在线调度

本文首先一般化了可中断的概念,并建立了相应的中断—安装重复模型,然后研究了单机排序问题1|rj,prmp| wj(1-e-acj)在中断—重复和中断—安装重复模型下的动态在线排序问题,给出了只考虑当前可用信息而不是考虑全部任务信息的在线调度规则。     

关于问题Pm|intree;pj=1;rj|Cmax的分支定界算法

本文针对一个尚未解决的问题Pm|intree;pj=1;rj|Cmax进行了研究,借助于决策论中的递阶层次结构的概念提出一个全新的分支定界算法,并用这一算法得到了问题Pm|intree;pj=1;rj|Cmax的最优排序．     

关于排序模型1｜·｜ri≥0｜ ∑n i=1 to n vi的注记

设J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件Ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少. 1978年Kise，Ibaraki，Mine等在条件ri〈rj蕴涵di≤dj（对于任何1≤i，j≤n）下，对于任何给定的J找到算法A他们在论文[1]中“证明”算法A是最优算法．最近，李杉林给出一个例子说明他们的证明中的一个关键引理是错误的．本文作者在书[2]中也沿用了这个错误的“证明”．对于算法A的最优性，本文给出一个新的简单的证明．     

处理机具有不同开始加工时间的可中断排序问题

本文对处理机具有的不同开始加工时间的可中断排序问题进行讨论，得到下面结论：若处理机具有相同开始加工时间的可中断排序问题存在最优排序算法，则相应的处理机具有不同开始加工时间的可中断排序问题也存在最优排序算法。     

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

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

单机排序问题最优解的结构及其求法

本文研究了单机排序问题|r_i=0|∑|c_i-d_i|最优解的结构．提出了最优解的紧密规则，以及最优解的近似求法．     

单机排序问题1|rj,prmp|∑wj(1-e-acj)的动态在线调度

本文首先一般化了可中断的概念,并建立了相应的中断-安装重复模型,然后研究了单机排序问题1 |rj,prmp|∑wj(1-c-acj)在中断-重复和中断-安装重复模型下的动态在线排序问题,给出了只考虑当前可用信息而不是考虑全部任务信息的在线调度规则.     

加工时间依赖资源的流水作业资源分配问题

本研究加工时间受资源影响的流水作业时间表长问题。对问题F2|chain，∑（j=1，n）μj≤U|Cmax给出了问题求最优解的多项式时间算法。     

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.     

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

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

单机主次指标排序问题1|(rj, dj) agreeable, pj = p, pmtn|∑Uj|Tmax

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax．在同工期且准备时间和工期具有一致性的情形下，给出了该问题的允许中断抢先的多项式时间算法．     

单机排序问题1｜rj,prmp｜∑ωj（1-e^-acj）的动态在线调度

本首先一般化了可中断的概念，并建立了相应的中断一安装重复模型，然后研究了单机排序问题1|rj,prmp|∑ωj(1-e^-acj)在中断-重复和中断-安装重复模型下的动态在线排序问题，给出了只考虑当前可用信息而不是考虑全部任务信息的在线调度规则。     

不等式｜f（x）｜＋｜g（x）｜〈C的解法

我们会解形如 | ｆ(ｘ) | <ｃ (1)(常数ｃ>0 ,下同 )的不等式 ,实际上不等式 (1)等价于 ｆ2 (ｘ) <ｃ2 ,或者 -ｃ <ｆ(ｘ) <ｃ.解含有绝对值的不等式的关键是去掉绝对值符号 .但如果不等式中含有两个代数式的绝对值 ,比如不等式| ｆ(ｘ) | | ｇ(ｘ) | <ｃ (2 )去掉绝对值符号就不那么容易了 ,通常要把实数集划分成若干个区间来讨论 ,这样不仅有划分数集的繁难 ,还有解多个不等式的琐碎 .因此 ,我们设想 ,能不能通过一种变换 ,将不等式 (2 )转化为形如 (1)的基本不等式求解 ,从而回避或者简化这种繁难和琐碎呢 ?这样的变换是有的 ,而且出人…     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.