File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Non-clairvoyant weighted flow time scheduling on different multi-processor models

TitleNon-clairvoyant weighted flow time scheduling on different multi-processor models
Authors
KeywordsCompetitive algorithms
Flow-time
Job size
Job-shop scheduling
Multi-processors
Issue Date2011
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 9th Workshop on Approximation and Online Algorithms (WAOA 2011), Saarbrücken, Germany, 8-9 September 2011. In Lecture Notes in Computer Science, 2011, v. 7164, p. 137-149 How to Cite?
AbstractWe study non-clairvoyant scheduling to minimize weighted flow time on two different multi-processor models. In the first model, processors are all identical and jobs can possibly be speeded up by running on several processors in parallel. Under the non-clairvoyant model, the online scheduler has no information about the actual job size and degree of speed-up due to parallelism during the execution of a job, yet it has to determine dynamically when and how many processors to run the jobs. The literature contains several O(1)-competitive algorithms for this problem under the unit-weight multi-processor setting [9,10] as well as the weighted single-processor setting [2]. This paper shows the first O(1)-competitive algorithm for weighted flow time in the multi-processor setting. In the second model, we consider processors with different functionalities and only processors of the same functionality can work on the same job in parallel to achieve some degree of speed up. Here a job is modeled as a sequence of non-clairvoyant demands of different functionalities. This model is derived naturally from the classical job shop scheduling; but as far as we know, there is no previous work on scheduling to minimize flow time under this multi-processor model. In this paper we take a first step to study non-clairvoyant scheduling on this multi-processor model. Motivated by the literature on 2-machine job shop scheduling, we focus on the special case when processors are divided into two types of functionalities, and we show a non-clairvoyant algorithm that is O(1)-competitive for weighted flow time. © 2012 Springer-Verlag.
DescriptionLNCS v. 7164 is proceedings of the 9th International Workshop, WAOA 2011
Persistent Identifierhttp://hdl.handle.net/10722/139995
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorZhu, Jen_US
dc.contributor.authorChan, HLen_US
dc.contributor.authorLam, TWen_US
dc.date.accessioned2011-09-23T06:04:30Z-
dc.date.available2011-09-23T06:04:30Z-
dc.date.issued2011en_US
dc.identifier.citationThe 9th Workshop on Approximation and Online Algorithms (WAOA 2011), Saarbrücken, Germany, 8-9 September 2011. In Lecture Notes in Computer Science, 2011, v. 7164, p. 137-149en_US
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/139995-
dc.descriptionLNCS v. 7164 is proceedings of the 9th International Workshop, WAOA 2011-
dc.description.abstractWe study non-clairvoyant scheduling to minimize weighted flow time on two different multi-processor models. In the first model, processors are all identical and jobs can possibly be speeded up by running on several processors in parallel. Under the non-clairvoyant model, the online scheduler has no information about the actual job size and degree of speed-up due to parallelism during the execution of a job, yet it has to determine dynamically when and how many processors to run the jobs. The literature contains several O(1)-competitive algorithms for this problem under the unit-weight multi-processor setting [9,10] as well as the weighted single-processor setting [2]. This paper shows the first O(1)-competitive algorithm for weighted flow time in the multi-processor setting. In the second model, we consider processors with different functionalities and only processors of the same functionality can work on the same job in parallel to achieve some degree of speed up. Here a job is modeled as a sequence of non-clairvoyant demands of different functionalities. This model is derived naturally from the classical job shop scheduling; but as far as we know, there is no previous work on scheduling to minimize flow time under this multi-processor model. In this paper we take a first step to study non-clairvoyant scheduling on this multi-processor model. Motivated by the literature on 2-machine job shop scheduling, we focus on the special case when processors are divided into two types of functionalities, and we show a non-clairvoyant algorithm that is O(1)-competitive for weighted flow time. © 2012 Springer-Verlag.-
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectCompetitive algorithms-
dc.subjectFlow-time-
dc.subjectJob size-
dc.subjectJob-shop scheduling-
dc.subjectMulti-processors-
dc.titleNon-clairvoyant weighted flow time scheduling on different multi-processor modelsen_US
dc.typeConference_Paperen_US
dc.identifier.emailZhu, J: jqzhu@cs.hku.hken_US
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_US
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.authorityChan, HL=rp01310en_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-29116-6_12-
dc.identifier.scopuseid_2-s2.0-84859355207-
dc.identifier.hkuros194066en_US
dc.identifier.volume7164-
dc.identifier.spage137-
dc.identifier.epage149-
dc.publisher.placeGermany-
dc.description.otherThe 9th Workshop on Approximation and Online Algorithms (WAOA 2011), Saarbrücken, Germany, 8-9 September 2011. In Lecture Notes in Computer Science, 2011, v. 7164, p. 137-149-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats