A branch-and-cut algorithm for job-shop scheduling under Time-of-Use pricing and a peak power limit
针对分时电价和峰值功率限制下的作业车间调度问题，提出一种周期索引混合整数线性规划模型，并设计分支切割算法，通过有效不等式和切割平面降低能耗成本。
We address the job-shop scheduling problem under Time-of-Use pricing and a peak power limit, with the objective of minimizing total energy costs. To solve this problem, we propose a period-indexed mixed-integer linear programming formulation that reduces the number of variables compared to traditional time-indexed approaches, at the expense of an exponential number of constraints required to enforce the peak power limit. For this reason, we embed the formulation in a branch-and-cut scheme, where peak-power constraints are added only when violated. In addition, the formulation is strengthened with valid inequalities to improve the root relaxation and enumeration tree exploration. The proposed Branch-and-Cut incorporates clique-forbidding cuts, derived from minimal covers of the knapsack polytope associated with the peak-power constraint. We further extend this approach by deriving cuts from arbitrary valid inequalities of the peak-power polytope, and implement a problem-specific cut selection strategy inspired by established metrics in the literature to add the most effective lazy cuts. The resulting framework addresses the structural challenges of energy-aware job-shop scheduling while advancing exact methods in this domain. • We study the job-shop scheduling problem with ToU pricing and peak power constraints. • We propose a period-indexed Branch-and-Cut with clique-forbidding constraints. • We improve the formulation through several families of valid inequalities. • We extend the clique-forbidding constraints via extremal interval-graph arguments. • We report an extensive computational study across problem sizes and ToU profiles.