Flow shop for dual CPUs in dynamic voltage scaling (Q1986559)

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.