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

Scheduling on single machine and identical machines with rejection

作　　者：高强[1] 鲁习文[1] 

机构地区：[1]华东理工大学理学院数学系,上海200237

出　　处：《运筹学学报》2014年第4期1-10,共10页Operations Research Transactions

基　　金：国家自然科学基金(No.11371137)

摘　　要：研究了带有拒绝的单机和同型机排序问题.对于单机情形,工件的惩罚费用是对应加工时间的α倍.如果工件有到达时间,目标为最小化时间表长与惩罚费用之和,证明了这个问题是可解的.如果所有工件在零时刻到达,目标为最小化总完工时间与惩罚费用之和,也证明了该问题是可解的.对于同型机排序问题,研究了工件分两批在线实时到达的情形,目标为最小化时间表长与惩罚费用之和.针对机器台数2和m,分别给出了竞争比为2和4-2/m的在线算法.We consider scheduling and identical machines in this paper. penalty α times of its processing time. problems with rejection for both single machine For the single machine problems, each job has If jobs have release dates, the problem of mini- mizing the sum of makespan and total penalty can be solved in polynomial time. If all jobs arrive at time zero, the problem of minimizing the sum of total completion time and total penalty also can be solved in polynomial time. For the identical machines problem- s, jobs arrive over time at two different time points. The objective is to minimize the sum of makespan and total penalty. We design on-line approximation algorithms with competitive ratios 2 or 4 - 2/m for the two cases when the number of machines is two or m, respectively.

关 键 词：排序 可拒绝 在线算法 竞争比 

分 类 号：O223[理学—运筹学与控制论]