带运输时间的若干批处理排序问题的研究

摘要

本文主要研究带运输时间的单机在线批处理排序问题的算法设计及其竞争比分析.每个工件带有到达时间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的最好的在线算法.
　　 第四章总结本文并给出了今后进一步的研究方向和研究内容.