摘要
研究了带机器准备时间的m台平行机排序问题,设计出了一个多项式时间近似方案(PTAS),并给出了一个机器数m为固定常数的情形下的全多项式时间近似方案(FPTAS).
This paper is concerned with the parallel scheduling problem on m machines with non-simultaneous machine available times. A polynomial-time approximation scheme with running time O（mn） for the general case and a full polynomial-time approximation scheme with running time O（n） for the fixed number m of machines are presented.
出处
《系统科学与数学》
CSCD
北大核心
2010年第4期433-440,共8页
Journal of Systems Science and Mathematical Sciences
基金
国家自然科学基金(10861012)
云南省中青年学术技术带头人基金(2007PY01-21)
云南大学校级重点培养基金(2009F04Z)资助课题
关键词
运筹学
排序
带机器准备时间
多项式时间近似方案
全多项式时间近似方案
Operations research, scheduling, non-simultaneous machine available times polynomial-time approximation scheme, full polynomial-time approximation scheme.
