The researchers from Industrial Informatics Department Ondřej Benedikt, István Módos and Zdeněk Hanzálek won Best Student Paper Award for their paper called Power of Pre-Processing: Production Scheduling with Variable Energy Pricing and Power-Saving States at the on-running conference CPAIOR – 17th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research.
The aim of the conference CPAIOR is to bring together interested researchers from Constraint Programming (CP), Artificial Intelligence (AI), and Operations Research (OR) to present new techniques or applications, and to provide an opportunity for researchers in one area to learn about techniques in the others. A main objective of this conference series is also to give these researchers the opportunity to show how the integration of techniques from different fields can lead to interesting results on large and complex problems. Therefore papers that actively combine, integrate, or contrast approaches from more than one of the areas are especially solicited.
The awarded paper addresses a single machine scheduling problem with non-preemptive jobs to minimize the total electricity cost. Two latest trends in the area of the energy-aware scheduling are considered, namely the variable energy pricing and the power-saving states of a machine. Scheduling of the jobs and the machine states are considered jointly to achieve the highest possible savings. Although this problem has been previously addressed in the literature, the reported results of the state-of-the-art method show that the optimal solutions can be found only for instances with up to 35 jobs and 209 intervals within 3 hours of computation. We propose an elegant pre-processing technique called SPACES for computing the optimal switching of the machine states with respect to the energy costs. The optimal switchings are associated with the shortest paths in an interval-state graph that describes all possible transitions between the machine states in time. This idea allows us to implement efficient integer linear programming and constraint programming models of the problem while preserving the optimality. The efficiency of the models lies in the simplification of the optimal switching representation. The results of the experiments show that our approach outperforms the existing state-of-the-art exact method. On a set of benchmark instances with varying sizes and different state transition graphs, the proposed approach finds the optimal solutions even for the large instances with up to 190 jobs and 1277 intervals within an hour of computation.
You can watch the full presentation: