工件可拒绝平行机排序

摘要：

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.

关键词：排序、拒绝费用、完全多项式时间近似算法

所属期刊栏目：42

分类号：O223(运筹学)

在线出版日期：2011-08-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：15-18,22