Decision diagrams for solving single- and multi-machine scheduling with release times, deadlines and possibly rejection

Scheduling problems appear in many interesting domains, including for example manufacturing and satellite scheduling. State-of-the-art solvers can still not solve all realistically-sized problem instances within reasonable time, leaving an open challenge for further research. Decision diagrams represent the state space by a directed a-cyclic graph, and can be seen as a generalization of dynamic programming. This representation can help to find lower bounds for multi-machine (parallel and uniform) scheduling problems, but also for finding exact solutions for single-machine scheduling with release times, deadlines and rejection. For a significant set of instance classes, these relatively simple algorithms outperform state of the art MILP formulations run with CPLEX.