Preemptive and Non-preemptive On-line Algorithms for Scheduling with Rejection on Two Uniform Machines |
| |
Authors: | G Dósa Y He |
| |
Affiliation: | (1) Department of Mathematics, University of Veszprém, 8201 Veszprém, Hungary;(2) Department of Mathematics and State Key Lab of CAD & CG, Zhejiang University, Hangzhou, 310027, P. R. China |
| |
Abstract: | In this paper, we consider the problem of on-line scheduling a job sequence on two uniform machines. A job can be either rejected,
in which case we pay its penalty, or scheduled on machines, in which case it contributes its processing time to the makspan
of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule for all accepted jobs and
the penalties of all rejected jobs. Both preemptive and non-preemptive versions are considered. For the preemptive version,
we present an optimal on-line algorithm with a competitive ratio for any s≥1, where s is the machine speed ratio. For the non-preemptive version, we present an improved lower bound. Moreover, as an optimal algorithm
for s≥1.6180 is known, we present a modified version of the known algorithm, and show that it becomes optimal for any 1.3852≤s<1.6180 and has a smaller competitive ratio than that of original version for any 1≤s<1.3852. The maximum gap between its competitive ratio and the lower bound is 0.0534. |
| |
Keywords: | 90B35 90B27 |
本文献已被 SpringerLink 等数据库收录! |
|