【摘 要】
:
本文研究在Lookahead作用下的单位长度工件的单机在线平行分批排序问题。目标函数为求最大按时完工工件个数。平行分批是指,多个工件可以组成一批同时加工,而每一批的加工时
论文部分内容阅读
本文研究在Lookahead作用下的单位长度工件的单机在线平行分批排序问题。目标函数为求最大按时完工工件个数。平行分批是指,多个工件可以组成一批同时加工,而每一批的加工时间等于该批中工件的最长加工时间。用b=∞和b<∞分别表示批容量无限制和有限制。LK_L模型是指,在一时刻点t,在线算法可以预见在时间段(t,t+L)内将要到达工件的全部信息。本文的主要结果如下。(1)当0≤L<1时,证明了一个简单的贪婪在线算法是最好可能的在线算法。该算法的竞争比为1/min{n,b+1},其中n表示工件个数。这意味Lookahead在这种情形下是没有任何帮助的。(2)当1≤L<2时,对b=∞和b<∞本文分别给出了问题的上界为0.39和2/3。同时设计了一个批延迟在线算法,并证明该算法的竞争比分别为1/4(b=∞时)和1/5(b<∞时)。
其他文献
随着社会信息化的高速发展,虹膜识别已成为目前较有推广前途的信息安全与人体生物特征识别的热点研究课题之一,也是应用数学与模式识别等多交叉学科的前沿课题。近年来,在虹
本文主要围绕广义柯西矩阵,广义柯西范德蒙矩阵,成对柯西矩阵展开讨论,归纳总结了它们的若干性质。 首先介绍了广义柯西矩阵的概念,并指出它与具有多重极点的插值问题间的
江泽民同志在十六大报告中 ,十分强调理论创新的重大意义 ,提出理论创新是其他一切创新的前提。对此 ,通过对理论创新的哲学基础的分析 ,论证党的第三次理论创新与坚持马克思
C.H.Papadimiteiou和M.Yannakadis提出了加拿大旅行者问题(Canadian Traveler Problem,简称CTP)。为了制定行走策略,Manasse S M和David S B将在线问题和竞争算法运用到此问
多目标决策问题是现代决策科学的重要组成部分,是运筹学的重要分支。本文针对实际的多目标决策问题的不确定性进行讨论。在人们遇到的实际决策问题中,往往伴随着客观实际的偶
本文主要讨论了具有脉冲的BAM型神经网络模型和脉冲影响的Cohen-Grossberg神经网络模型利用Brouwer不动点定理与使用Lyapunov逐点连续函数分别获得了系统(1)和系统(2)的概周
小波变换是八十年代后期发展起来的应用数学分支,具有多分辨分析的特点,而且在时频两域都具有表征信号局部特性的能力。由于小波分析的时频分析特征,很快就成功地应用于地球物理
在本文中,我们主要研究了两类平面Filippov系统的分支问题.通过运用微分方程的定性理论以及构造适当的Poincaré映射,我们首先讨论了由两个平衡点类型不同的线性系统构成的平