We consider a job shop scheduling problem with time windows, flexible energy prices, and machines whose energy consumption depends on their operational state (offline, ramp-up, setup, processing, standby or ramp-down). The goal is to find a valid schedule that minimizes the overall energy cost. To solve this problem to optimality, we developed a branch-and-bound algorithm based on a time-indexed integer linear programming (ILP) formulation, which uses binary variables that describe blocks spanning multiple inactive periods on the machines. In this paper, we discuss the propagation and branching schemes used in that algorithm. The strategies, which are specifically tailored for energy related machine scheduling problems, primarily aim to determine and sharpen the activity profiles of the machines (and thus reduce the number of the inactive block variables) and address the workload profile of the tasks with lower priority.
@inproceedings{doi:10.17170/kobra-202311108997,
author ={Bley, Andreas and Linß, Andreas},
keywords ={510 and Ganzzahlige Optimierung and Branch-and-Bound-Methode and Reihenfolgeproblem and Energieverbrauch},
title ={Propagation and branching strategies for job shop scheduling minimizing the weighted energy consumption},
copyright ={https://rightsstatements.org/page/InC/1.0/},
language ={en},
year ={2023}
}