赵玉芳, 梁 媛

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

0 引 言

在传统的排序问题中,所有的工件都需要加工。然而,在实际问题中,机器的加工能力有限,若拒绝部分工件反而可能获得更大的利润。因而决策者需要将工件集进行划分,一般分为接受工件集与拒绝工件集。接受工件在机器上加工,拒绝工件外包处理或直接搁置,外包需要支付代加工费,搁置工件也有仓库费用,如此产生拒绝惩罚。恶化效应在现实生活中的很多地方都有体现,比如在钢铁的锻造生产过程中[1]。安装时间也称为调整时间,即机器在处理不同的工件时都有一个调整时间,在实际生产中也是普遍存在的。

对于拒绝问题,Bartal等[2]研究了多处理机排序问题,目标函数是接受工件的最大完工时间与拒绝工件的总拒绝惩罚之和,并给出了近似算法。Gerstl和Mosheiov[3]研究了带有拒绝、工期依赖于工件位置的单机排序问题,目标函数是最大延误或总延误与拒绝惩罚之和,证明了上述2个问题都是NP难的,并给出了伪多项式动态规划算法和启发式算法。Shabtay等[4]综述了带有拒绝的排序问题。Agnetis和Mosheiov[5]研究了带有拒绝、加工时间依赖位置但不依赖于机器的流水作业问题,目标函数是最大完工时间,并证明了问题是多项式时间可解的。工件的恶化效应是由Browne和Yechiali[6]提出的,他们认为工件的加工时间是开始时间的函数,并在假设加工时间为线性恶化模型时,讨论了极小化流水作业问题。Wang和Liang[7]研究了带有成组技术与简单线性恶化效应的单机资源分配问题。……