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

极小化完工时间和的有界批调度问题(英文) 被引量：3

Minimizing Total Completion Time of Bounded Batch Scheduling
下载PDF
导出
摘要 考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案. We consider the problem of scheduling n jobs with release dates on rn identical parallel batching machines; our objective is to minimize the total completion time. We present a polynomial time approximation scheme （PTAS） for this problem.
作者 李曙光 李国君 赵洪銮
机构地区 山东大学数学与系统科学学院
出处 《应用数学》 CSCD 北大核心 2006年第2期446-454,共9页 Mathematica Applicata
基金 SupportedbytheNationalScienceFoundationofChina(10271065) theScienceandTechnologyResearchKeyItemoftheMinistryofEducationofChina theScienceandTechnologyDevelopmentFoundationofTianjinMunicipalEducationCommission(20051519)
关键词 近似算法 多项式时间近似方案 调度 批加工 完工时间和 Approximation algorithms Polynomial time approximation scheme Scheduling Batch processing Total completion time
分类号 O224 [理学—运筹学与控制论] TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献10

  • 1Afrati F, Bampis E, Chekuri C, Karger D, Kenyon C, Khanna S, Milis I. Queyranne M, Skutella M, Stein C.Sviridenko M. Approximation schemes for minimizing average weighted completion time with release dates[A]. Proceedings of the 40th Annual Symposium on Foundations of Computer Science[C]. New York: IEEE, 1999,32 - 43.
  • 2Cai M, Deng X, Feng H, Li G, Liu G. A PTAS for minimizing total completion time of bounded batch scheduling,International Journal of Foundations of Computer Science,2002,13(6):817-827.
  • 3Chandru V,Lee C Y. Uzsoy R. Minimizing total completion time on batch processing machines[J]. International Journal of Production Research, 1993,31 :2097-2121.
  • 4Chandru V,Lee C Y, Uzsoy R. Minimizing total completion time on a batch processing machine with job families[J]. Operations Research Letters, 1993,13:61-65.
  • 5Chekuri C,Khanna S. Approximation algorithms for minimizing average weighted completion tirne[A].Handbook of Scheduling: Algorithms Models and Performance Analysis[C]. CRC Press,2004.
  • 6Deng X,Feng H ,Li G J ,Shi B Y. A PTAS for semiconductor burn-in-scheduling[J]. Journal of Combinatorial Optimization, 2005,9:5 - 17.
  • 7Graham R L,Lawler E L,Lenstra J K,Rinnooy Kan A H G. Optimization and approximation in deterministic sequencing and scheduling, a survey[J]. Annals of Discrete Mathematics, 1979,5 : 287 - 326.
  • 8Dorit S. Hochbaum, Dan Landy, Scheduling semiconductor burn in operations to minimize total flowtime[J]. Operations Research, 1997,45: 874-885.
  • 9Lawler E L. Combinatorial Optimization: Networks and Matroids[M]. New York: Holt Rinehart and Winston, 1976.
  • 10Lenstra J K, Rinnooy Kan A H G, Brucker P. Complexity of machine scheduling problems[J]. Annals of Discrete Mathematics ,1997,1 : 343-362.

同被引文献94

引证文献3

二级引证文献9

应用数学
2006年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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