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

加工时间可控的单台机器排序问题的近似算法 被引量：2

An Approximation Algorithm for Single Machine Scheduling with Controllable Processing Times
原文传递
导出
摘要 本文研究加工时间可控的单台机器的赋权的总完工时间问题.它是一个NP 难问题.我们利用半定规划松弛的技巧给出它的一个1.2752-近似算法. We derive a 1.2752-approximation algorithm for the NP-hard single ma-chine total weighted completion time problem with controllable processing times by the technique of semidefinite programming relaxation.
作者 徐大川
机构地区 中国科学院数学与系统科学研究院应用数学研究所
出处 《数学学报（中文版）》 SCIE CSCD 北大核心 2003年第6期1047-1054,共8页 Acta Mathematica Sinica：Chinese Series
基金 973项目(1998030401) 国家自然科学基金(19731001) 王宽诚教育基金会资助项目(20020903103811)
关键词 加工时间可控 单台机器排序 半定规划 1.2752-近似算法 排序模型 Scheduling with controllable processing times Semidefinite programming Approximation algorithm
分类号 O223 [理学—运筹学与控制论]
  • 相关文献

参考文献17

  • 1Chen Z. L., Lu Q., Tang G., Single machine scheduling with discretely controllable processing times, Operations Research Letters, 1997, 21: 69-76.
  • 2Nowicki E., Zdrzalka S., A survey of results for sequencing problems with controllable processing times,Discrete Applied Mathematics, 1990, 26: 271-287.
  • 3Graham R. L., Lawler E. L., Lenstra J. K. and Rinnooy Kan A. H. G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 1979, 5: 287-326.
  • 4Chen Z. L., Simultaneous job scheduling and resource allocation on parallel machines, Working Paper, Department of Systems Engineering, University of Pennsylvania, Philadelphia, PA, 1999.
  • 5Cheng T. C. E., Chen Z. L. and Li C. L., Parallel machine scheduling with controllable processing times, IIE Transactions, 1996, 28: 177-180.
  • 6Hoogeveen J. A., Woeginger G. J., Scheduling with controllable processing times, Manuscript, Department of Mathematics, TU Graz, Graz, Austria, 1998.
  • 7Huang W., Zhang F., An O(n2) algorithm for a controllable machine scheduling problem, IMA Journal of Mathematics Applied in Business and Industry, 1999, 10: 15-26.
  • 8Vichson R. G., Choosing the job sequence and processing times to minimize total processing plus flow cost on single machine, Operations Research, 1980, 28: 1155-1167.
  • 9Zhang F., Tang G. and Chen Z. L., A 3/2-approximation algorithm for a parallel machine scheduling problem with controllable processing times, Operations Research Letters, 2001, 29: 41-47.
  • 10Skutella M., Semidefinite relaxation for parallel machine scheduling, Proceedings of 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, 472-481.

同被引文献19

  • 1唐国春,孙世杰.可控排序和赶工排序[J].运筹学杂志,1994,13(1):1-4. 被引量：3
  • 2CHENQing-Geng WANGNing HUANGShao-Feng.The Distribution Population-based Genetic Algorithm for Parameter Optimization PID Controller[J].自动化学报,2005,31(4):646-650. 被引量：8
  • 3玄光南 程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004..
  • 4Chen Z L, Lu Q, Tang G. Single machine scheduling with discretely controllable processing times [ J ]. Operations Re- search Letters, 1997 ( 21 ) :69 - 76.
  • 5Nowicki E, Zdrzalka S. A survey of results for sequencing problems with controllable processing times [ J ]. Discrete Applied Mathematics, 1990 (26) :271 - 287.
  • 6Vickson R. Choosing the job sequence and processing times to minimize total processing plus flow cost on a single ma- chine [ J ]. Operations Research, 1980 ( 28 ) : 1155 - 1167.
  • 7Vickson R. Two single machine sequencing problems invol- ving controllable job processing times [ J ]. AIIE Transac- tions, 1980 (12) : 258 - 262.
  • 8Mastrolilli M. A PTAS for the single machine scheduling problem with controllable processing times. 8th Scandinavi- an Workshop on Algorithm Theory [ C ]. Turku, Finland, 2002.
  • 9Jansen K, Mastrolilli M, Solis-Oba R. Approximation schemes for job shop scheduling problems with controllable processing times [ J ]. European Journal of Operational Re- search ,2005 (167) :297 - 319.
  • 10Wan G. Single machine scheduling to minimize total com- pression plus weighted flow cost is NP-hard [ J ]. IPL, 2001 (79) :273 -280.

引证文献2

数学学报（中文版）
2003年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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