带服务等级约束的单位长度工件排序问题

研究带服务等级约束的等工件长度排序问题.对该问题的离线情形,给出了求解最优解的线性时间算法.对带有两个服务等级的在线情形,证明了该问题的下界为3/2,并给出了两台机上的最优在线算法.     

带两个服务等级约束的三台机排序问题

研究带两个服务等级约束的3台同型机在线排序问题。工件和机器的服务等级为1或2,加工允许中断但不允许引入机器空闲时间,目标是最小化最大完工时间。该文首先证明任意在线算法的竞争比至少是3/2,接着对仅有1台机器等级为1的情形给出了竞争比为5/3的在线算法。     

带模具约束的两台同型机排序问题的改进算法

研究带模具约束的两台同型机排序问题,针对极小化工件最大完工时间的目标函数,与已有的■近似算法相比,增加对最大工件集的处理,得到改进算法的近似比为■,并给出了紧例。     

工件带链约束和尺寸的并行批排序

主要对带链优先约束和尺寸的工件并行批排序问题进行了研究,当工件的加工时间一致时对目标函数是极小化所有工件加工时间之和的情形,借助于拆分的技巧,给出了一个最差性能比为2的近似算法.     

带冲突约束两台平行专用机排序的一个改进算法

研究带冲突约束的两台平行专用机排序问题的一种特殊情形,针对极小化工件最大完工时间的目标函数,与已有的■近似算法相比,考虑了一类专属工件的加工,并对时间窗口作出改进,得到新算法的近似比为■,并给出了紧例。     

带权误工工件数排序问题

本文研究带权误工工件数排序问题.在分析工件间优先关系的基础上,提出一种新的分支定界算法,可以求解85个工件的大型问题.     

一类工件有尺寸且分两次到达的在线分批排序

研究了工件有尺寸大小,有到达时间的在线分批排序,目标函数为工件的极大完工时间。就所有工件有2个到达时间的在线分批排序,给出算法,并证明了算法的竞争比不超过3。     

单机等长区间的在线排序问题研究

在单机区间排序环境中定义了一种新的半在线排序模型:区间是随着时间依次到达的,区间的一切信息,如到达时间、区间长度、权重等在区间的到达时刻才可获知;已知区间实例集中区间的最大权重与最小权重之比为Δ;目标是确定一个工件允许被终端抢先的排序最大化接收区间的总权重。用对手法给出了该问题的一个下界为2,接着用组合分析法设计了该问题的一个在线算法H,并用最小反例法证明其竞争比分别为(1+(4Δ+1)1/2)/2(1≤Δ≤12时)和4(Δ>12时)。表明当Δ=2时,算法H是一个最好可能的在线算法.     

机器带中断的误工问题的近似排序算法

该文讨论两台平行机排序问题,其中一台机器在不确定情况下中断,中断持续时间为D,目标为极小化误工工件数。当工件转移时间T=0时,该文提出该问题的最优算法。当转移时间T>0时为NP难问题,该文提出了一个差界为1的多项式时间的近似算法。     

一类带时间约束的多工件排序优化

研究了多个工件在多台机床上顺序加工,满足不同工件时间约束下总体加工时间最短的排序问题。建立了该问题的0-1整数优化模型,编写了基于LINGO软件的求解方程,算例表明了该模型的有效性。     

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

提出一种工件之间带有链优先约束的平行机排序问题,目标函数为极小化最大完工时间,优先约束为n条链Ti(1≤i≤n,n为任意实数),处理机为m台同速机,用三参数法表示为Pm|chains|Cmax.问题Pm|chains|Cmax是强NP完备的,利用启发式算法的最长加工时间优先规则,给出了一个多项式时间的近似方案.     

机器带故障的两台机排序问题的一个近似算法

讨论机器带故障中断的两台平行机排序问题,目标为极小化误工工件数,在转移时间t=0时的排序问题是问题P2｜D=∞,t=0｜∑u′ij,该文给出了相应的算法,并利用该算法,考虑了当工件转移时间t〉0时的NP难的排序问题P2｜D=∞,t≠0｜∑u′ij。该文使用对前一问题的最优序π^＊当中的工件相交换,使得增加误工工件数尽量少的方法,提出了一个差界为1的多项式时间的近似算法,并给出了证明及算法的计算复杂性。     

使两台和三台平行机的最小完工时间为最大的线性算法

讨论使两台和三台平行机的最小完工时间为最大的线性算法——对偶阈值算法DA m(ε),其中ε是参数。对于问题P2||Cmin,证明对偶阈值算法DA2(1/7)的最坏情况界为6/7,并证明此界为紧界;对于问题P3||Cmin,进而提出层次对偶阈值算法TDA3(ε),并证明当ε取2/11时,算法的最坏情况界为9/11。这些都是线性时间算法中使最坏情况界值为最小的算法。     

并行可替换机床混合流程调度算法研究

针对并行机床混合流程调度特性，分析了两种可替换加工情况调度问题的特点，考虑到调度目标是使所有任务有两台并行机房上的加工时间跨度最小，在此基础上作出了两个相应的推理。推理1得出了一台同机床可以替换时的优化调度方法，推理2得出了两台机床都可以作为替换机床时的优化调度方法，并在分析定界法的基础上，给出了两台并行可替换机床两种情况下的优化调度算法，最后通过仿真实验证明了本算法的有效性。     

不误工工件加工时间之和最小的最优解

误工排序问题是经典排序论中最基本的问题之一。1968年Moore提出解决这个问题的算法,可以在时间O（nlogn）内得到最优解。误工问题推广到以下情况：或者某些工件必须不误工;或者工件的加工时间与工件的权有反向一致性;或者工件的加工时间与工件的权具有反向一致性,并且某些工件必须不误工等等。对于这些误工问题及其推广问题提出了多项式时间算法,证明了算法的最优性,并且证明了算法得到的最优解是所有最优解中不误工工件加工时间之和是最小的。     

机器容量无限的同型机分批排序问题

分别研究了最小化不同目标函数的工件有相同就绪时间和不同就绪时间的同型机分批排序问题,对于所研究的问题设计了伪多项式时间的动态规划算法或者完全多项式时间框架。     

误工工件个数最少的多目标排序问题

考虑在误工工件个数最少的约束条件下使得工件集合的总完工时间为最小的单台机器多目标排序问题.首先要使得误工工件个数∑Uj为最少,著名的Moore-Hodgson算法得到的排序就是一个可行解,并且该算法在遇到误工工件时总是尽可能把加工时间最长的工件放到误工工件集合L中,这也符合使总完工时间∑Cj为最小的目的.然而以往文献中的例子显示,这样得到的解并不总是最优解,这就暗示了该问题的复杂性,因此给出了不同于以往文献的分支定界算法及其Matlab解,简化了计算过程.