ORF  >> Vol. 9 No. 4 (November 2019)

    同类机上工件实时到达在线排序问题
    Online Scheduling Problem for Jobs Arriving over Time on Related Machines

  • 全文下载: PDF(485KB) HTML   XML   PP.279-284   DOI: 10.12677/ORF.2019.94032  
  • 下载量: 82  浏览量: 348   科研立项经费支持

作者:  

马丽娜:计算与随机数学教育部重点实验室 湖南师范大学数学与统计学院,湖南 长沙;沅陵县第一中学,湖南 怀化;
李荣珩:计算与随机数学教育部重点实验室 湖南师范大学数学与统计学院,湖南 长沙

关键词:
排序问题相关平行机LS算法最坏性能比Scheduling Problem Related Machine LS Algorithm Worst Performance Ratio

摘要:

同类机上工件实时到达的在线排序问题是给定m台分别具有加工速度S1S2···,Sm的同类机器M1M2···,Mm及实时到达的工件序列L=﹛J1J2···,Jn,目标函数是最小化机器的最大完工时间,本文研究了S1=S2=···=Sm-1=1, Sm >1时同类机上工件实时到达的在线排序问题的LS算法,给出并证明了LS算法的最坏性能比。

Online scheduling problem for jobs arriving over time is as follow. We are given m related machines M1M2···,Mm with the processing speed of S1S2···,Sm, respectively and a job list L=﹛J1J2···,Jnarriving over time. The objective function is to minimize the maximum completion time of all machines. In this paper, LS algorithm is considered for online scheduling problem for jobs arriving over time under the assumption S1=S2=···=Sm-1=1, Sm >1. The worst performance ratio of the LS algorithm is given and proved.

1. 引言

同类机排序问题是将n个独立工件 J 1 , J 2 , , J n 分配到m台具有相同功能的机器 M 1 , M 2 , , M m 上加工,每台机器 M i 的加工速度为 s i ( i = 1 , 2 , , m ) ,不妨假设 s 1 s 2 s m ,每个工件只需在其中一台机器上加工一次就能完工,每台机器每次只能加工一个工件。工件 J 1 , J 2 , , J n 之间没有先后的依存关系,

J j ( j = 1 , 2 , , n ) 的大小为 p j ,工件 J j 安排在机器 M i 上加工时所需的时间为 p j s i ,目标函数是使所有

工件在最早时间内完成加工,也就是使得所有机器中最大完工时间达到最小。该问题由Gonzalez [1] 等人首先提出。当 s 1 = s 2 = = s m = 1 时称为相同平行机排序问题,相同平行机排序问题首先由Graham [2] 提出。根据排序者对工件信息的了解程度,排序问题分为离线和在线两种情形,离线情形是指在安排工件前,所有工件信息都已知道,包括工件大小及到达时间等,在线情形是指工件是逐个释放的,只有在当前出现了的工件被安排后下一个工件的信息才能释放。Granham [2] 首先研究了相同平行机在线排序问题,

给出了LS算法并证明了LS算法具有最坏性能比 2 1 m 。LS是指总是安排当前工件在能使这个工件最早

完工的机器上。Cho和Sahni [3] 首先研究了同类机在线排序问题,得到了时LS算法的最坏性能比

1 + 5 2 m 3 时最坏性能比为 1 + 2 m 2 2 ,当 s 1 = s 2 = = s m 1 = 1 , s m > 1 时最坏性能比为 3 4 m + 1 。Berman等 [4] 得到最坏性能比为 3 + 8 5.828 ,并证明了问题的下界为≈4.311。此外,关于机器数m取较小的值时,也有一些结果。例如:当 m = 2 时,Epstein等 [5] 证明了LS是最好的在线算法,其最坏性能比为 min { 2 s + 1 s + 1 , s + 1 s } ,这里的s为加工速度较快的机器与加工速度较慢的机器两者的加工速

度的比值。当 m = 3 时,蔡 [6] 证明了当 s 1 = s 2 = s 1 , s 3 = 1 这一特殊情形下LS算法的最坏性能比。Cai和Yang [7] 也研究了当 m = 3 时的情形,证明了部分情形下LS算法是最好的在线算法。

经典排序问题假设机器开始加工时所有工件都已到达,但实际情况中工件不一定都已到达,所以提出了工件有到达时间的排序问题。有到达时间的在线问题又分为实时到达在线问题和订单到达在线问题。设工件序列 L = { J 1 , J 2 , , J n } J j ( j = 1 , 2 , , n ) 的到达时间为 r j ,如果 r j ( 1 , 2 , , n ) 为任意实数序列,则称其为订单在线排序问题或工件有任意到达时间排序问题 [8],当 r 1 r 2 r n 时我们称其为工件实时到达在线排序问题。易知工件实时到达在线排序问题是订单在线排序问题的特例。文献 [8] 中只讨论相同平行机的订单在线排序问题,即 s i = 1 ( i = 1 , 2 , , n ) 的情形。本文是首次讨论同类平行机的实时到达在线排序问题。

2. 符号及LS算法

我们后面所要引入的符号的的意义如下:

1) Ui表示在 LS 算法下机器 M i ( i = 1 , 2 , , m ) 上面的空闲时间总和。

2) rj和pj分别表示工件Jj的到达时间和工件大小。

3) C max OPT ( L ) 表示在OPT算法下机器的最大完工时间。

4) C max LS ( L ) 表示在LS算法下机器的最大完工时间。

5) Hi表示在LS算法下安排最后一个工件Jn之前机器 M i ( i = 1 , 2 , , m ) 的完工时间。

6) Fi表示在LS算法下安排完所有的工件后机器 M i ( i = 1 , 2 , , m ) 的最后完工时间。

定义1:算法A是一个近似算法, C max A ( L ) C max OPT ( L ) 分别表示在算法A和最优算法下该工件序列的最大完工时间。我们定义

R ( m , A ) = sup L C max A ( L ) C max OPT (L)

为算法A的最坏性能比,其中 L = { J 1 , J 2 , , J n } 为任一符合条件的工件序列。

本文后面我们总是假设m台具有相同功能的机器 M 1 , M 2 , , M m 的加工速度为 s 1 = s 2 = = s m 1 = 1 ,。下面给出LS算法:

LS算法:

设当前工件是 J j ,大小为 p j 及到达时间为 r j ,各个机器当前的完工时间为 L i ( i = 1 , 2 , , m ) ,我们将安排在机器 M k 上,这里 M k 满足如下条件:

min { max { L i , r j } + p j , max { L m , r j } + p j s | i = 1 , 2 , , m 1 } = { max { L k , r j } + p j , k < m max { L k , r j } + p j s , k = m (1)

即算法总是安排当前工件 J j 在能使这个工件最早完工的机器上。

如果(1)中有 L k < r j ,则 J j 在机器 M k 上产生空闲,空闲长度为 r j L k 。下面给出一个实例说明LS算法的应用。设 m = 2 s 2 = s = 2 r 1 = 1 r 2 = 1 r 3 = 2 p 1 = 4 p 2 = 1 p 3 = 4 。显然J1被安排在机器M2的[1, 3]时间段上加工,而J2被安排在机器M1的时间段[1, 2]上加工。J3安排在M1上的起始时间为2,完工时间为6,安排在M2上的起始时间为3,完工时间为5,故按LS算法规则,J3应安排在M2上。

LS算法中每个工件的安排需要找出最早完工的机器,机器台数为m,最多m次可以找出,注意到工件个数为n,所以复杂度为O(mn)。

下面我们分析LS算法的最坏性能比。

3. 定理及其证明

对给定的工件序列 L = { J 1 , J 2 , , J n } ,我们首先给出下面的基本不等式:

C max OPT ( L ) max { j = 1 n p j m + s 1 , r j + p j s | j = 1 , 2 , , n }

引理1:

证明:由基本不等式知有 r i + p i s C max OPT ( L ) U i r n ,所以有 U i C max OPT ( L ) p n s

定理 2:如果 s 1 = s 2 = = s m 1 = 1 , s m = s > 1 ,则实时在线LS算法有性能比:

C max LS ( L ) C max OPT ( L ) { 2 , s m 1 m 2 1 + m 1 m + s 1 min { 3 , s } , m 1 m 2 < s m 1 2 + m 1 m + s 1 , s > m 1

证明:我们不妨设Jn的完工时间即为 C max LS ( L ) ,由LS算法,我们有

s H m + p n s C max LS ( L ) , H i + p n C max LS ( L ) , i = 1 , 2 , , m 1

所以

( m + s 1 ) C max LS ( L ) s H m + p n + ( m 1 ) i = 1 m 1 ( H i + p n ) = j = 1 n p n + i = 1 m 1 U i + s U m + ( m 1 ) p n ( m + s 1 ) C max OPT ( L ) + ( m + s 1 ) ( C max OPT ( L ) p n s ) + ( m 1 ) p n = 2 ( m + s 1 ) C max OPT ( L ) + s ( m 1 ) ( s + m 1 ) s p n

上面第二个不等式由引理1得。

s ( m 1 ) s + m 1 ( m + s 1 ) C max LS ( L ) 2 ( m + s 1 ) C max OPT ( L ) 即有:

C max LS ( L ) C max OPT ( L ) 2

s ( m 1 ) > s + m 1 时,由于 C max OPT ( L ) > p n s ,所以有

因而得到

C max LS ( L ) C max OPT ( L ) { 2 , s m 1 m 2 1 + s ( m 1 ) m + s 1 , s > m 1 m 2 (2)

下面我们假设工件t′是最后一个被 LS 算法安排在机器Mm上加工但在OPT算法下没有安排在Mm上的工件的长度。如果这样的t′不存在,则有 H m C max OPT ( L ) 。如果Jn在OPT算法下安排在机器Mm上,则有

C max LS ( L ) H m + p n s C max OPT ( L )

否则Jn在OPT算法下安排在某一机器 M i ( i { 1 , 2 , , m 1 } ) 上,这时有 p n C max OPT ( L ) ,并且

C max LS ( L ) H m + p n s C max OPT ( L ) + C max OPT ( L ) s 2 C max OPT ( L )

现在我们假设存在这样的t′,设 S U C ( t ) 表示工件t′之后在机器Mm上加工的工件总长度。显然 S U C ( t ) s C max OPT ( L ) t C max OPT ( L ) 。假设在LS算法下工件t′之后Mm上还有空闲,则在OPT算法下从Mm移走工件t′之后不会改变Mm的完工时间,所以 H m C max O P T ( L ) 。分别讨论最优算法里Jn安排在机器Mm上与不在机器Mm上,我可以用t′不存在时同样的方法可得

C max LS ( L ) 2 C max OPT ( L )

假设在LS算法下工件t′之后Mm上没有空闲,由LS算法知

H i + t H m S U C ( t ) s , i = 1 , 2 , , m 1

如果Jn在OPT算法下安排在机器Mm上,则

U m + S U C ( t ) + p n s C max OPT ( L )

所以

H i + C max OPT ( L ) H i + t H m S U C ( t ) s = H m + p n s + U m s U m + S U C ( t ) + p n s C max LS ( L ) + U m C max OPT (L)

整理得

C max LS ( L ) H i U m + 2 C max OPT ( L )

若Jn在OPT算法下没有安排在Mm上,则有 p n C max OPT ( L ) 并且有

C max LS ( L ) H i + p n H i + C max OPT ( L ) H i U m + 2 C max OPT ( L ) , i = 1 , 2 , , m 1

所以不管什么情况都有

C max LS ( L ) H i U m + 2 C max OPT ( L ) , i = 1 , 2 , , m 1

对于Mm s C max LS ( L ) s H m + p n ,所以

C max LS ( L ) C max OPT ( L ) = s C max LS ( L ) + ( m 1 ) C max LS ( L ) ( m + s 1 ) C max OPT ( L ) s H m + p n + i = 1 m 1 H i + 2 ( m 1 ) C max OPT ( L ) ( m 1 ) U m ( m + s 1 ) C max OPT ( L ) = ( s m + 1 ) U m + i = 1 m 1 U i + j = 1 n p n + 2 ( m 1 ) C max OPT ( L ) ( m + s 1 ) C max OPT ( L ) { ( s m + 1 ) C max OPT ( L ) + ( m 1 ) C max OPT ( L ) + ( m + s 1 ) C max OPT ( L ) + 2 ( m 1 ) C max OPT ( L ) ( m + s 1 ) C max OPT ( L ) , s m 1 ( m 1 ) C max OPT ( L ) + ( m + s 1 ) C max OPT ( L ) + 2 ( m 1 ) C max OPT ( L ) ( m + s 1 ) C max OPT ( L ) , s < m 1 { 2 + m 1 m + s 1 , s > m 1 1 + 3 ( m 1 ) m + s 1 , s m 1

结合(2)定理得证。

4. 小结

本文研究了特殊情形下在同类机上工件实时到达的在线排序问题的LS算法,给定m台同类机器 M 1 , M 2 , , M m ,机器加工速度假设为, s m > 1 时,目标函数是最小化机器的最大完工时间,我们给出了LS算法的最坏性能比为

C max LS ( L ) C max OPT ( L ) { 2 , s m 1 m 2 1 + m 1 m + s 1 min { 3 , s } , m 1 m 2 < s m 1 2 + m 1 m + s 1 , s > m 1

进一步的研究可设计比LS算法具有更好性能比的算法。

基金项目

本文得到湖南省教育厅重点课题(编号:16A126)资助。

NOTES

*通讯作者。

文章引用:
马丽娜, 李荣珩. 同类机上工件实时到达在线排序问题[J]. 运筹与模糊学, 2019, 9(4): 279-284. https://doi.org/10.12677/ORF.2019.94032

参考文献

[1] Gonzalez, T., Ibarra, O.H. and Sahni, S. (1977) Bounds for LPT Scheduling on Uniform Processors. SIAM Journal on Computing, 6, 155-166.
https://doi.org/10.1137/0206013
[2] Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429.
https://doi.org/10.1137/0117039
[3] Cho, Y. and Sahni, S. (1980) Bounds for List Schedules on Uniform Pro-cessors. SIAM Journal on Computing, 9, 91-103.
https://doi.org/10.1137/0209007
[4] Berman, P., Chanrikar, M. and Karpinski, M. (2000) Online Load Balancing for Related Machines. Journal of Algorithms Archive, 35, 108-121.
https://doi.org/10.1006/jagm.1999.1070
[5] Epstein, L., Noga J., Seiden, S., Sgall, J. and Woeginger, G.J. (2001) Randomized Online Scheduling on Two Uniform Machines. Journal of Scheduling, 4, 71-92.
https://doi.org/10.1002/jos.60
[6] 蔡圣义. 三台同类机在线排序问题一种特殊情形的研究[J]. 系统工程理论与实践, 2006, 26(7): 41-46.
[7] Cai, S.Y. and Yang, Q.F. (2012) Online Scheduling on Three Uniform Machines. Discrete Applied Mathematics, 160, 291-302.
https://doi.org/10.1016/j.dam.2011.10.001
[8] Li, R.H. and Huang, H.C. (2004) On-line Scheduling for Jobs with Arbitrary Release Times. Computing, 73, 79-97.
https://doi.org/10.1007/s00607-004-0067-1