带机器准备时间的平行机排序问题  

PARALLEL SCHEDULING PROBLEM WITH NON-SIMULTANEOUS MACHINE AVAILABLE TIMES

作　　者：李伟东[1] 李建波[2] 李建平[1] 张同全[3] 

机构地区：[1]云南大学数学与统计学院数学系,昆明650091 [2]昆明理工大学管理与经济学院,昆明650093 [3]云南民族大学数学与计算机科学学院,昆明650031

出　　处：《系统科学与数学》2010年第4期433-440,共8页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(10861012);云南省中青年学术技术带头人基金(2007PY01-21);云南大学校级重点培养基金(2009F04Z)资助课题

摘　　要：研究了带机器准备时间的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.

关 键 词：运筹学 排序 带机器准备时间 多项式时间近似方案 全多项式时间近似方案 

分 类 号：O223[理学—运筹学与控制论]