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

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

具有传递时间的排序问题

研究具有传递时间的两类单机排序问题，运用交换方法证明最优性条件并设计了相应算法。     

一类调整时间可分离的Flow Shop 排序问题F3│S│Cmax的最优算法

讨论调整时间可分离的Flow Shop排序问题F3│S│Cmax，对其一类特殊情况给出了最优算法。     

具有可变时间的并行排序问题

设有p台处理机要加工n项任务，当每项任务t在时刻i和处理机j上被开始执行时，都有一个不可间断的加工时间l(t，i，j)∈{k1，k2}，我们的目标是要找一个可行方案σ，使得总的完工时间最短．该问题是NP-完备的，本文给出该问题的一个近似算法。     

工件具有指数学习效应的流水作业排序问题

讨论了工件具有学习效应的流水作业排序问题.目标函数为极小化最大完工时间和极小化总完工时间和.利用Gonzalez和Sahni提出的STPT算法规则估计了此两目标函数的最坏情况界,同时举例说明了对于两台机器流水作业的Johnson规则对于本研究问题并不适用.另外,对所讨论的问题的一些特殊情况分别给出了多项式时间算法.     

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

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

一类处理机具有准备时间的恒速机排序问题

讨论任务的加工是不可中断,处理机是恒速机且处理机具有准备时间的排序问题,目标函数是极小化最大完工时间.对于2台处理机的情况,已经有了一个与处理机加工速度有关的排序的界.研究了对于m(m≥2)台处理机的一种特殊情况,给出了一个与处理机加工速度有关的算法的界.     

流水生产中存在调整时间的Lot—Streaming问题

对二台机器流水生产中的ＬＳ问题，以往的研究多为固定分批数，寻找最优分批大小，本文对机器引入调整时间，研究同时决定最优分批数及最优分批大小，并给出了相应最优算法。     

FlowShop排序问题F3／s／Cmax的最优算法

讨论调整时间可分离的ＦｌｏｗＳｈｏｐ排序问题Ｆ３／ｓ／Ｃｍａｘ,对其一类特殊民政部给了优算法。     

一类调整时间可分离的Flow Shop排序问题F3|s|Cmax的最优算法

讨论调整时间可分离的Flow Shop排序问题F3|s|C     

工件加工时间的可控排序问题

讨论离散加工时间可控的排序问题P｜dis_cpt,pmtn｜ n∑j=1Cjtj＋Cmax,应用线性规划松弛方法得到其性能比为e/e-1（≈1.583）多项式时间近似算法.     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

带有学习效应和加工时间可控的排序问题

考虑了带有学习效应和加工时间可控的交货期窗口的单机排序问题。工件的加工时间是关于所分配资源的线性函数或凸函数。其中每一个工件均有一个交货期窗口且窗口大小相同,若工件在窗口之前或之后完工则会产生相应的惩罚,若工件在窗口中完工则无惩罚,目标是通过极小化包括提前,误工工件数、窗口的开始时间、窗口大小和资源消耗的总惩罚函数确定工件的最优排序、最优加工时间和最优资源分配量。在加工时间是线性资源函数的情况下,通过将问题转化为一系列指派问题,构造一个多项式时间算法;在加工时间是凸资源函数的情况下,构造了一个在多项式时间内可解的动态规划算法。     

具有非线性恶化函数和安装时间的 单机排序问题

研究了具有非线性恶化函数的加工时间,同时工件的安装时间与已加工完工件的实际加工时间有关（即p-s-d）的单机排序问题.证明了极小化最大完工时间,极小化完工时间和是多项式时间可解的.另外极小化加权完工时间和,极小化总延误以及极小化最大延误在一定的条件下是多项式时间可解的.     

具有学习效应和非线性安装时间的单机排序问题

讨论了加工工件具有学习效应和安装时间的单机排序问题。文中工件的加工时间不是固定不变的,不仅与工件的加工位置有关,同时还与已加工完成工件的加工时间有关。安装时间分为线性安装时间和非线性安装时间,本文主要讨论的是具有非线性安装时间的情况。工件的安装时间是依赖于已加工完的工件的实际加工时间和工件所排列位置的函数形式。在文中主要证明了极小化最大完工时间,极小化完工时间总和问题是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误问题是多项式可解的。     

加权总完工时间有限的资源约束单机排序问题

讨论工件加工时间依赖于分配给它的一类资源，且加权总完工时间有限，目标函数为极小化资源总量的单机排序问题，对问题1，给出了一个有关最优解中最优资源使用的重要性质并利用该性质，对于bj=b，wj=w,aj=a这种特殊情况给出了最优算法．     

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

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

带有启动时间的GI/G/1排队系统的扩散逼近

为了刻画通信网络中自动请求重发(automatic repeat request,ARQ)通信协议,将其模型化转为一个带有启动时间的GI/G/1排队系统。首先建立了服务员的闲期所满足的上下界函数关系,后利用此关系证明了该排队系统队长、负荷和忙期过程的扩散逼近,近似刻画了系统指标。     

一类安装时间和加工时间受资源约束的成组排序问题

讨论了安装时间和加工时间同时受资源约束的单机成组排序问题．目标函数为在满足最大完工时间限制条件下极小化安装时间消耗资源量与工件消耗资源量的总和．在讨论了问题若干性质基础上，给出了一个最优多项式算法，并用数值例子作了说明．     

一种具有较低切换时延的覆盖网构造和调度算法

为了降低P2P视频广播系统的频道切换和源端时延,提出了一种混合体系结构MTreeTV,能够同时利用P2P覆盖网和流服务器的优点.MTreeTV使用一种新颖的支持邻近性的P2P覆盖网构造和实时数据段调度算法,降低了切换和源端时延并能适应自治节点的高波动.并且通过权衡客户缓冲区大小、连接节点数量、客户带宽、节目速率和服务器服务范围等关键参数,可以进一步提高P2P因特网视频广播系统的性能.分析和仿真结果表明,MTreeTV具有较低的频道切换时延(小于5s),系统开销小(小于2%)并具有很高的播放连续性(大于98%).支持邻近性的P2P覆盖网构造和实时数据段调度算法并结合关键参数的优化,可以大大降低MTreeTV的切换时延.