典型文献
工件有到达时间及可拒绝下的同类平行机排序问题的近似算法
文献摘要：
本文研究工件有到达时间且可拒绝下的同类平行机排序问题.在该问题中,给定一个待加工工件集,每个工件在到达之后,可以被选择安排到m台同类平行机器中的某一台机器上进行加工,也可以被选择拒绝加工,但需支付一定的拒绝惩罚费用.目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和.当m为固定常数时,设计了一个伪多项式时间动态规划精确算法;当m为任意输入时,设计了一个近似算法,当接受工件个数大于(m-1)时,该算法近似比为3,当接受工件个数小于(m-1)时,该算法近似比为(2+p),其中p为机器加工速度最大值和最小值的比值.最后通过算例演示了算法的运行.
文献关键词：
同类机排序;工件可拒绝;动态规划;近似算法
中图分类号：
作者姓名：
毕春燕;万龙;罗文昌
作者机构：
宁波大学数学与统计学院,浙江宁波315211;江西财经大学信息管理学院,江西南昌330013
文献出处：
引用格式：
[1]毕春燕;万龙;罗文昌-.工件有到达时间及可拒绝下的同类平行机排序问题的近似算法)[J].运筹学学报,2022(02):73-82
A类：
2+p,同类机排序
B类：
到达时间,平行机排序,排序问题,近似算法,加工工件,排到,一台,台机,最大完工时间,拒绝工件,拒绝费用,定常,多项式时间,时间动态,动态规划,精确算法,近似比,加工速度,最小值,演示,工件可拒绝
AB值：
0.333653
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
