Online cardinality constrained scheduling |
| |
| Institution: | 1. Department of Mathematics, University of Haifa, Haifa, Israel;2. Department 1: Algorithms and Complexity, MPI-Inf, Saarbrücken, Germany;3. Faculty of Data and Decision Sciences, The Technion, Haifa, Israel;4. Heinz Nixdorf Institute & Department of Computer Science, Paderborn University, Paderborn, Germany;5. School of Business and Economics, Maastricht University, Maastricht, Netherlands |
| |
| Abstract: | In online load balancing problems, jobs arrive over a list. Upon arrival of a job, the algorithm is required to assign it immediately and irrevocably to a machine. We consider such a makespan minimization problem with an additional cardinality constraint, i.e., at most k jobs may be assigned to each machine, where k is a parameter of the problem. We present both upper and lower bounds on the competitive ratio of online algorithms for this problem with identical machines. |
| |
| Keywords: | Scheduling Load balancing Online algorithms Competitive analysis |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
