工件可拒绝的单机分批排序问题研究

摘要：

本文首次考虑工件可拒绝的单机分批排序问题,目标函数是极小化最大完工时间加上被拒绝工件的拒绝费用之和.对于工件同时到达的情况,本文通过动态规划给出了O(n2log B)的精确算法;对于工件不同时到达的情况,本文给出了PTAS算法.

关键词： 分批排序 动态规划 PTAS算法 工件

作者: 王珍 曹志刚 张玉忠

作者单位: 曲阜师范大学运筹与管理学院,山东日照,276826

会议类型: 国内会议

会议名称: 第八届中国青年运筹信息管理学者大会

会议地点: 广西桂林

会议语种:中文

页码: 147-156

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