三台可拒绝平行机在线排序问题的近似算法

荣建华, 侯丽英

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

三台可拒绝平行机在线排序问题的近似算法

荣建华1, 侯丽英2

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

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

0 引言

在经典的排序文献中，所有的工件都不允许被拒绝，换言之，任何工件都必须被安排到机器上进行加工。然而在工厂实际生产过程中，生产决策者们并非总是如此。在现有的生产资源有限的前提下，为了使企业获得更多的利润，生产厂家有时不得不拒绝一些资源耗费较多但带来的利润却较少的工件，所以工件带拒绝费用的排序问题受到研究人员广泛的关注。本文主要研究了工件带拒绝费用的3台平行机在线排序问题。基本模型描述如下：设有3台机器M1，M2，M3和n个工件J1,J2,…,Jn，每台机器的加工速度相同，每个工件Jj带两个参数(tj,pj),tj表示其加工时间,pj表示其拒绝费用。当工件Jj到达后，生产决策者需马上做出决定，工件可以被拒绝，但要付出一定的拒绝费用；也可以选择被加工，花费一定的加工时间。目标为拒绝工件的总拒绝费用与加工工件的最晚完工时间(makespan)之和最小。进一步,当工件被拒绝时文中设计出H1,H2两套拒绝策略，且两种拒绝策略相互独立，最后输出目标值较好的一种。

1 H算法

为了便于设计算法和分析竞争比，下面对文中涉及到的符号作统一规定：

H算法

(2)最终取目标值较好的方案。

证明 情形1：首先讨论由策略H1生成的排序。

子情形1.1：如果所有工件均被拒绝，则有

子情形1.2：假定不是所有工件被拒绝，令x为策略H1中最后一个完工工件，由LS规则：

(1)

(2)

(3)

情形2：其次讨论由策略H2生成的排序。

子情形2.1：如果所有工件均被拒绝，则有

子情形2.2：如果不是所有工件均被拒绝，令y为策略H2中最后一个完工工件，由LS规则

(4)

(5)

(6)

2 结语

[1]BartalY,LeonardiS,Marchetti-SpaccamelaA,etal.Multiprocessorschedulingwithrejection[J].SiamJournalonDiscreteMathematics,2000,13(1):64-78.

[2]闵啸.一特殊情形不可中断的两台可拒绝同型平行机在线排序问题[J].数学的实践与认识,2006,36(6):163-169.

[3]闵啸.一特殊情形的三台可拒绝同型机在线排序问题[J].嘉兴学院学报,2006,18(3):44-47.

[4]闵啸，张玉才.一个可中断两台可拒绝同型机半在线排序问题[J].浙江大学学报：理学版,2007,34(5):509-514.

[5]MINXiao,KONGXiangqing.Semion-lineschedulingontwoidenticalmachineswithrejection[J].ORTransactions,2009,13(1):29-36.

[6]闵啸，刘静，王玉青. 两台可中断同类机可拒绝半在线排序问题的近似算法[J].浙江大学学报：理学版, 2010,37(5):519-523.

[7]荣建华，侯丽英.带拒绝费用的平行机在线排序[J].石家庄铁道大学学报:自然科学版,2016,29(2): 107-110.

On-line Scheduling on Three Identical Machines with Rejection

Rong Jianhua1, Hou Liying2

(1.Department of Basic Courses,Shijiazhuang Tiedao University Sifang College,Shijiazhuang 051132,China;2.College of Sciences,Nanjing Agricultural University,Nanjing 210095,China)

identical machine;rejection;preemptive;operations research;on-line scheduling；competitive ratio

南京农业大学青年科技创新基金(0506J0116)河北省高等教育教学改革研究与实践项目(2015GJJG293);河北省高等教育科学研究课题 (GJXH2015-291)

荣建华(1981-)，女，硕士，讲师，主要从事组合最优化、近似算法、排序论的研究。E-mail:rongjianhua2006@126.com

O223

A

2095-0373(2017)02-0101-05

2016-06-01 责任编辑:刘宪福

10.13319/j.cnki.sjztddxxbzrb.2017.02.18

荣建华,侯丽英.三台可拒绝平行机在线排序问题的近似算法[J].石家庄铁道大学学报:自然科学版,2017,30(2):101-104.