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-06-01T22:36", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_56.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 N1bde8359fb0a431880c297fd7f48ab7a
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 Ndf81bc4c16d94506b9638993f5fdb720
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N1d5d3c623fd44437a3f4ab6911623cc9
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 N58d2e63a419348d59c47b73ef40f33c6
68 Nd837e1c2b51343c7a023d994f56375d3
69 schema:publisher N7834139442b6433c93a3c3c8beadc621
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012727775
71 https://doi.org/10.1007/11534273_30
72 schema:sdDatePublished 2022-06-01T22:36
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher N56acde033e674e35a74e25238fb872cd
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 N1262d31c8a3341bcb4fc7e4105451dac schema:familyName Sack
80 schema:givenName Jörg-Rüdiger
81 rdf:type schema:Person
82 N1bde8359fb0a431880c297fd7f48ab7a rdf:first sg:person.012717512701.24
83 rdf:rest N44643a5522f64e9cbd7d0a19575f5fb1
84 N1d5d3c623fd44437a3f4ab6911623cc9 schema:isbn 978-3-540-28101-6
85 978-3-540-31711-1
86 schema:name Algorithms and Data Structures
87 rdf:type schema:Book
88 N44643a5522f64e9cbd7d0a19575f5fb1 rdf:first sg:person.016651212565.38
89 rdf:rest N8abec1e12b2641dd94dd43c3a69b54fd
90 N56acde033e674e35a74e25238fb872cd schema:name Springer Nature - SN SciGraph project
91 rdf:type schema:Organization
92 N58d2e63a419348d59c47b73ef40f33c6 schema:name dimensions_id
93 schema:value pub.1012727775
94 rdf:type schema:PropertyValue
95 N7834139442b6433c93a3c3c8beadc621 schema:name Springer Nature
96 rdf:type schema:Organisation
97 N8abec1e12b2641dd94dd43c3a69b54fd rdf:first sg:person.013345515575.46
98 rdf:rest rdf:nil
99 Nb5a08cb68ded4cc092773c29861d85be schema:familyName Dehne
100 schema:givenName Frank
101 rdf:type schema:Person
102 Nce1ecc7f1ed14d62b9d2b9fafcf36a52 rdf:first N1262d31c8a3341bcb4fc7e4105451dac
103 rdf:rest rdf:nil
104 Nd837e1c2b51343c7a023d994f56375d3 schema:name doi
105 schema:value 10.1007/11534273_30
106 rdf:type schema:PropertyValue
107 Ndf81bc4c16d94506b9638993f5fdb720 rdf:first Nb5a08cb68ded4cc092773c29861d85be
108 rdf:rest Nfd73b9909c87456eb43cd0e215f350d0
109 Nfae498661e5c400999a38c392299f72d schema:familyName López-Ortiz
110 schema:givenName Alejandro
111 rdf:type schema:Person
112 Nfd73b9909c87456eb43cd0e215f350d0 rdf:first Nfae498661e5c400999a38c392299f72d
113 rdf:rest Nce1ecc7f1ed14d62b9d2b9fafcf36a52
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)


...