【摘 要】
:
所谓排序,就是在一定的约束条件下分配时间资源去完成一些任务,使一个或多个目标达到最优。近年来,在线排序和分批排序是两个发展比较迅速的排序模型。在线排序是指工件信息在其
论文部分内容阅读
所谓排序,就是在一定的约束条件下分配时间资源去完成一些任务,使一个或多个目标达到最优。近年来,在线排序和分批排序是两个发展比较迅速的排序模型。在线排序是指工件信息在其到达之前是一无所知的,并且一旦工件被安排后就不允许再改变。平行分批排序是指机器可以同时加工多个工件,每批的加工时间是这批工件中所有工件加工时间的最大者。一旦批开始加工就不能被中断,直到该批被加工完毕。
本文中,我们研究了一种在线排序模型:带有运输的单机平行分批在线排序问题。在这里,我们有一台批处理机和充分多的车辆。有n个工件J1,J2,Jn,每个工件都分别有一个到达时间rj,加工时间pj和运输时间qj。工件的这些信息在其到达之后我们才能获得。在此问题中,每个工件需要在机器上加工,并且工件一旦完工就由车辆将其运送到目的地。我们的目标函数是最小化所有工件被运到目的地所花费的时间。用Graham等人[4]提出的三参数表示法,我们的问题可以表示为:1|on-line,rj,qj,B|Dmax,其中Dmax=max{Dj|Dj=Cj+qj,1≤j≤n}.本文的主要结果如下:
(1)给出了排序模型1|on-line,rj,qj,B=∞|Dmax的一个竞争比不超过2的在线算法。
(2)给出了排序模型1|on-line,rj,qj,pj=p,prec,B=∞|Dmax一个竞争比为(√5+1)/2的在线算法。该在线算法是最好可能的。
(3)给出了排序模型1|on-line,rj,qj,B<n|Dmax的一个竞争比不超过3的在线算法。
(4)给出了排序模型1|on-line,rj,pj,pj=p,B<n|Dmax一个竞争比为(√5+1)/2的在线算法。该在线算法是最好可能的。
(5)给出了排序模型1|on-line,rj,qj,pj=p,prec,B<n|Dmax一个竞争比不超过2的在线算法。
其他文献
数字图像处理又称为计算机图像处理。今天随着计算机技术的发展,数字图像处理已经成为又一新兴研究领域。在图像处理中有许多方法,例如:概率与统计,偏微分方程(PDEs)。 将偏微
The single and combinational effects of cadmium (Cd) and fluoranthene (FLT) on germination, growth and photosynthesis of soybean seedlings were investigated. Ex
本文主要研究F空间上的线性、非线性算子族的共鸣定理和有界线性算子空间理论.包括以下四个方面内容: 第一章回顾F空间的定义,利用“标准生成拟范数列”ρ给出它的一种特征刻
在云南旱地农业生态系统中,由于作物的选择和搭配不合理,栽培技术措施不配套,水土等自然资源及生产环境不能有效利用与保护,作物生态系统及土地生产力不能有效改善,严重制约
请下载后查看,本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
对于给定的一个实多项式函数f,R[x1,…,xn]中一个非空的有限子集H以及Rn中一个闭长方体∏n i=1[ai,bi],本文给出了一个有效算法,用来计算多项式函数f在集合∏n i=1[ai,bi]∩Zer
请下载后查看,本文暂不支持在线获取查看简介。
Please download to view, this article does not support online access to view profile.
在许多科学与工程领域,从输入—输出数据集估计一个未知函数仍然是一个重要课题。传统的基于方程理论的方法已发展成熟且在实践中成功应用,但是精确的数学模型并不总是存在的,从
在实际工作中经常会遇到一些污染数据,说的是在寿命试验中,元件寿命分布函数可能为两个分布函数的混合,考虑一列非负独立同分布的随机变量,具有不同的分布函数。取a为大于0小于1
本文以竞争理论为基础,研究了多种产品竞争的产品扩散模型和具有G0mpertz增长的三种群竞争模型的定性行为。 借鉴种群动力学与传染病动力学的建模思想,建立了描述多产品在市