带有拒绝的单机和同型机排序问题

作者：高强; 鲁习文

来源：运筹学学报, 2014, (04): 1-10.

DOI：10.15960/j.cnki.issn.1007-6093.2014.04.001

• 排序
• 可拒绝
• 在线算法
• 竞争比 scheduling
• rejection
• on-line algorithm
• competitive ratio

研究了带有拒绝的单机和同型机排序问题.对于单机情形,工件的惩罚费用是对应加工时间的α倍.如果工件有到达时间,目标为最小化时间表长与惩罚费用之和,证明了这个问题是可解的.如果所有工件在零时刻到达,目标为最小化总完工时间与惩罚费用之和,也证明了该问题是可解的.对于同型机排序问题,研究了工件分两批在线实时到达的情形,目标为最小化时间表长与惩罚费用之和.针对机器台数2和m,分别给出了竞争比为2和4-2/m的在线算法.

• 出版日期2014
• 单位华东理工大学