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

荣建华, 侯丽英

(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时，由△和△*的定义可知，

所以

证毕.

证明设L1,L2,…,Lm为恰要分配x时机器M1,M2,…,Mm上的加工总长度.由LS算法可知：

另一方面，C(A)≤L1+tx,C(A)≤L2+tx,…,

证毕.

对S(0)中的工件，记

将S1(r)中的工件按1,2,…|S1(r)|进行编号.

算法H:

步骤1对于S(0)中的工件，拒绝S2(0)中的工件.记σi(0)(i=0,1,…|S1(0)|)为接收S1(0)中的前i个工件并按LS算法安排加工、拒绝S1(0)中的其他工件所得到的排序.从σi(0)中选取使目标函数最小的排序，记为π1.

步骤2对于S(r)中的工件，拒绝S2(r)中的工件.记(π1,σj(r))(j=0,1,…|S1(r)|)为接收S1(r)中的前j个工件并按LS算法安排加工、拒绝S1(r)中的其他工件所得到的排序.从(π1,σj(r))中选取目标函数最小的排序，记为(π1,π2).

情形1S(r)=φ.

情形1.1k1=0，即在最优排序中拒绝S1(0)中的所有工件.另外，根据S2(0)的定义，S2(0)中的工件在最优排序中也全部被拒绝.又因为S(r)=φ，此时算法H所得的排序是最优的，即WH=W*.

情形1.2k1>0.根据算法有

因为

所以

情形2S(r)≠φ.

情形2.1k1=0,k2=0.此时在最优排序中

此时算法得到的排序最优.

情形2.2k1=0,k2>0.此时在最优排序中，

情形2.3k1>0,k2=0.

情形2.4k1>0,k2>0.

(此时在最优排序中)

证毕.

2　结　语

[1]BARTAL Y, LEONARDI S ,MARCHETTI-SPACCAMELA A,et al. Multiprocessor scheduling with rejection[J]. SIA M J on Discrete Mathematics, 2000,13:64-78.

[2]ZHANG L,LU L,YUAN J.Single machine schedul-ing with release dates and rejection[J]. European Journal of Operational Research,2009,198:975-978.

[3]LU L,NG C T,ZHANG L.Optimal algorithms for single-machine scheduling with rejection to minimize the makespan[J]. International Journal of Production Economics, 2011,130:153-158.

[4]CAO Z, ZHANG Y. Scheduling with rejection and non-identical job arrivals[J]. Journal of Systems Science and Complexity, 2007,20:529-535.

[5]ENGELS D W, KARGER D R, KOLLIOPOULOS S G, et al. Techniques for scheduling with rejection[J]. Journal of Algorithms, 2003,49:175-191.

[6]LU L, ZHANG L, YUAN J.The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan[J]. Theoretical Computer Science, 2008,396:283-289.

[7]LU L,CHENG T C ,YUAN J,et al.Bounded single -machine parallel-batch scheduling with release dates and rejection[J]. Computers & Operations Research, 2009,36:2748-2751.

[8]GAO Q,LU X. Scheduling on single-machine and identical machines with rejection[J]. Operations Research Transactions,2014,18:1-10.

[9]闵啸，何勇.两台可拒绝同类机在线排序问题近似算法的参数性能比[J].高校应用数学学报：A辑，2000，15(3)：326-332.

MIN Xiao, HE Yong. Heuristic of scheduling with rejection on two uniform machines[J]. Applied Math-ematics A Journal of Chinese Universities,2000,15(3)：326-332.

[10]MIN X,LIU J,WANG Y. Optimal semi-online algorithm for scheduling with rejection on two uniform machines[J]. Journal of Combinatorial Optimization,2011,22:674-683.

[11]闵啸，刘静.拒绝可缓冲的2台同类机半在线排序问题的近似算法[J].浙江大学学报:理学版，2014,41(4)：399-405.

MIN Xiao, LIU Jing. Approximate algorithm of semi online scheduling on two uniform machines with a re-

jecting buffer[J]. Journal of Zhejiang University:Science Edition,2014,41(4)：399-405.

Uniformmachineschedulingwitharrivaltimeandrejection.

RONGJianhua1,HOULiying2

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

on-linescheduling;uniformmachine;rejection;competitiveratio

2015-10-29.

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

荣建华(1981-)，ORCID：http//orcid.org/0000-0002-7147-4866,女，硕士，讲师，主要从事排序论、近似算法的研究，E-mail:rongjianhua2006@126.com.

10.3785/j.issn.1008-9497.2016.05.009

O223

A

1008-9497(2016)05-545-05