Scheduling under a non-reversible energy source: An application of piecewise linear bounding of non-linear demand/cost functions

In this paper, we address a preemptive scheduling problem involving a non-reversible energy source. To the classical scheduling issue, additional information is added regarding the characteristics of the energy source used to satisfy the total power demand of tasks processed at each instant. Different non-reversible energy sources can have very different characteristics in terms of power range and energy demand/cost function also known as efficiency function. The objective is to identify the best combination between scheduling and energy resource utilization that minimizes the total energy cost of the project. The non-linear efficiency function used to compute energy costs is bounded from above and below by two piecewise-linear curves, yielding two instances of a scheduling problem with a piecewise-linear objective that can be solved separately. For the piecewise-linear scheduling problem, we show that the problem involving multiple non-reversible sources is equivalent to a single-source problem, the particular case of a linear function is polynomially solvable, and the case with a piecewise-linear function with two pieces is NP-hard. A pseudo-polynomial size time-indexed mixed-integer linear formulation of the problem and its Dantzig–Wolfe decomposition yielding an extended formulation are presented. A branch-and-price procedure is proposed to solve the extended formulation. The formulations are compared on a set of scheduling instances, considering artificial and real-world efficiency functions.