Online scheduling with machine cost and rejection |
| |
| Authors: | J. Nagy-Gyö rgy |
| |
| Affiliation: | a Department of Mathematics, University of Szeged, Aradi vértanúk tere 1, H-6720 Szeged, Hungary
b Department of Informatics, University of Szeged, Árpád tér 2, H-6720 Szeged, Hungary |
| |
| Abstract: | In this paper we define and investigate a new scheduling model. In this new model the number of machines is not fixed; the algorithm has to purchase the used machines, moreover the jobs can be rejected. We show that the simple combinations of the algorithms used in the area of scheduling with rejections and the area of scheduling with machine cost are not constant competitive. We present a 2.618-competitive algorithm called OPTCOPY. |
| |
| Keywords: | Online algorithms Scheduling Competitive analysis |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
