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

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

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

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

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

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

生产和运输时间具有一致性的单机在线最优算法

探讨工件带运输时间实时在线排序问题,目标是极小化所有工件被运达目的地的时间.在工件的加工时间和运输时间具备一致性的情况下,即若工件Ji和Jj的加工时间满足pi≥pj,则它们的运输时间有qi≥qj,给出了竞争比为2的最优在线算法.     

已知工件总加工时间的两台同类机半在线问题

研究了已知总加工时间的两台同类机半在线问题.假设工件是分别独立地到达加工机器,并且工件的总加工时间是已知的,目标函数为极大化最小机器负载.将总加工时间标准化后,给出近似算法及其竞争比,并证明此竞争比是紧的.给出此问题竞争比的一个下界1.6180,并由此推出当两台机器的速度比为1.618 0时,算法是最优的,算法的竞争比与最优算法的竞争比之差小于0.089.     

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

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

三划分转化为供应链排序问题

供应链排序研究了两个部分的问题,第一部分是权重不一致的工件在一台机器上加工,第二部分是把加工完的工件分成若干批按照某种运输方式运输,并且运送到预先指定的目的地,目标是求加权完工时间与运费总和最小.我们将用已知的NP-难题三划分问题转化成本问题来证明此供应链问题是一个NP-难问题,并给出此难题的近似的算法.     

期望按期完工工件数最大化算法研究

该文讨论工件加工时间为随机变量的单台机排序极大化期望按期完工工件数问题。在确定性排序问题中，Moore算法给出问题的最优解，但事实上Moore算法的期望值版本不能给出期望按期完工工件数最大化问题的最优解。文章从研究排序中工件的按期完工置信系数人手，结合Moore算法，提出了一个启发式算法，有效地解决了该随机排序问题的实际计算。     

2台并行机上的批在线调度

针对在2台同构并行机上的批在线调度问题,将经典在线调度中工件顺次到达的列表调度,推广为批在线列表调度,其目标函数是使最大完成时间(makespan)最小.给出了一个批在线启发式算法(BLPT-算法),要求在每一个批中的工件按LPT规则调度.证明了该算法的竞争率为3/2,并给出了该算法的一个实例.     

工业生产中一个带有拒绝费用的工件排序问题研究

在工业生产中,生产决策者为了获得最大利润,可能接收一个工件,也可能拒绝一个工件.为了解决哪些工件应该被接收,哪些工件应该被拒绝问题,本文研究了工业生产中一个带有拒绝费用的工件排序问题,对该问题设计了一个动态规划算法.     

带有路径和运输方式选择的供应链排序算法研究

主要研究了在供应链中具有单台机器的单个制造商、多个客户的生产和运输的集成排序问题。以生产排序和运输的总费用达到最小作为目标函数。其中生产排序费用是用工件送达时间的函数表示,发送费用是由固定费用和可变费用组成,可变费用与路径和运输方式的选择有关。对该问题的两类特殊情形给出了基于动态规划的多项式时间算法。     

Q2,rj|sum|Cmin问题的半在线排序

研究了两台平行同类机的一个半在线排序问题.当机器是有准备时间的同类机时,总加工时间已知,给出了一个竞争比至少为b 2/b 3的半在线算法,同时给出了证明.     

到达顾客时间总和最短的排序及运输

生产和运输中的一个重要的问题是把生产和运输相结合.建立一台机器进行加工工件,并且把工件运送给不同目的地的多个顾客,目标函数是使到达顾客的时间最短.此问题在一般情况下是NP-难的.当顾客的数量是固定时,设计了动态规划算法,并对几种特殊情况设计了更有效的算法.     

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

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

机器有等待的工件具有区间限制两台同构并行机上批在线调度

研究两台同构并行机上的批在线调度问题,工件以批方式到达且每个批中有m个工件,每个工件的处理时间限定在一个区间上,只有当前批中工件全部加工完成后才可以加工其后面的工件,目标函数是使最大完成时间最小。针对这一问题,给出了1个批在线启发式调度算法,在同一批中的工件按LPT规则调度。对算法的最坏情况进行了分析并给出了算法的最坏情况比与批中工件数有关,并由计算机程序进行了验证。     

最小化完工时间和为第一目标的的多目标不相容分批排序

研究以工件总完工时间为第1目标的多目标不相容分批排序问题,对于加权总完工时间和最大延误为第2目标的排序问题给出了多项式时间的算法。对于误工工件个数和工件总延误为第2目标的排序问题的不同情况进行了讨论,给出了多项式时间算法或证明了其复杂性。     

机器带周期性维护时段的加工与运输协同排序问题

研究了一类机器带周期性维护时段且完工工件需要运输的新型排序问题。在该问题中,机器需要进行周期性的维护,且被维护时段打断的工件加工不可恢复;工件具有不同的尺寸且工件的加工时间与物理尺寸大小具有一定的比例关系,每个维护时段内只允许加工一个批次的工件;加工完的工件需要由一辆带有容量限制的运输工具运往客户。算法的目标是极小化所有工件加工完成并运送到客户的时间。证明了该问题是强NP-Hard问题,设计了该问题的一个多项式时间近似算法,并证明了该算法的最坏情况界不大于5/3。     

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

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

两个代理的单机排序问题研究

研究了两个代理的单机排序问题.其中第一个代理以完工时间和为目标函数,第二个代理以误工工件个数为目标函数.排序问题的目标是寻找一种排序,使得在第二个代理的目标函数不超过给定上界的情况下,第一个代理的目标函数最小.本文还对这一问题设计了一个拟多项式时间算法.     

工件的预排序及其算法的可行性

在工件排序时,各个工件的加工次序往往存在某些约束.为了寻找一个加工次序,既要满足约束条件,又要使某种指标达现最优或较优,有时需要对原来工件序号进行重新编号.本文给出了一个算法,并验证了它的可行性.