Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Online nonpreemptive scheduling of equal-length jobs on two identical machines

Online nonpreemptive scheduling of equal-length jobs on two identical machines Online Nonpreemptive Scheduling of Equal-Length Jobs on Two Identical Machines MICHAEL H. GOLDWASSER AND MARK PEDIGO Saint Louis University Abstract. We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P2 | p j = p, r j | U j . The problem is known to be polynomially solvable in an of ‚ine setting. In an online variant of the problem, a job ™s existence and parameters are revealed to the scheduler only upon that job ™s release date. We present an online deterministic algorithm for the problem and prove that it is 3 -competitive. A simple lower bound shows that this is the optimal deterministic 2 competitiveness. Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation ”Online computation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems ”Sequencing and scheduling General Terms: Algorithms, Theory Additional Key Words and Phrases: Admission control, competitive analysis, scheduling ACM Reference Format: Goldwasser, M. H., and Pedigo, M. 2008. Online nonpreemptive scheduling of equal-length http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Online nonpreemptive scheduling of equal-length jobs on two identical machines

Download PDF
18 pages

Loading next page...
 
/lp/association-for-computing-machinery/online-nonpreemptive-scheduling-of-equal-length-jobs-on-two-identical-17OcXcKAno
Publisher
Association for Computing Machinery
Copyright
Copyright © 2008 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1435375.1435377
Publisher site
See Article on Publisher Site

Abstract

Online Nonpreemptive Scheduling of Equal-Length Jobs on Two Identical Machines MICHAEL H. GOLDWASSER AND MARK PEDIGO Saint Louis University Abstract. We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P2 | p j = p, r j | U j . The problem is known to be polynomially solvable in an of ‚ine setting. In an online variant of the problem, a job ™s existence and parameters are revealed to the scheduler only upon that job ™s release date. We present an online deterministic algorithm for the problem and prove that it is 3 -competitive. A simple lower bound shows that this is the optimal deterministic 2 competitiveness. Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation ”Online computation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems ”Sequencing and scheduling General Terms: Algorithms, Theory Additional Key Words and Phrases: Admission control, competitive analysis, scheduling ACM Reference Format: Goldwasser, M. H., and Pedigo, M. 2008. Online nonpreemptive scheduling of equal-length

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2008

References

  • Ten notes on equal-processing-time scheduling. 4OR
    Baptiste P.
  • On-line scheduling to maximize task completions
    Baruah S. K.