【摘 要】
:
本文主要研究带运输时间的单机在线批处理排序问题的算法设计及其竞争比分析.每个工件带有到达时间rj,加工时间乃和运输时间qj.给定一台批处理机,它一次可以同时加工多个工件
论文部分内容阅读
本文主要研究带运输时间的单机在线批处理排序问题的算法设计及其竞争比分析.每个工件带有到达时间rj,加工时间乃和运输时间qj.给定一台批处理机,它一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,并且开工后不允许中断,也不允许插入其他工件,加工时间等于其中最长工件的加工时间.工件一旦加工完毕须立即运往目的地,目标是极小化所有工件最迟到达目的地的时间.本文主要考虑两种情况;运输时间与加工时间相关的批处理在线排序问题和带运输时间的工件分类批处理排序问题.
全文共分四章,第一章介绍了与排序问题相关的一些概念,并概括了本文研究的背景及目前国内外关于批处理排序的研究现状.
第二章研究运输时间与加工时间相关的在线批处理排序问题.当pj≥βqj(β≥0.4472)时,给出了最优算法,竞争比为√5+1/2;当qj=βpj(β≥0)时,给出算法的竞争比为√β2+2β+4-β+1/2,下界为√β+5/β+1+1/2.
第三章研究工件分类在线批处理排序问题.这里属于不同类别的工件不能在同一批次中加工.本章考虑批处理机容量为无穷大且工件分两类时的情形,设计了一个竞争比为2的在线算法.若工件的到达时间都相同,给出了一个动态规划算法.当加工时间与运输时间具有一致性,即若pj≥pj,则qi≥qi,给出了竞争比为√17+3/4的最好的在线算法.
第四章总结本文并给出了今后进一步的研究方向和研究内容.
其他文献
本文主要研究Hausdorff算子在加权Hardy空间上的有界性,得到Hausdorff算子在加权Hardy空间上有界的充分条件.这个条件改进了已知定理的结论,并在尺度意义下是最佳的, 本论文
近年以来,一些房地产投资增幅偏快、房价上涨过高。在房价上涨比较快的地方伴随着商品房结构的不合理,中低价位、中小型房屋严重供不应求。房价上涨与投机性购房相互推动:房价上
数据压缩技术是当今通信、广播、存储和多媒体娱乐等领域的一项必不可少的关键技术。本文应用Java编程实现了基于统计模型、字典模型、RLE的压缩算法的数据压缩程序,并进行了
滤波问题在控制和信号处理领域是较为关键的问题之一。自随机系统的最优滤波理论提出之后,随机系统的Kalman滤波理论被广泛应用于通讯、航天、航空、工业过程控制等领域,但Ka
长期以来,森林火灾检测一直都是世界范围内的一个重要研究课题,对于保护地球环境及人类安全都有着重要意义。相对于传统的传感式火灾探测器,基于智能视频分析的火灾监测技术具有
目前互联网领域主要的搜索引擎服务商如Yahoo、百度、Google等,为用户提供的都是横向的海量信息搜索。而在互联网不断更新和演化的现阶段,我们发现:普通网络用户想找到所需的
AEA(Alopex-based evolutionary algorithm)算法是一种基于Alopex的群体进化算法。本文在AEA的基础上提出了一种改进的算法QIAEA。QIAEA将AEA和二次插值法进行结合,极大提高
由于经济和社会的迅速发展,单桩越来越广泛地使用于工程中,因此能否准确地确定单桩极限承载力对于工程非常重要。静荷载试验是确定单桩极限承载力的最可靠的方法,然而,由于其代价
心率的RR间期是心脏状态的重要表现之一。心脏运动是一个信息变化的过程,每一次心搏都会耗用上一次心搏的部分信息。因此将信息论方法应用于心率的RR间期研究是有意义的。本
随着社会的发展及科学的进步.微分方程的研究与应用已经深入到了自然科学和社会科学的众多领域,其中微分方程定性理论、稳定性理论的发展更加拓广了它的应用范围.在微分方程的