两类带有分族工件的平行分批排序问题

作     者：李士生 

作者单位：郑州大学 

学位级别：硕士

导师姓名：原晋江

授予年度：2008年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：平行分批 在线 运输时间 分族工件 竞争比 近似算法 

摘      要：在平行分批排序模型中,机器可以同时加工属于同一批的多个工件.每批的加工时间是这批工件中所有工件加工时间的最大者.当所加工的工件是分族工件时,不同族的工件不能放在一批进行加工.在线排序模型中,工件的信息在工件到达之前是一无所知的,并且一旦工件被安排后就不允许再改变. 本文研究了两种排序模型:(1)带有分族工件和到达时间的平行机平行批的最小化时间表长排序问题;(2)带有分族工件和运输时间的单机平行批的在线排序问题.主要结果如下. (1)给出了排序模型P|family-jobs,p-batch,r,bn|C的一个多项式时间近似方案(PTAS). (2)给出了排序模型P|family-jobs,p-batch,r,b=∞|C的一个改进的多项式时间近似方案(PTAS). (3)对于排序模型1|on-line,family-jobs,p-batch,r,q,b=∞|L,当不同工件族的个数是常数时,给出了一个竞争比为2的在线算法;当不同工件族的个数任意时,给出一个竞争比为2+ε的在线算法.其中ε是任意小的正常数. (4)给出了排序模型1|on-line,family-jobs,p-batch,agreeable(p,q),r,b=∞|L的一个竞争比不超过2的在线算法.其中不同工件族的个数是任意的. (5)给出了排序模型1|on-line,family-jobs,p-batch,r,agreeable(p,q),bn|L的一个竞争比是2的在线算法.其中不同工件族的个数是任意的. (6).对于排序模型1|on-line,family-jobs,p-batch,r,q,bn|L,当不同工件族的个数是常数时,给出一个竞争比为2+ε的在线算法.其中ε是任意小的正常数.