Job-shop scheduling with flexible energy prices and time windows: A branch-and-price-and-cut approach

Energy-aware scheduling is crucial in the current economy and green production initiatives. However, with the rise of renewable energy sources, power production is subject to uncertain weather conditions. Hence, within a network, some balancing group managers must maintain a balance between production and demand, which requires precise energy orders for specific times. Therefore, those managers must prioritize accurate energy orders to manage this complex problem. The primary aim of this thesis is to manage one customer's energy order for a series of energy-dependent tasks efficiently. It is crucial to recognize that energy costs are subject to fluctuations and that the customer's primary concern is to minimize costs, assuming all orders are completed. To embed the customers' interests into a mathematical model, we consider the job-shop scheduling problem with time windows, precedence constraints and machine states, where the challenge is to organize the energy required to process a set of jobs. We aim to create a feasible processing start for each task while ensuring that the machines consume the least amount of energy. To that end, we use an integer programming formulation that couples the scheduling of tasks with the assignment of the corresponding machine states. The objective function is the price of the consumed energy. It turns out that the considered scheduling problem is NP-hard in general. Nevertheless, we present some relevant cases that are solvable in polynomial time. Scheduling problems are notoriously difficult due to the intertwining of time-based events and job processing start times. To address this, we use a time-indexed formulation using many variables. Additionally, proving the optimality of primal solutions becomes increasingly time-consuming as the problem size grows. To handle a huge number of variables, we use presolving rules specifically designed for the problem and involve combinatorial conditions to reduce the number of variables quickly.