Operations Research Letters On-line Scheduling of Unit Time Jobs with Rejection: Minimizing the Total Completion Time
Operations Research Letters On-line Scheduling of Unit Time Jobs with Rejection: Minimizing the Total Completion Time
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
L. Epstein;J. Noga;G. Woeginger
中科院分区：
文献类型：
--
作者：
L. Epstein;J. Noga;G. Woeginger
本文研究了单机上单位时间工件的在线排序问题，该问题的惩罚与工件相关。作业在线到达（一个接一个），可以接受和调度，也可以以罚款为代价拒绝。目标是最小化被接受工件的总完工时间加上被拒绝工件的惩罚之和。给出了该问题的一个在线算法，其竞争比为1 2（2 + 3）<$1：86602.此外，我们证明了不存在一个在线算法的竞争比优于1.63784。
We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs. We give an on-line algorithm for this problem with competitive ratio 1 2 (2 + √ 3) ≈ 1:86602. Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.