平行机在线排序综述

平行机排序是一类重要的组合优化问题,列表在线排序是在线问题研究形成和发展的重要推手,也是成果最为丰富的在线问题之一.本文回顾以最大完工时间为目标的在线和半在线排序问题的最新进展,总结工件可拒绝、机器可增加及目标为机器负载的Lp范数等3类复杂目标在线排序问题的主要结果,介绍竞争比近似方案、带建议的在线算法和多样化算法性能指标等3个在线排序新课题.     

平行机半在线排序问题研究(Ⅱ)

继续介绍半在线平行机排序问题的研究进展．主要介绍第二类、第三类半在线模型．研究两个(或两个以上)半在线模型间关系：复合与限制．文章最后给出了一些待研究的问题。     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

带复合信息的三台平行机半在线排序问题

本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题． Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5／4的最优半在线算法．本文将其情况推广到三台机器,给出竞争比为4／3的半在线算法,并得到一个11／9的问题下界．     

预知工件大小上界的平行机排序问题

平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡,大型计算中的并行计算,柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:C_(max)(极小化机器最大负载makespan)和C_(min)(极大化机器最小负载).在不同的目标下,针对m台平行机的一般情况均给出了问题的下界并设计了半在线算法,某些情况下设计的算法是最优算法.     

两台可拒绝同型机半在线排序问题

本文讨论一个两台可拒绝同型机半在线排序问题.当工件到达时,可以被拒绝,但要付出一定的罚值,也可以被接收加工,消耗一定的加工时间.其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小.加工不允许中断.进一步,机器带有两个并行处理子系统,可以提供两种排序方案,最后选取较好的一种.这是第一个在可拒绝同型机排序模型中使用半在线信息,我们设计出一个近似算法,其竞争比为3/2,另外又给出一个√3+1/2≈1.366的下界.     

有使用限制的二台机器流水作业问题

本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形,并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题,给出了一个竞争比为3/2的半在线算法。     

排序问题的定义、分类和在国内的某些研究进展

排序问题是组合最优化中的一个重要分支。然而,由于使用术语混淆,问题表述不清楚,给学习和交流带来困难。本文从国际公认的有关定义出发,提出序列、整序、排序、时间表和排时(安排时间表)等术语的汉语译名和相关定义,阐述目前国际上使用的三参数分类法,回顾国内排序研究的动向,介绍上海地区研究生和青年教师排序问题讨论班的情况、成果和打算。一、排序、排时和整序若干个工件要在一些机器上进行加工,如何安排机器和工件,使得某些要求(目标函数)达到最优,这就是所谓排序问题。排序问题最早是在机器制造中提出,因此沿用机器制造的术语是理所当然的。然而,这并不意味着排序问题仅仅在机器制造中得以应用。事实上,排     

模糊量排序综述

对模糊量排序研究作一个全面回顾 ,包括排序问题的描述、应用背景、排序指标综述及分类、排序方法的合理性、排序方法之间的联系等方面。     

P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

在线约束单机排序问题的启发式算法

由于约束单机排序问题是经典装箱问题的一种推广并且同经典装箱问题有一些相同的特征。本文主要讨论了经典装箱问题的一些启发式算法在在线约束单机排序问题上的推广和最坏界估计。     

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

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

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

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

折扣加权总完工时间问题的半在线排序算法

讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间P→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同Pmin=Pmax     

带机器准备时间的机器覆盖问题的在线、半在线算法

研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.     

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

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

基于在线信息的群评价模型及其偏序集求解方法

在相关研究的基础上,明确界定了在线群评价模型。该模型将在线评价信息用向量评价矩阵来表示,巨量数据转换成易于运算的方式。针对向量难以集结、属性权重难以明确等问题,运用偏序集相关知识对方案进行排序。通过权重排序信息,应用偏序集决策方法,对向量评价矩阵进行变换,得到方案间的比较关系矩阵。用偏序集表示的在线评价模型,不仅能够对方案进行排序,还能用于个性化产品推荐,通过Hasse图能够直观展示方案间的层次关系。最后,依据汽车之家网站提供的汽车产品在线评价信息的例子,体现本文方法的独特性和实用性。     

A Review of On-Line Machine Scheduling:Algorithms and Competitiveness

在过去的十年里，在线算法的研究吸引了广泛的兴趣．本文对在排序和时间表问题中的各种有效的在线算法以及它们的竞争度作一综述．