Flow shop for dual CPUs in dynamic voltage scaling

DOI10.1016/J.TCS.2017.09.014MaRDI QIDQ1986559zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 8 April 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2017.09.014

zbMATH Keywords

flow shopschedulingspeed scaling

Mathematics Subject Classification ID

Wireless sensor networks as related to computer science (68M18) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Review text

In this paper a flow shop scheduling problem on two processors is considered. Here the objective is to find a feasible schedule such that all jobs are completed by the common deadline with minimized energy consumption. A new model, called sense-and-aggregate, is proposed, 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. Depending on the model, the aggregation function can be different, and an algorithm whose time complexity depends on the aggregation function is proposed. The performance of the flow shop problem when the order of jobs is fixed is investigated by comparing it to the approximation algorithm with an arbitrary order.

Recommendations

• Flow Shop for Dual CPUs in Dynamic Voltage Scaling
• Power-aware scheduling for makespan and flow
• Energy-efficient algorithms for flow time minimization
• Energy-Efficient Algorithms for Flow Time Minimization
• Speed scaling on parallel processors

Cites work

• Algorithms for dynamic speed scaling
• DVS scheduling in a line or a star network of processors
• Dynamic voltage scaling under EDF revisited
• Flow shop scheduling with peak power consumption constraints
• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• Optimal two- and three-stage production schedules with set-up time included
• Scheduling algorithms

Cited in

(2)

• Flow Shop for Dual CPUs in Dynamic Voltage Scaling
• Minimizing energy on homogeneous processors with shared memory

This page was built for publication: Flow shop for dual CPUs in dynamic voltage scaling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1986559)