首页 | 本学科首页   官方微博 | 高级检索  
     


A simpler competitive analysis for scheduling equal-length jobs on one machine with restarts
Authors:Michael H. Goldwasser  Arundhati Bagchi Misra
Affiliation:a Department of Mathematics and Computer Science, Saint Louis University, St. Louis, MO, USA
b Department of Mathematics and Statistics, Mississippi State University, Mississippi State, MS, USA
Abstract:We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadlines. Chrobak et al. (2007, SICOMP 36:6) introduce a preempt-restart model in which progress toward completing a preempted job is lost, yet that job can be restarted from scratch. They provide a View the MathML source-competitive deterministic algorithm and show that this is the optimal competitiveness. Their analysis is based on a complex charging scheme among individual jobs and the use of several partial functions and mappings for assigning the charges. In this paper, we provide an alternative proof of the result using a more global potential argument to compare the relative progress of the algorithm versus the optimal schedule over time. This new proof is significantly simpler and more intuitive that the original, and our technique is applicable to related problems.
Keywords:Analysis of algorithms   On-line algorithms   Preemption   Scheduling
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号