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

具有就绪时间与先后约束的工件可拒绝排序 被引量：2

Scheduling with Rejection Subject to Release Times and Precedence Constraints
下载PDF
导出
摘要 讨论了具有就绪时间与先后约束的工件可拒绝排序,其目标函数是所拒绝加工工件的总拒绝费用与加工工件的带权总完工时间之和。应用线性规划松弛方法设计了近似算法,得到(3+√3)-近似算法。 A scheduling problem with rejection subject to release times and precedence constraints is researched. The objective function is rejection costs plus weighted total completion times. Applying linear programming relaxation, a（3 ＋√3） -approximation algorithm is obtained.
作者 张峰
机构地区 上海第二工业大学理学院
出处 《上海第二工业大学学报》 2009年第1期1-5,共5页 Journal of Shanghai Polytechnic University
基金 上海市教委项目(No.07zz178) 上海市教委科研创新项目(No.08zy78)
关键词 排序 工件可拒绝 线性规划松弛 scheduling rejection linear programming relaxation
分类号 O223 [理学—运筹学与控制论]
  • 相关文献

参考文献11

  • 1BARTAI Y, LEONARD S, MARCHETTI-SPACCAMELA A. Multiprocessor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics, 2000,13:64- 78.
  • 2ENGELS D W, KARGER D R, KOLLIOPOULOS S G. Techniques for scheduling with rejection[C]//Proceeding of the 6^th European Symposium on Algorithms (ESA'98), Springer LNC, 1461: 490- 501.
  • 3HE Y, MIX. On-line uniform machine scheduling with rejection[J]. Computing, 2000, 65: 1-12.
  • 4EPSTEIN Leah, NOGA John, WOEGINGER G J. On-line scheduling of unit time jobs with rejection[J]. Operations Research Letters 2001, 30:415 - 420.
  • 5HOOGEVEEN H, SKUTELLA M, WOEGINGER G J. Preemptive scheduling with rejection[J]. Math. Programming, 2003,94: 361- 374.
  • 6SELDEN S S. Preemptive multiprocessor scheduling with rejection[J]. Theoretical Computer Science. 2001, 262: 437-458.
  • 7张峰,范静.工件可拒绝排序问题的线性规划松弛算法[J].上海第二工业大学学报,2005,22(5):13-20. 被引量：3
  • 8DOSA G, HE Y. Scheduling with machine cost and rejection[J]. J Comb Optim,2006, 12: 337- 350.
  • 9DOSA G, VESZPREM, HE Y. Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines[J]. Computing, 2006, 76: 149- 164.
  • 10张峰,唐国春.工件可拒绝排序问题的研究[J].同济大学学报（自然科学版）,2006,34(1):116-119. 被引量：3

二级参考文献15

  • 1ZHANGFeng,CHENFeng,TANGGuochun.Convex quadratic programming relaxations for parallel machine scheduling with controllable processing times subject to release times[J].Progress in Natural Science:Materials International,2004,14(9):758-764. 被引量：3
  • 2Bartal Y, Leonard S, Marchetti-Spaccamela A, et al. Multiprocessor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics, 2000,13:64.
  • 3Engles D W, Karger D R, Kolliopoulos S G, et al, Techniques for scheduling with rejection[M]//LNCS. Proceedings of the 6th European Symposium on Algorithms, LNCS 1461. New York:Springer-Verlag, 1998: 490-501.
  • 4Hoogeveen H, Skutella M, Woeginger G J. Preemptive scheduling with rejection[J]. Math Programming, 2003,94:361.
  • 5Skutella M. Convex quadratic and semidefinite programming relaxations in scheduling[J]. J Assn Comput Mach, 2001,48: 206.
  • 6ZHANG Feng,TANG Guochun, CHEN Zhilong. A 3/2-approximation algorithm for parallel machine scheduling with controllable processing times[J]. Oper Res Lett,2001,29:41.
  • 7Bartal Y, Leonard S and Marchetti-Spaccamela A. Multiprocessor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics, 2000,13: 64-78.
  • 8Engels D W, Karger D R and Kolliopoulos S G Techniques for scheduling with rejection[C]. Proceeding of the 6^th European Symposium on Algorithms (ESA'98), Springer LNC, 1461: 490-501.
  • 9Hoogeveen H, Skutella M and Woeginger G J. Preemptive scheduling with rejection[J]. Math. Programming, 2003,94: 361-374.
  • 10Hall L A, Schulz A S, Shmoys D A and Wein J. Scheduling to minimize average completion time: off-line and on-line approximation algorithms[J].Mathematics of Operations Research, 1997, 22:513--544.

共引文献2

同被引文献16

引证文献2

二级引证文献8

上海第二工业大学学报
2009年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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