File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Scheduling with gaps: new models and algorithms

TitleScheduling with gaps: new models and algorithms
Authors
Issue Date2015
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 9th International Conference (CIAC 2015), Paris, France, 20-22 May 2015. In Lecture Notes in Computer Science, 2015, v. 9079, p. 114-126 How to Cite?
AbstractWe initiate the study of scheduling problems where the number or size of the gaps in the schedule is taken into consideration. We focus on the model with unit jobs. First we examine scheduling problems with release times and deadlines, where we consider variants of minimum-gap scheduling, including maximizing throughput with a budget for gaps or minimizing the number of gaps with a throughput requirement. We then turn to other objective functions. For example, in some scenarios, gaps in a schedule may be actually desirable, leading to the problem of maximizing the number of gaps. The second part of the paper examines the model without deadlines, where we focus on the tradeoff between the number of gaps and flow time. For all these problems we provide polynomial algorithms. The solutions involve a spectrum of algorithmic techniques, including different dynamic programming formulations, speed-up techniques based on searching Monge arrays, searching X+Y matrices, or implicit binary search. Throughout the paper, we also draw a connection between our scheduling problems and their continuous analogues, namely hitting set problems for intervals of real numbers.
DescriptionLNCS v. 9079 entitled: Algorithms and Complexity: 9th International Conference, CIAC 2015 ... Proceedings
Persistent Identifierhttp://hdl.handle.net/10722/214760
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorChrobak, M-
dc.contributor.authorGolin, M-
dc.contributor.authorLam, TW-
dc.contributor.authorNogneng, D-
dc.date.accessioned2015-08-21T11:54:26Z-
dc.date.available2015-08-21T11:54:26Z-
dc.date.issued2015-
dc.identifier.citationThe 9th International Conference (CIAC 2015), Paris, France, 20-22 May 2015. In Lecture Notes in Computer Science, 2015, v. 9079, p. 114-126-
dc.identifier.isbn978-3-319-18172-1-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/214760-
dc.descriptionLNCS v. 9079 entitled: Algorithms and Complexity: 9th International Conference, CIAC 2015 ... Proceedings-
dc.description.abstractWe initiate the study of scheduling problems where the number or size of the gaps in the schedule is taken into consideration. We focus on the model with unit jobs. First we examine scheduling problems with release times and deadlines, where we consider variants of minimum-gap scheduling, including maximizing throughput with a budget for gaps or minimizing the number of gaps with a throughput requirement. We then turn to other objective functions. For example, in some scenarios, gaps in a schedule may be actually desirable, leading to the problem of maximizing the number of gaps. The second part of the paper examines the model without deadlines, where we focus on the tradeoff between the number of gaps and flow time. For all these problems we provide polynomial algorithms. The solutions involve a spectrum of algorithmic techniques, including different dynamic programming formulations, speed-up techniques based on searching Monge arrays, searching X+Y matrices, or implicit binary search. Throughout the paper, we also draw a connection between our scheduling problems and their continuous analogues, namely hitting set problems for intervals of real numbers.-
dc.languageeng-
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Science-
dc.rightsThe final publication is available at Springer via http://dx.doi.org/[insert DOI]-
dc.titleScheduling with gaps: new models and algorithms-
dc.typeConference_Paper-
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.authorityLam, TW=rp00135-
dc.identifier.doi10.1007/978-3-319-18173-8_8-
dc.identifier.hkuros249629-
dc.identifier.volume9079-
dc.identifier.spage114-
dc.identifier.epage126-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 150929-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats