有使用限制的两台机器排序问题的近似算法

研究了两台机器有使用限制的排序问题,其中一台机器在给定的一个时间段内不可用,而另一台机器一直可用,目标为最小化最大完工时间.每台机器每次至多可以加工一个工件.工件在加工过程中不可中断.对于该问题,文章给出了一个FPTAS (fully polynomial－time approximation scheme).     

机器使用有限制的两台同类机排序

研究两台同类机的排序问题,其中一台机器在一个给定的时间段内不可用,目标函数为工件的最大完工时间。证明了LPT算法的性能比是max{32,1s2},并说明了这个界是紧的。     

单台机器速度可选择的排序问题

研究一类单台机器具有速度可选择约束的排序问题。引进了有关记号，给出了该问题解的概念。ｍ＝１的情形问题１｜ｓｐｅ．｜ΣＣ＿ｊ和问题１｜ｓｐｅ．｜Σｗ＿ｊＣ＿ｉ具有多项式时间算法，即为所谓的Ｐ问题，但对ｍ为一般情形其计算复杂性尚未解决。     

有限制条件的单台机器的排序问题

根据给定n个工件在一台机器上加工时工件间的先后关系 ,定义了一个n个顶点的有向图D ,简化图D得排序图D ,通过穷举图D 的顶点的拓扑序列 ,搜索出了n个工件完工时间之和最小、机器加工完n个工件总时间最少和延误损失最少的加工顺序 .     

机器有使用限制的两台同类机排序的在线LS算法

研究了机器有使用限制的两台同类机排序问题的在线算法,对于Q2 a(M1)Cmax和Q2 a(M2)Cmax问题,证明了LS算法的竞争比分别为1 s12和s2 s12,并举例说明了这两个界是紧的。     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

一类机器带时间限制的分批排序问题及算法

机器带有时间约束的分批排序问题是一类新型排序问题。本文首次对1,R|B≥n|∑Cj问题进行了研究。并给出了一个伪多项式时间动态规划算法。     

产品中各工件在单台机器上加工时的排序问题

本文考虑的是工件在单台机器上加工随后组装成产品的排序问题．每个产品由一个特殊工件和一个共同工件组成,机器从加工特殊工件转到加工共同工件有一个调整时间,目标是使所有产品完工时间在批可达或工件可达情况下的加权和最小．对两种情况我们都给出了多项式时间算法．     

同时具有学习效应和恶化效应的机器可用限制性排序问题

针对单机和两台机器的平行机排序问题,建立了工件同时具有学习效应和恶化效应,机器有可用性限制的排序模型.考虑了目标函数为极小化总完工时间的单机、两台机器的同型机问题和两台机器的同类机问题.对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法.     

极小化最大完工时间及拒绝费用的单机可拒绝分批排序

首次考虑了工件可拒绝的单机分批排序问题,目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和.对于工件同时到达的情况,本文通过动态规划算法给出了多项式时间的精确算法,借助于数据结构中的堆排序,我们将算法复杂性降低为O(n2logB).     

具有到达时间和禁用区间的单机平行批排序

研究工件带有到达时间且机器带有可用性限制(禁用区间)的单机平行批排序问题.假设机器在一些不交的时间区间上不可用.工件以平行批的形式在机器可用的时间区间上加工,并且不可中断.一个批的加工时间是这一批中加工时间最长的工件的加工时间.对任意的正则目标函数,当工件带有到达时间且机器带有可用性限制时,给出了单机平行批排序问题的一个拟多项式时间算法.     

加工时间为线性增函数有上界的排序问题

本文讨论工件的加工时间是其开工时间的一类线性增加函数有上界的单机排序问题1|pj(t)(t0,T1,T2)|Cmax:设工件集J=J1,J2,…,Jn中的每个工件需要在一台机器上得到加工;工件集J被划分成两组J=Ω1+Ω2;机器上第一个被加工的工件在时刻t00开始加工;Ω1中工件的加工时间为pj(t)=ajt(当tT1)或pj(t)=ajT1(当t≥T1),Ω2中工件的加工时间为pj(t)=ajt(当tT2)或pj(t)=ajT2(当t≥T2),其中T2T1t0均是给定的常数,t表示对应工件的开工时刻;排序的目的是极小化时间表长(最大完工时间)Cm ax。在所得的引理2和引理3的基础上,本文给出一个复杂度为nlogn的多项式时间算法,从而也证明了所讨论的问题是多项式时间可解得的。     

平行批排序最小化最大完工时间在线算法的一个注记

讨论单机、平行批、批容量无界、最小化最大完工时间的在线排序问题.对该排序问题,Zhang等人(G.Zhang,X.Cai and C.K.Wong,On-line algorithms for minimizing makespan on batch processing machines,NavalResearch Logistics,48(2001),241-258.)和Deng等人(X.Deng,C.K.Poon and Y.Z.Zhang,Approximation algo-rithms in batch processing,Journal of Combinatorial Optimization,7(2003),247-257.)两组作者分别独立地给出了同一个竞争比为(5 1)/2的在线算法,并证明该在线算法是最佳可能的.在他们的算法中,在每一批中的加工时间最大的工件,不妨设其准备时间为r而加工时间为p,将被滞后到(1 α)r αp时刻以后加工,其中α=(5-1)/2.对同一问题设计了一个修订的在线算法,其中加工时间为p的工件只需要滞后到αp时刻.该在线算法仍然是最佳可能的,并且在一定意义下,该在线算法是渐近最优的.     

目标函数是最大延误的数学期望的单机随机调度问题

在任务的加工时间和工期是相互独立的随机变量的情况下研究单机随机排序问题,目标函数为最大延误的数学期望。通过理论分析,给出了该问题的不可中断静态优先策略,并通过实例验证。     

最小化时间表长的带有多个工件组单机无界继列批在线排序

考虑了批容量无界情形下带有多个工件组的单机继列分批的在线排序间题.每个工件具有各自的安装时间和加工时间(s,p),属于不同组的工件不能在同一批中加工,目标函数是最小化最大完工时间,给出了此问题的一个竞争比为2的最好可能的在线算法.     

带有不可用区间及拒绝的最大完工时间单机排序问题

研究带有退化效应、拒绝工件及不可用区间的单机排序问题。该问题中,工件可以被排在机器上进行加工,也可以被拒绝,但是需要支付一定的拒绝惩罚。加工工件的开始加工时间越晚,则工件的实际加工时间越大。机器带有不可用区间,在此区间内任何工件都不能被加工。目标函数为所有拒绝工件的拒绝惩罚与接受工件的最大完工时间之和。首先给出了拟多项式时间的动态规划算法,最后得到了一个全多项式近似方案。