可拒绝的同类机在线排序(英文) 被引量：1

On-line Scheduling with Rejection on Uniform Parallel Machines

下载PDF

导出

摘要考虑了带拒绝费用的在线同类机排序模型.工件一个一个的到达,到达后或被接受,或以一定的费用被拒绝,目标是最小化最大完工时间与总的拒绝费用之和.我们提供了一个在线算法和分析了算法的竞赛比. We consider the version of on-line uniform machines scheduling with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected at a certain penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejection jobs. We propose an on-line algorithm and analyze the competitive ratio.

作者刘守鹏高明海张玉忠

机构地区滨州医学院卫生管理学院曲阜师范大学运筹与管理学院

出处《大学数学》 2012年第1期27-32,共6页 College Mathematics

基金 The Natural Science Foundation of China under Grant(11001117)

关键词在线排序竞赛比同类机 on-line scheduling competitive ratio uniform machine

分类号 O223 [理学—运筹学与控制论]

引文网络
相关文献

参考文献7

1Sleator D R E. Amortized efficiency of list update and paging rules[J]. Comm ACM. 1985, 28: 202--208.
2He Yong He and Min X. On-line uniform machine scheduling with rejection[J]. Computing, 2000, 65: 1-12.
3Engels D W, Kolliopoulous S G, Sengupta S, Urea R N, Wein J. Techniques for scheduling with rejection[C]// Proceedings of the Sixth European Symposium on Algorithm (ESA11998), Lecture Notes in Computer Science, 1998, 1461: 490--501.
4Leah Epstein, Join Noga, Gerhard J Woeginger. on-line scheduling of unit time with rejection: minimizing the total completion time[J]. Operations Research Letters,2002, 30 : 415--20.
5Bartal Y, Leonardi S, Marchetti--Spaccarnela A, Sgall J, Stougie L. Multiproceeor scheduling with rejection[J]. SIAM J. Discrete Math. , 2000,13: 64--78.
6Cuixia MIAO,Yuzhong ZHANG.ON-LINE SCHEDULING WITH REJECTION ON IDENTICAL PARALLEL MACHINES[J].Journal of Systems Science & Complexity,2006,19(3):431-435. 被引量：4
7Shoupeng LIU,Yuzhong ZHANG.ON-LINE SCHEDULING OF UNIT TIME JOBS WITH REJECTION ON UNIFORM MACHINES[J].Journal of Systems Science & Complexity,2008,21(1):114-118. 被引量：3

二级参考文献15

1Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, and L. Stougie, Multiprocessor scheduling with rejection, SIAM J. Discrete Math., 2000, 13: 64-78.
2S. S. Seiden, Preemptive multiprocessor scheduling with rejection, Theoret. Comput. Sci., 2001,262:437-458.
3Hoogeveen, M. Skutella, and G. J. Woeginger, Preemptive scheduling with rejection, in Proceedings of the Eighth European Symposium on Algorithms (ESA'2000), Lecture Notes in Computers Science,Springer, Berlin, 2000, 1879:268-277.
4D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma, and J. Wein, Techniques for scheduling with rejection, in Proceedings of the Sixth European Symposium on Algorithms (ESA'1998), Lecture Notes in Computer Science, Springer, Berlin, 1998, 1461:490-501.
5Leah Epstein, Join Noga, and Gerhard J. Woeginger, On-line scheduling of unit time with rejection:Minimizing the total completion time, Operations Research Letters, 2002, 30:415-420.
6Xiaotie Deng, Chung Keung Poon, and Yuzhong Zhang, Approximation algorithms in batch processing, J. Comb. Optim., 2003, 7(3): 247-257.
7Xiaotie Deng, Haodi Feng, Pixing Zhang, Yuzhong Zhang, and Hong Zhu, Minimizing mean completion time in a batch processing system, Algorithmica, 2004, 38(4): 513-528.
8D. Sleator and R. E. Tarjan, Amortized efficiency of list update and paging rule, Communications of ACM, 1985, 28: 202-208.
9D. W. Engels, S. G. Kolliopoulous, S. Sengupta, R. N. Uma, and J. Wein, Techniques for scheduling with rejection, in Proceedings of the 6th European Symposium on Algorithm (ESA'1998), Lecture Notes in Computer Science, 1998, 1461: 490-501.
10Leah Epstein, Join Noga, and J. Gerhard Woeginger, On-line scheduling of unit time with rejection: minimizing the total completion time, Operations Research Letters, 2002, 30: 415-420.