Flow shop for dual CPUs in dynamic voltage scaling

	Flow shop for dual CPUs in dynamic voltage scaling
	Vincent Chau; Xin Chen; Ken C.K. Fong; Minming Li; Kai Wang
刊名	Theoretical Computer Science
	2017
文献子类	期刊论文
英文摘要	" 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 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 and the job execution order is fixed. We also provide a -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 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 dynamic programming algorithm when and a greedy algorithm when . Finally, we investigate the performance of the flowshop problem when the order of jobs is fixed by comparing it to the approximation algorithm with an arbitrary order. We show experimentally that the approximation ratio is close to 1 when there are few machines and when there are more jobs."
URL标识	查看原文
语种	英语
内容类型	期刊论文
源URL	[http://ir.siat.ac.cn:8080/handle/172644/12489]
专题	深圳先进技术研究院_数字所
作者单位	Theoretical Computer Science
推荐引用方式 GB/T 7714	Vincent Chau,Xin Chen,Ken C.K. Fong,et al. Flow shop for dual CPUs in dynamic voltage scaling[J]. Theoretical Computer Science,2017.
APA	Vincent Chau,Xin Chen,Ken C.K. Fong,Minming Li,&Kai Wang.(2017).Flow shop for dual CPUs in dynamic voltage scaling.Theoretical Computer Science.
MLA	Vincent Chau,et al."Flow shop for dual CPUs in dynamic voltage scaling".Theoretical Computer Science (2017).