|
|||||
|
|
| 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法 | |
| 作者姓名： | 刘晓霞 余山杉 罗文昌 |
| 作者单位： | 宁波大学数学与统计学院, 浙江宁波 315211 |
| 基金项目： | 国家自然科学基金（No.11971252）,浙江省自然科学基金（No.LY19A010005） |
| 摘 要： | 考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案. |
| 关 键 词： | 平行分批排序 拒绝 动态规划 近似算法 |
| 收稿时间： | 2019-06-03 |
| 点击此处可从《运筹学学报》浏览原始摘要信息 | |
| 点击此处可从《运筹学学报》下载免费的PDF全文 | |