Approximation Algorithms for Open Shop Variations Subject to Energy Consumption

We consider the open shop scheduling problem subject to speed scaling and energy consumption. The computational complexity is analyzed and approaches to solving various versions of the problem are proposed. The algorithms use a two-stage scheduling scheme. At the first stage, bounds on the objective function and processing times of jobs are constructed. At the second stage, the speed scaling problem is reduced to the classical problem with fixed job speeds, and list-type methods are applied for scheduling. As a result, NP-hardness is proved in the general case, and polynomial-time exact and approximation algorithms are proposed for the practically important special cases when preemptions are allowed or not, when the set of speeds is discrete or continuous, and when energy consumption is bounded or optimized. A model of mixed-integer convex programming is constructed based on continuous time representation using the notion of event points.