Online Scheduling with Bounded Migration

• 成果类型: Article
• 署名作者: Sanders, Peter; Sivadasan, Naveen; Skutella, Martin
• 署名单位: Helmholtz Association; Karlsruhe Institute of Technology; Max Planck Society; Technical University of Berlin
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1090.0381
• 发表日期: 2009
• 页码: 481-498
• 关键词: bin-packing; algorithms; time

摘要

Consider the classical online scheduling problem, in which jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by some constant times the size of the arriving job. This constant is called the migration factor. For small migration factors, we obtain several simple online algorithms with constant competitive ratio. We also present a linear time online approximation scheme, that is, a family of online algorithms with competitive ratio arbitrarily close to 1 and constant migration factor.