共查询到19条相似文献,搜索用时 62 毫秒
1.
2.
3.
单机排序问题1|rj,prmp|∑ωj(1-e^-acj)的动态在线调度 总被引:1,自引:0,他引:1
本首先一般化了可中断的概念,并建立了相应的中断一安装重复模型,然后研究了单机排序问题1|rj,prmp|∑ωj(1-e^-acj)在中断-重复和中断-安装重复模型下的动态在线排序问题,给出了只考虑当前可用信息而不是考虑全部任务信息的在线调度规则。 相似文献
4.
加工时间依赖资源的流水作业资源分配问题 总被引:2,自引:1,他引:1
本研究加工时间受资源影响的流水作业时间表长问题。对问题F2|chain,∑(j=1,n)μj≤U|Cmax给出了问题求最优解的多项式时间算法。 相似文献
5.
几类任务到达时间受资源约束的单机排序问题 总被引:2,自引:1,他引:1
本研究了任务到达时间受资源影响的,与时间表长有关的几个问题。对问题1|rj=bj-ajuj,∑j=1^nju≤U|Cmax的一种特殊情况给出了求任务的最优排序的算法,对问题1|rj=fj(uj),pj=p,Cmax≤C|∑j=1^nuj给出了最优算法;还给出了问题1|rj=fj(uj)|∑j=1^nujΛCmax的一个算法。 相似文献
6.
本文考虑的是平行机排序问题Pm‖Cmax.对此问题Knuth和Kleitman给出了一个近似算法AKK,Graham证明了此算法的最坏情况性能比不大于1+1-1/m/1+|k/m|,而且当k≡0(modm)时这个界是紧的.在本文中我们给出了此算法的一个改进的最坏情况性能比: 1+max{1-1/m/1+k1+1/m,1-1/m-k2/1+k1},其中k1和k2为非负整数且k1m+k2=k.本文证明了当k2≠0时,它好于Graham的结果,同时我们给出了两个实例说明这个界是紧的. 相似文献
7.
研究在一台随机发生故障的机器上加工n个具有同一工期的工件, 使得所谓绝对超前-延误惩罚的数学期望最小的调度问题.详细地讲, 问题中的目标测度是最小化完工时间与公共 工期之绝对偏差和的数学期望. 我们在机器的工作时间服从指数分布的条件下分中断-恢复型问题和中断-重复型问题进行研究(对于中断-重复型要求故障时间服从指数分布或是一 个常数). 主要工作如下: (1)问题规划和预备知识. 建立支持后续工作的定义,关系和事实. 特别地, 证明了一个加工时间为t的工件的完工时间与任一工期之绝对偏差的数学期望是关于变量t的半V型函数; (2) 最优解的性质.给出了最优解的几个特征.最重要的是, 证明了最优解具有半V型性质; (3)算法.讨论了几个关于求所研究问题最优解的计算问题. 相似文献
8.
9.
复合并行机F''''2|m1≥2,m2=1|Cmax排序问题的归并算法研究 总被引:2,自引:0,他引:2
在文献[1]中,已经证明了排序问题F2|m1≥2,m2=1|Cmax是NP完全问题,没有好算法.本文提出了复合并行机F'2|m1≥2,m2=1|Cmax排序问题的一个启发式算法--归并算法,并证明了该算法在最坏情况下的性能比(Performance Ratio)是2m-1/m,且优于文献[2]中算法. 相似文献
10.
关于排序模型1|·|ri≥0|n∑i=1vi的注记 总被引:2,自引:1,他引:1
设 J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少.1978年Kise,Ibaraki,Mine等在条件ri<rj蕴涵di≤dj(对于任何1≤i,j≤n)下,对于任何给定的J找到算法A.他们在论文[1]中"证明"算法A是最优算法.最近,李杉林给出一个例子说明他们的证明中的一个关键引理是错误的.本文作者在书[2]中也沿用了这个错误的"证明".对于算法A的最优性,本文给出一个新的简单的证明. 相似文献
11.
12.
本文给出了Flow shop排序问题Fm/prmu/∑^WjCj的一个启发式算式,其最坏情况的界为m,且是紧界。 相似文献
13.
14.
问题Pm|rj,B|∑Cj的多项式时间近似算法 总被引:2,自引:0,他引:2
本文针对同型机分批排序问题Pm|rj,B|∑Cj进行了研究,给出了该问题在批容量B及机器台数m为常数情况下的多项式时间近似算法(以下简称PTAS);在B为常数时设计出了问题1|rj,B|∑WjCj的计算时间更少的PTAS. 相似文献
15.
16.
P|rj,on-line|∑Cj的一类在线算法与竞争比分析 总被引:1,自引:1,他引:0
本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法SSPT是此问题的一类在线算法,论文引入一个拟时间表,此时间表具有SRPT时间表的部分性质,论文通过此辅助时间表证明了SSPT算法是(3-(1/m))-competitive的. 相似文献
17.
邱淦弟 《数学物理学报(A辑)》2004,24(2):246-250
该文主要讨论亚纯函数的导数具有四个公共小函数时的唯一性问题,考虑了Nevanlinna 四值定理在亚纯函数的导数具公共小函数时的情形,推广并改进了作者近期的一个结果。
相似文献
18.
19.
Summary The paper deals with absolute summability factors for infinite series. The main result obtained in this paper generalizes
a recent paper of Mazhar. 相似文献