荣建华 侯丽英

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



带拒绝费用的平行机在线排序

荣建华1侯丽英2

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

研究了工件带有拒绝费用的m台平行机在线算法，假定有m台平行机M1,M2,…,Mm，n个工件J1,J2,…,Jn,每个工件的加工时间与拒绝费用成固定的比例α(α≥0)，即pj=αtj，当α较大时，即工件的拒绝费用相对于加工时间较大，则将此工件接收加工；当α较小时，即每个工件的拒绝费用相对于其加工时间较小，此时将工件拒绝。文中设计出在线算法PRLS,并证明算法的竞争比为关于参数α的分段函数，且为紧界。

在线排序； 竞争比； 同型机； 拒绝费用；不可中断;运筹学

0 引言

在经典的排序文献中，所有的工件都不允许被拒绝，换言之，任何工件都必须被安排到机器上进行加工。然而在工厂实际生产过程中，生产决策者们并非总是如此。随着社会经济的迅速发展，市场竞争也越来越激烈，为了使企业在市场竞争中立于不败之地，良好的调度管理和有效的控制成本成为企业间竞争的重要因素。因此在现有的生产资源有限的前提下，为了使企业获得最多的利润，生产厂家有时不得不拒绝一些资源耗费较多但带来的利润却较少的工件。基于在实际生产中上述问题比较常见，所以工件带拒绝费用的排序问题受到研究人员广泛的关注[1-4]。本文主要研究了工件带拒绝费用的m台平行机在线排序问题。……