Flow shop for dual CPUs in dynamic voltage scaling

Vincent CHAU, Ken C.K. FONG, Minming LI*, Kai WANG

*Corresponding author for this work

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

Abstract

We study the following flow shop scheduling problem on two processors. We are given n jobs with a common deadline D, where each job j has workload pi,j on processor i and a set of processors which can vary their speed dynamically. Job j can be executed on the second processor if the execution of job j is completed on the first processor. Our objective is to find a feasible schedule such that all jobs are completed by the common deadline D with minimized energy consumption. For this model, we present a linear program for the discrete speed case, where the processor can only run at specific speeds in S = {s1, s2, · · ·, sq} and the job execution order is fixed. We also provide a mα−1-approximation algorithm for the arbitrary order case and for continuous speed model where m is the number of processors and α is a parameter of the processor. 

We then introduce a new variant of flow shop scheduling problem called sense-and-aggregate model motivated by data aggregation in wireless sensor networks where the base station needs to receive data from sensors and then compute a single aggregate result. In this model, the first processor will receive unit size data from sensors and the second processor is responsible for calculating the aggregate result. The second processor can decide when to aggregate and the workload that needs to be done to aggregate x data will be f(x) and another unit size data will be generated as the result of the partial aggregation which will then be used in the next round aggregation. Our objective is to find a schedule such that all data are received and aggregated by the deadline with minimum energy consumption. We present an O(n5) dynamic programming algorithm when f(x) = x and a greedy algorithm when f(x) = x − 1.

Original languageEnglish
Title of host publicationComputing and Combinatorics: 22nd International Conference, COCOON 2016, Proceedings
EditorsThang N. DINH, My T. THAI
Place of PublicationSwitzerland
PublisherSpringer, Cham
Pages520-531
Number of pages12
Edition1
ISBN (Electronic)9783319426341
ISBN (Print)9783319426334
DOIs
Publication statusPublished - 20 Jul 2016
Externally publishedYes
Event22nd International Conference on Computing and Combinatorics, COCOON 2016 - Ho Chi Minh City, Viet Nam
Duration: 2 Aug 20164 Aug 2016

Publication series

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

Conference

Conference22nd International Conference on Computing and Combinatorics, COCOON 2016
Country/TerritoryViet Nam
CityHo Chi Minh City
Period2/08/164/08/16

Funding

This work was fully supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 117913].

Fingerprint

Dive into the research topics of 'Flow shop for dual CPUs in dynamic voltage scaling'. Together they form a unique fingerprint.

Cite this