Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Jian-Jia Chen , Tei-Wei Kuo , Hsueh-I Lu

ABSTRACT

We study the problem of non-preemptive scheduling to minimize energy consumption for devices that allow dynamic voltage scaling. Specifically, consider a device that can process jobs in a non-preemptive manner. The input consists of (i) the set R of available speeds of the device, (ii) a set J of jobs, and (iii) a precedence constraint Π among J. Each job j in J, defined by its arrival time aj, deadline dj, and amount of computation cj, is supposed to be processed by the device at a speed in R. Under the assumption that a higher speed means higher energy consumption, the power-saving scheduling problem is to compute a feasible schedule with speed assignment for the jobs in J such that the required energy consumption is minimized.This paper focuses on the setting of weakly dynamic voltage scaling, i.e., speed change is not allowed in the middle of processing a job. To demonstrate that this restriction on many portable power-aware devices introduces hardness to the power-saving scheduling problem, we prove that the problem is NP-hard even if aj = aj ′ and dj = dj ′ hold for all j,j ′∈ Jand |R|=2. If |R|<∞, we also give fully polynomial-time approximation schemes for two cases of the general NP-hard problem: (a) all jobs share a common arrival time, and (b) Π = ∅ and for any j,j ′ ∈ J, aj ≤ aj ′ implies dj ≤ dj ′. To the best of our knowledge, there is no previously known approximation algorithm for any special case of the NP-hard problem. More... »

PAGES

338-349

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11534273_30

DOI

http://dx.doi.org/10.1007/11534273_30

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1012727775


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0906", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Electrical and Electronic Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Jian-Jia", 
        "id": "sg:person.012717512701.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012717512701.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, Graduate Institute of Networking and Multimedia, National Taiwan University, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, Graduate Institute of Networking and Multimedia, National Taiwan University, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kuo", 
        "givenName": "Tei-Wei", 
        "id": "sg:person.016651212565.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016651212565.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, Graduate Institute of Networking and Multimedia, National Taiwan University, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, Graduate Institute of Networking and Multimedia, National Taiwan University, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We study the problem of non-preemptive scheduling to minimize energy consumption for devices that allow dynamic voltage scaling. Specifically, consider a device that can process jobs in a non-preemptive manner. The input consists of (i) the set R of available speeds of the device, (ii) a set J of jobs, and (iii) a precedence constraint \u03a0 among J. Each job j in J, defined by its arrival time aj, deadline dj, and amount of computation cj, is supposed to be processed by the device at a speed in R. Under the assumption that a higher speed means higher energy consumption, the power-saving scheduling problem is to compute a feasible schedule with speed assignment for the jobs in J such that the required energy consumption is minimized.This paper focuses on the setting of weakly dynamic voltage scaling, i.e., speed change is not allowed in the middle of processing a job. To demonstrate that this restriction on many portable power-aware devices introduces hardness to the power-saving scheduling problem, we prove that the problem is NP-hard even if aj = aj \u2032 and dj = dj \u2032 hold for all j,j \u2032\u2208 Jand |R|=2. If |R|<\u221e, we also give fully polynomial-time approximation schemes for two cases of the general NP-hard problem: (a) all jobs share a common arrival time, and (b) \u03a0 = \u2205 and for any j,j \u2032 \u2208 J, aj \u2264 aj \u2032 implies dj \u2264 dj \u2032. To the best of our knowledge, there is no previously known approximation algorithm for any special case of the NP-hard problem.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "L\u00f3pez-Ortiz", 
        "givenName": "Alejandro", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11534273_30", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28101-6", 
        "978-3-540-31711-1"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "dynamic voltage scaling", 
      "energy consumption", 
      "voltage scaling", 
      "high energy consumption", 
      "speed assignment", 
      "high speed", 
      "speed changes", 
      "available speeds", 
      "devices", 
      "speed", 
      "scheduling problem", 
      "scaling device", 
      "amount of computation", 
      "hardness", 
      "arrival time", 
      "consumption", 
      "scheduling", 
      "scaling", 
      "non-preemptive manner", 
      "common arrival time", 
      "feasible schedule", 
      "non-preemptive scheduling", 
      "problem", 
      "scheme", 
      "input", 
      "computation", 
      "algorithm", 
      "special case", 
      "general NP-hard problem", 
      "NP-hard problem", 
      "amount", 
      "time", 
      "assumption", 
      "hold", 
      "cases", 
      "polynomial time approximation scheme", 
      "NPs", 
      "middle", 
      "schedule", 
      "approximation algorithm", 
      "deadlines", 
      "approximation scheme", 
      "changes", 
      "job j", 
      "manner", 
      "jobs", 
      "restriction", 
      "AJ", 
      "knowledge", 
      "assignment", 
      "setting", 
      "jand", 
      "paper"
    ], 
    "name": "Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices", 
    "pagination": "338-349", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1012727775"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11534273_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11534273_30", 
      "https://app.dimensions.ai/details/publication/pub.1012727775"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_390.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11534273_30"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11534273_30'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11534273_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11534273_30'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11534273_30'


 

This table displays all metadata directly associated to this object as RDF triples.

139 TRIPLES      23 PREDICATES      79 URIs      72 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11534273_30 schema:about anzsrc-for:09
2 anzsrc-for:0906
3 schema:author Nc46846e35e514129bc027b24ddf56700
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description We study the problem of non-preemptive scheduling to minimize energy consumption for devices that allow dynamic voltage scaling. Specifically, consider a device that can process jobs in a non-preemptive manner. The input consists of (i) the set R of available speeds of the device, (ii) a set J of jobs, and (iii) a precedence constraint Π among J. Each job j in J, defined by its arrival time aj, deadline dj, and amount of computation cj, is supposed to be processed by the device at a speed in R. Under the assumption that a higher speed means higher energy consumption, the power-saving scheduling problem is to compute a feasible schedule with speed assignment for the jobs in J such that the required energy consumption is minimized.This paper focuses on the setting of weakly dynamic voltage scaling, i.e., speed change is not allowed in the middle of processing a job. To demonstrate that this restriction on many portable power-aware devices introduces hardness to the power-saving scheduling problem, we prove that the problem is NP-hard even if aj = aj ′ and dj = dj ′ hold for all j,j ′∈ Jand |R|=2. If |R|<∞, we also give fully polynomial-time approximation schemes for two cases of the general NP-hard problem: (a) all jobs share a common arrival time, and (b) Π = ∅ and for any j,j ′ ∈ J, aj ≤ aj ′ implies dj ≤ dj ′. To the best of our knowledge, there is no previously known approximation algorithm for any special case of the NP-hard problem.
7 schema:editor Nfff345db2a0b4a238e62c6f02faaf031
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N02193cd8b47c44e6a67dc204c10def9d
12 schema:keywords AJ
13 NP-hard problem
14 NPs
15 algorithm
16 amount
17 amount of computation
18 approximation algorithm
19 approximation scheme
20 arrival time
21 assignment
22 assumption
23 available speeds
24 cases
25 changes
26 common arrival time
27 computation
28 consumption
29 deadlines
30 devices
31 dynamic voltage scaling
32 energy consumption
33 feasible schedule
34 general NP-hard problem
35 hardness
36 high energy consumption
37 high speed
38 hold
39 input
40 jand
41 job j
42 jobs
43 knowledge
44 manner
45 middle
46 non-preemptive manner
47 non-preemptive scheduling
48 paper
49 polynomial time approximation scheme
50 problem
51 restriction
52 scaling
53 scaling device
54 schedule
55 scheduling
56 scheduling problem
57 scheme
58 setting
59 special case
60 speed
61 speed assignment
62 speed changes
63 time
64 voltage scaling
65 schema:name Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices
66 schema:pagination 338-349
67 schema:productId Nbf773ab2199f4dfaa3535a083afd9684
68 Nd08ab3ace9684d939ef8725e14232391
69 schema:publisher Nb86d5e2ab9714b85b9a96d07732f0101
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012727775
71 https://doi.org/10.1007/11534273_30
72 schema:sdDatePublished 2022-05-20T07:47
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher Ncf19e1f35869426389db090730f5c2e4
75 schema:url https://doi.org/10.1007/11534273_30
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N02193cd8b47c44e6a67dc204c10def9d schema:isbn 978-3-540-28101-6
80 978-3-540-31711-1
81 schema:name Algorithms and Data Structures
82 rdf:type schema:Book
83 N02ad8e4f661045eabd4c945e59232e6f rdf:first sg:person.013345515575.46
84 rdf:rest rdf:nil
85 N09e9cf706ecd497aa50f2d93ce528342 schema:familyName Dehne
86 schema:givenName Frank
87 rdf:type schema:Person
88 N259ece8772c648ee85d6960beec123d5 rdf:first sg:person.016651212565.38
89 rdf:rest N02ad8e4f661045eabd4c945e59232e6f
90 N63c07ac510e14adda8f028e1de46f0d2 schema:familyName López-Ortiz
91 schema:givenName Alejandro
92 rdf:type schema:Person
93 Nb86d5e2ab9714b85b9a96d07732f0101 schema:name Springer Nature
94 rdf:type schema:Organisation
95 Nbf773ab2199f4dfaa3535a083afd9684 schema:name dimensions_id
96 schema:value pub.1012727775
97 rdf:type schema:PropertyValue
98 Nc46846e35e514129bc027b24ddf56700 rdf:first sg:person.012717512701.24
99 rdf:rest N259ece8772c648ee85d6960beec123d5
100 Ncb9530557ffd42c9899ebc95fccfe3ab rdf:first Ncfd9d131a35041218dbcab344f977188
101 rdf:rest rdf:nil
102 Ncf19e1f35869426389db090730f5c2e4 schema:name Springer Nature - SN SciGraph project
103 rdf:type schema:Organization
104 Ncfd9d131a35041218dbcab344f977188 schema:familyName Sack
105 schema:givenName Jörg-Rüdiger
106 rdf:type schema:Person
107 Nd08ab3ace9684d939ef8725e14232391 schema:name doi
108 schema:value 10.1007/11534273_30
109 rdf:type schema:PropertyValue
110 Nfc9d78cf457745fbbf2d9db23bb47239 rdf:first N63c07ac510e14adda8f028e1de46f0d2
111 rdf:rest Ncb9530557ffd42c9899ebc95fccfe3ab
112 Nfff345db2a0b4a238e62c6f02faaf031 rdf:first N09e9cf706ecd497aa50f2d93ce528342
113 rdf:rest Nfc9d78cf457745fbbf2d9db23bb47239
114 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
115 schema:name Engineering
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0906 schema:inDefinedTermSet anzsrc-for:
118 schema:name Electrical and Electronic Engineering
119 rdf:type schema:DefinedTerm
120 sg:person.012717512701.24 schema:affiliation grid-institutes:grid.19188.39
121 schema:familyName Chen
122 schema:givenName Jian-Jia
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012717512701.24
124 rdf:type schema:Person
125 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
126 schema:familyName Lu
127 schema:givenName Hsueh-I
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
129 rdf:type schema:Person
130 sg:person.016651212565.38 schema:affiliation grid-institutes:grid.19188.39
131 schema:familyName Kuo
132 schema:givenName Tei-Wei
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016651212565.38
134 rdf:type schema:Person
135 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, Graduate Institute of Networking and Multimedia, National Taiwan University, Taiwan, Republic of China
136 Department of Computer Science and Information Engineering, National Taiwan University, Taiwan, Republic of China
137 schema:name Department of Computer Science and Information Engineering, Graduate Institute of Networking and Multimedia, National Taiwan University, Taiwan, Republic of China
138 Department of Computer Science and Information Engineering, National Taiwan University, Taiwan, Republic of China
139 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...