荣建华, 侯丽英

(1. 石家庄铁道大学四方学院 基础部 河北 石家庄 050000； 2. 南京农业大学 理学院 江苏 南京 210095)



带有到达时间和拒绝费用工件的同类机排序问题

荣建华1, 侯丽英2

(1. 石家庄铁道大学四方学院 基础部 河北 石家庄 050000； 2. 南京农业大学 理学院 江苏 南京 210095)

在线排序；同类机；拒绝费用；竞争比

JournalofZhejiangUniversity(ScienceEdition), 2016,43(5):545-549

0　引　言

排序是运筹学与组合优化领域的一类重要问题，对排序理论的研究具有重要的理论意义和广阔的应用前景.在经典的排序问题中，工件不允许被拒绝，换言之，所有工件都必须被分配到机器上进行加工.然而实际生产中，并非如此.因为厂家可以接受一项有盈利的任务，也可以拒绝存在风险或成本过高的任务，但此时要付出相应的罚值，所以带有拒绝费用的排序问题是现代工业生产中一个新的组合优化模型，它比经典的不可拒绝的排序问题更具普遍性.因现实生活中上述问题比较常见，所以工件可拒绝的排序问题被研究人员广泛关注.

对于排序问题，人们致力于研究其近似算法，通常用竞争比ρA来衡量算法A的优劣.设ZA(I)为用算法A安排实例I所得的目标值，Z*(I)为离线排序下的最优值，则定义ρA=inf{l|ZA(I)≤lZ*(I),∀I}.一个排序问题具有下界ρL是指其竞争比严格小于ρL的算法A不存在.如果某算法A的竞争比与其相应的下界相等，即ρA=ρL，则称该算法为最优近似算法.

1　Qm|rj∈{0,r},online|W的算法设计

令S为工件集，表1为文中所涉及的符号.

表1　符号及含义

证明当△=0时，不等式显然成立.当△≠0时，由△和△*的定义可知，

所……