D-SWPT在线算法竞争比的简易证明方法
|
摘要
竞争比反映了算法构造的调度偏离最优调度的最大程度,是衡量一个算法优劣的重要指标.针对经典在线调度问题1|online,r_j|∑w_jC_j,著名学者Anderson和Potts在2004年给出了在线算法D-SWPT,并证明了其竞争比为2.然而,其证明过于复杂冗长.对此问题,作者提出一个新的简单易学的证明方法,证明了在线算法D-SWPT的竞争比为2.
The competition ratio reflects the maximum degree of deviation from the optimal scheduling constructed by the algorithm,and is an important index to measure the performance of an algorithm. For the classical online scheduling problem 1 |online,r_j| ∑w_jC_j,famous scholars Anderson and Potts presented the online algorithm D-SWPT in 2004,and proved its competition ratio 2. It matches the lower bound of the problem,thus proving that the online algorithm D-SWPT is the best possible online algorithm. However,the competition ratio proof of D-SWPT is too complex and lengthy because of introducing double problems and extended problems. The proof technique is not easy to learn and master. In this paper,for this classical online scheduling problem,we proposed a new proof method,which is easy to learn,i. e.,to change the processing time. By changing the processing time,the competition ratio of online algorithm D-SWPT is proved to be 2.
The competition ratio reflects the maximum degree of deviation from the optimal scheduling constructed by the algorithm,and is an important index to measure the performance of an algorithm. For the classical online scheduling problem 1 |online,r_j| ∑w_jC_j,famous scholars Anderson and Potts presented the online algorithm D-SWPT in 2004,and proved its competition ratio 2. It matches the lower bound of the problem,thus proving that the online algorithm D-SWPT is the best possible online algorithm. However,the competition ratio proof of D-SWPT is too complex and lengthy because of introducing double problems and extended problems. The proof technique is not easy to learn and master. In this paper,for this classical online scheduling problem,we proposed a new proof method,which is easy to learn,i. e.,to change the processing time. By changing the processing time,the competition ratio of online algorithm D-SWPT is proved to be 2.
引文
[1]Pinedo M. Scheduling:Theory,Algorithms,and Systems[M]. 2002,Prentice Hall.
[2]Hall L A,Shmoys D B,Wein J. Scheduling to minimize average completion time:Off-line and online algorithms[J]. Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelpia,PA,USA,1996:142-151.
[3] Ran Ma,Long Wan,Lijun Wei,Jinjiang Yuan. Online bounded-batch scheduling to minimize total weighted completion time on parallel machines[J]. International Journal of Production Economics,2014,(156):31-38.
[4] Ran Ma,Jiping Tao,Jinjiang Yuan. Online scheduling with linear deteriorating jobs to minimize the total weighted completion time[J]. Applied Mathematics and Computation,2016,(273):570-583.
[5]Fiat A,Woeginger G J. Competitive analysis of algorithms[J]. Lecture Notes in Computer Science,1998,(1442):1-12.
[6]Lawler E J,Labetoulle J. On preemptive scheduling of unrelated paralleled processors by linear programming[J].Journal of the ACM,1978,25(4):612-619.
[7]Phillips C,Stein C,Wein J. Minimizing average completion time in the presence of release dates[J]. Mathematical Programming,1998,82(1):199-223.
[8] Anderson E J,Potts C N. Online scheduling of a single machine to minimize total weighted completion time[J].Mathematics of Operation Research,2004,29(3):686-697.
[9]Hoogeveen J A,Vestjens A P A. Optimal online algorithms for single-machine scheduling[J]. Lecture Notes in Computer Science,1996,(1084):404-414.
[10]陶继平.基于实例空间压缩的在线及半在线调度算法的竞争分析[D].上海:上海交通大学,2010.
[11]陶继平,席裕庚.一种新的在线调度算法竞争比分析方法—基于实例空间转换的方法[J].系统科学与数学,200,29(10):1381-1389.
[12]马冉,姚景景,郑玉歌.工件带链约束和尺寸的并行批排序[J].河南理工大学学报:自然科学版,2011,(30)4:502-504.
[2]Hall L A,Shmoys D B,Wein J. Scheduling to minimize average completion time:Off-line and online algorithms[J]. Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelpia,PA,USA,1996:142-151.
[3] Ran Ma,Long Wan,Lijun Wei,Jinjiang Yuan. Online bounded-batch scheduling to minimize total weighted completion time on parallel machines[J]. International Journal of Production Economics,2014,(156):31-38.
[4] Ran Ma,Jiping Tao,Jinjiang Yuan. Online scheduling with linear deteriorating jobs to minimize the total weighted completion time[J]. Applied Mathematics and Computation,2016,(273):570-583.
[5]Fiat A,Woeginger G J. Competitive analysis of algorithms[J]. Lecture Notes in Computer Science,1998,(1442):1-12.
[6]Lawler E J,Labetoulle J. On preemptive scheduling of unrelated paralleled processors by linear programming[J].Journal of the ACM,1978,25(4):612-619.
[7]Phillips C,Stein C,Wein J. Minimizing average completion time in the presence of release dates[J]. Mathematical Programming,1998,82(1):199-223.
[8] Anderson E J,Potts C N. Online scheduling of a single machine to minimize total weighted completion time[J].Mathematics of Operation Research,2004,29(3):686-697.
[9]Hoogeveen J A,Vestjens A P A. Optimal online algorithms for single-machine scheduling[J]. Lecture Notes in Computer Science,1996,(1084):404-414.
[10]陶继平.基于实例空间压缩的在线及半在线调度算法的竞争分析[D].上海:上海交通大学,2010.
[11]陶继平,席裕庚.一种新的在线调度算法竞争比分析方法—基于实例空间转换的方法[J].系统科学与数学,200,29(10):1381-1389.
[12]马冉,姚景景,郑玉歌.工件带链约束和尺寸的并行批排序[J].河南理工大学学报:自然科学版,2011,(30)4:502-504.