Decision Diagrams for Industrial Scheduling
Session date: 13 November 2023
Session host: Eghonghon Eigbe
Summary:
A common way to model a manufacturing system is as a flow shop, which is a collection of jobs and machines. Many different variants exist depending on whether machines are multi-purpose, if jobs are processed in a fixed order, etc. Many exact and heuristic scheduling methods for flow shops exist in the literature. Exact solutions often scale poorly, and heuristics typically do not provide any theoretical guarantees. In this work, we bridge these gaps by combining the strength of decision diagrams to generalise easily and provide optimal solutions with the heuristic strength of finding good solutions quickly. Our approach builds on recent work on exploring solution neighbourhoods with decision diagrams. We introduce new state dominance relationships and extend the existing literature to perform neighbourhood search with exact decision diagrams. As the state-of-the-art for many flow shop scheduling problems is still to use heuristics, our approach serves as a way to strategically improve heuristic solutions and also to assess their optimality. We discuss the operation of this approach on a basic flow shop and a more complex industrial use case. We show via empirical evaluation that our approach is competitive with other exact solvers for some problems and scales better for others.
Relevant papers
-
Historical Overview
David Bergman, Andre A. Cire, Willem-Jan Hoeve, and 1 more author
Jan 2016
This chapter provides a brief review of the literature on decision diagrams, primarily as it relates to their use in optimization and constraint programming. It begins with an early history of decision diagrams and their relation to switching circuits. It then surveys some of the key articles that brought decision diagrams into optimization and constraint solving. In particular it describes the development of relaxed and restricted decision diagrams, the use of relaxed decision diagrams for enhanced constraint propagation and optimization bounding, and the elements of a general-purpose solver. It concludes with a brief description of the role of decision diagrams in solving some Markov decision problems in artificial intelligence.
-
Exact Decision Diagrams
David Bergman, Andre A. Cire, Willem-Jan Hoeve, and 1 more author
Jan 2016
In this chapter we introduce a modeling framework based on dynamic programming to compile exact decision diagrams. We describe how dynamic programming models can be used in a top-down compilation method to construct exact decision diagrams. We also present an alternative compilation method based on constraint separation. We illustrate our framework on a number of classical combinatorial optimization problems: maximum independent set, set covering, set packing, single machine scheduling, maximum cut, and maximum 2-satisfiability.