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

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

Scheduling on single machine and identical machines with rejection

We consider scheduling problems with rejection for both single machine and identical machines in this paper. For the single machine problems, each job has penalty \alpha times of its processing time. If jobs have release dates, the problem of minimizing 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 problems, 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.