Optimal batch schedules for parallel machines

Frederic Koehler, Samir Khuller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

We consider the problem of batch scheduling on parallel machines where jobs have release times, deadlines, and identical processing times. The goal is to schedule these jobs in batches of size at most B on m identical machines. Previous work on this problem primarily focused on finding feasible schedules. Motivated by the problem of minimizing energy, we consider problems where the number of batches is significant. Minimizing the number of batches on a single processor previously required an impractical O(n8) dynamic programming algorithm. We present a O(n3) algorithm for simultaneously minimizing the number of batches and maximum completion time, and give improved guarantees for variants with infinite size batches, agreeable release times, and batch "budgets". Finally, we give a pseudo-polynomial algorithm for general batch-count-sensitive objective functions and correct errors in previous results.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Pages475-486
Number of pages12
DOIs
StatePublished - Aug 12 2013
Event13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada
Duration: Aug 12 2013Aug 14 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8037 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Symposium on Algorithms and Data Structures, WADS 2013
CountryCanada
CityLondon, ON
Period8/12/138/14/13

Keywords

  • Batching
  • Optimal Algorithms
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal batch schedules for parallel machines'. Together they form a unique fingerprint.

Cite this