可拒绝平行批平行机与在线平行批两台一致机排序

论文摘要

平行批排序是现代排序的一个重要模型.其优点是多个工件可以放在同一批中同时进行加工,从而提高工作效率.其中,一个工件批的加工时间定义为这批中所包含的最长工件的加工时间.在这篇文章中,我们研究了两类平行批排序问题.首先我们研究了工件有到达时间并且可拒绝的m台无界平行批平行处理机最小化最大完工时间的排序问题.在该问题中,如果拒绝一个工件,那么要花费一定的惩罚费用；如果接受这个工件,那么该工件被分配到m台机器中的一台上分批加工.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的常数时,我们给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.其次我们研究了在线一致批处理机最小化最大完工时间的排序问题.在该问题中,我们有两个批处理机,一台机器的速度是1,另一台机器的速度为v,其中0<v≤1.所有的工件均依时间在线到达,而在工件到达之前,我们对其信息一无所知.假设α≈0.618是方程α2+α-1=0的正根,而β是方程β3+3β2+（3-1／v）β-1／v=0的正根.对该问题,我们首先建立了其竞争比下界：当0<v≤1／2时,下界为1+α；当1／2≤v≤1时,下界为1+β.上述下界对pj=1的情形也成立.其次我们给出了两个在线算法Delay-Q2和Refined-Delay-Q2.在线算法Delay-Q2的竞争比为max{1+α,min{1+v,1／v+α}}.当0<v≤1／2时,该在线算法是最好可能的,并且对pj=1的情形也是最好可能的,竞争比均为1+α≈1.618.当1／2≤v≤1且pj=1时,在线算法Refined-Delay-Q2是最好可能的,竞争比为1+β.这样,对pj=1的情形,所研究问题已经得到完整解决.

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 问题的背景及相关结果
• 1.2 本文的主要内容
• 第二章 工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题
• 2.1 问题提出及预备知识
• 2.2 动态规划算法
• 2.3 近似算法
• 第三章 在线一致批处理机最小化最大完工时间的排序问题
• 3.1 问题提出及预备知识
• 3.2 下界
• 3.3 两个贪婪算法
• 3.4 改进的在线算法
• j=1时最优在线算法'>3.5 当p_j=1时最优在线算法
• 后记
• 参考文献
• 个人简历、在学期间发表的学术论文及研究成果
• 致谢