期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

工件带拒绝费用的三台单机排序问题研究 被引量：1

Three single-machine scheduling problem with rejection cost
下载PDF
导出
摘要 本文对带拒绝费用的排序问题进行了研究,目标是极小化接受工件的最大完工时间与拒绝工件的总拒绝费用之和。对于一种三台机器的特殊情况,提出了一个新的在线算法,并对新算法的竞赛比进行了分析。 Our objective is to minimize the sum of the makespan of the accepeted jobs and the total rejection cost of the rejected jobs.We present a new on-line algorithm for a special case of three machines.We also analyze its competitive ratio.
作者 魏飞 刘守鹏
机构地区 滨州医学院
出处 《山东科学》 CAS 2013年第6期9-13,共5页 Shandong Science
基金 国家自然科学基金(11001117)
关键词 在线排序 竞赛比 同类机 on-line scheduling competitive ratio uniform machine
分类号 O223 [理学—运筹学与控制论]
  • 相关文献

参考文献7

  • 1SLEATOR D D,TARJAN R E. Amortized efficiency of list update and paging rules [ J ]. Comm ACM, 1985, 28 (2) : 202 -208.
  • 2HE Y, MIN X. On-line unifbrm machine scheduling with rejection[ J ]. Computing,2000, 65 (1) : 1 -12.
  • 3ENGELS D W, KARGER D R, KOLLIOPOULOUS S G, et al. Techniques for scheduling with rejection [ J ]. Journal of Algorithms, 2003,49(1 ) :175 - 191.
  • 4EPSTEIN L, NOGA J, W G J. On-line scheduling of unit time jobs with rejection : Minimizing the total completion time [ J ]. Operations Research Letters,2002, 30(6) : 415 -420.
  • 5BARTAL Y, LEONARDI S, MARCHETFI-SPACCAMELA A, et al L. Muhiprocessor scheduling with rejection [ J ]. SIAM J Discrete Math,2000,13 ( 1 ) :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.

共引文献4

同被引文献6

引证文献1

山东科学
2013年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部