【摘 要】
：
经典排序问题的研究已经超过半个世纪了,在这方面的研究也有很大的成就。但是经典排序也有它的弊端,就是要求所有工件的信息是透明的,也就是说所有工件的信息在开始加工前都
论文部分内容阅读
经典排序问题的研究已经超过半个世纪了,在这方面的研究也有很大的成就。但是经典排序也有它的弊端,就是要求所有工件的信息是透明的,也就是说所有工件的信息在开始加工前都已经知道。但在实际中,工件的信息有时事先并不知道,而是随着时间的推移而逐个到达。安排者必须在不知道未来工件信息情况下做出决定。这就是在线排序问题。 本文研究的是等长工件在序约束下分批在线排序问题。目标函数是最小化总完工时间。单机的情形三参数表示为1|prec,pj=p,p-batch,online|∑Cj;平行机的情形三参数表示为Pm|prec,pj=p,p-batch,online|∑Cj。在本文的结构安排上,我们先证明单机模型,然后是平行机模型。在每一种情形中,又根据批容量的大小分为批容量有限和无限情形。本文的主要结果如下:(1)对问题1|prec,pj=p,p-batch,b=∞,online|∑Cj,给出最好可能的在线算法,其竞争比为1+α=(?);(2)对问题1|prec,pj=p,p-batch,b<∞,online|∑Cj,给出一个在线算法,其竞争比不大于2;(3)对问题Pm|prec,pj=p,p-batch,b=∞,online|∑Cj,给出最好可能的在线算法,其竞争比为1+αm,其中αm满足(1+αm)m+1-(1+αm)=1;(4)对问题Pm|prec,pj=p,p-batch,b<∞,online|∑Cj,给出一个在线算法,其竞争比不大于2。
其他文献
本文提出了一种新的鲁棒函数观测器设计方法。首先通过求解Sylvester矩阵方程,得到系数矩阵T,L的参数形式。T,L均为自由参数的线性组合的形式,便于进行梯度计算。然后对于矩
带进位反馈移位寄存器(Feedback with carry shift registers)简称FCSR,由它产生的序列简称FCSR序列。2-adic复杂度类似于线性复杂度,所以2-adic复杂度在流密码学应用中有非
城市规划是研究城市的未来发展、城市的合理布局和综合安排城市各项工程建设的综合部署,是一定时期内城市发展的蓝图,城市建设和管理的依据。随着计算机科学的发展,近年来各
邓小平理论与“三个代表”重要思想,既是对马列主义、毛泽东思想的承续,又是创造性的发展,它是和平与发展时代的马克思主义,是当代中国的马克思主义,是全党必须长期坚持的领
有理Bézier曲线是计算机辅助几何设计中常用的一元函数参数形式。由于其具有良好的几何性质和比较成熟的算法，所以备受国内外学者的关注。近年来关于有理Bézier曲线插值与逼
近几十年来，保持问题已经成为国际矩阵论研究中一个十分活跃的领域。这一方面是因为它具有重要的理论价值；另一方面是因为许多问题在量子力学、微分几何、微分方程、数理统计和
数据挖掘是应用数学的一个热门研究领域。近年来,随着计算机技术、通信技术以及网络技术的飞速发展,许多领域中出现了连续到达、持续增长、动态演化的数据,这就是数据流(Data
国有企业是国民经济的支柱,加强国有企业党风廉政建设,建立健全监督制约机制,对于发挥国有企业在国民经济中的主导地位和作用,深入贯彻党的精神,促进国有企业改革与发展,都有
本文主要研究了门限签名体制，内容包括门限秘密共享、(t,n)门限签名和门限代理签名。取得的主要研究成果如下： 1.指出了一个基于单向函数和大整数因子分解问题的动态的(t，n)