We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.
Minimizing the makespan of tasks with precedence constraints has also been studied in the context of project management. Speed scaling is possible when additional resources can be used to shorten some of the tasks. Pinedo @cite_0 gives heuristics for some variations of this problem.
@cite_0
1570584007
Introduction.- Manufacturing Models.- Service Models.- Project Planning and Scheduling.- Machine Scheduling and Job Shop Scheduling.- Scheduling of Flexible Assembly Systems.- Economic Lot Scheduling.- Planning and Scheduling in Supply Chains.- Interval Scheduling, Reservations, and Timetabling.- Planning and Scheduling in Sports and Entertainment.- Planning, Scheduling, and Timetabling in Transportation.- Workforce Scheduling.- Systems Design and Implementation.- Advanced Concepts in Systems Design.- What Lies Ahead?- Mathematical Programming Formulations.- Exact Optimization Methods.- Heuristic Methods.- Constraint Programing Methods.- Selected Scheduuling Sytems.- The LEKIN Systems User's Guide.- Notation.- References.- Index.