EE
E. Eigbe
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
Optimising Discrete Problems
Decision Diagrams and Context-Aware Heuristics
Optimisation problems are all around us and play a critical role in the outcomes of various sectors of society including scheduling, logistics, network design, and resource allocation. In this thesis, we look at a subset of problems where some or all the choices to be made can only take on values belonging to a discrete set of values – a limitation which increases the difficulty of finding a solution in most cases. We handle this thesis in two parts: first zooming in on a particular class of problems – scheduling – and then on a particular solution method – decision diagrams.
In Part I of this dissertation, we consider the problem of scheduling in manufacturing systems. This popular discrete optimisation problem has been studied extensively; however, advancements in modern manufacturing systems present new challenges and opportunities. A major driver of the changes in manufacturing systems is the integration of the physical processes with computation, networking, and automated control capabilities. Thus, the domain of activities that can directly be decided upon and actuated from software has expanded. We look at one such activity in Chapter 3 namely,
sequence-dependent maintenance and propose solution methods that directly integrate maintenance and production planning.
Part II of this thesis looks into decision diagrams as a solution method for discrete optimisation problems. Decision diagrams have existed since the 1950s and were originally introduced as a means to represent boolean functions. Since then they have been used in different fields such as in circuit verification, knowledge representation, and most recently, operations research. While decision diagrams have already been shown to be very promising methods for solving optimisation problems, we push the field forward as follows. In Chapter 5, we propose a decision diagram model for the kind of scheduling problems tackled in Part I of this thesis. We further perform a comparative study of the consequences of heuristic decisions made during the decision diagram compilation process in Chapter 6 and integrate reinforcement learning with decision-diagram-based branch-and-bound in Chapter 7. In Chapter 8 we go further into considering uncertainty in optimisation problems. We focus on the paradigm of finding the best solution while accepting some level of risk, i.e., chance constrained optimisation and present a chance constrained decision diagram formulation. We further provide theoretical guarantees for instances with normally distributed variables.
The contributions of this thesis cover different aspects of solving discrete optimisation problems with a focus on scheduling and logistic applications. The hope is that these advances further the adoption of state of the art research in solving optimisation problems in real-world contexts. ...
In Part I of this dissertation, we consider the problem of scheduling in manufacturing systems. This popular discrete optimisation problem has been studied extensively; however, advancements in modern manufacturing systems present new challenges and opportunities. A major driver of the changes in manufacturing systems is the integration of the physical processes with computation, networking, and automated control capabilities. Thus, the domain of activities that can directly be decided upon and actuated from software has expanded. We look at one such activity in Chapter 3 namely,
sequence-dependent maintenance and propose solution methods that directly integrate maintenance and production planning.
Part II of this thesis looks into decision diagrams as a solution method for discrete optimisation problems. Decision diagrams have existed since the 1950s and were originally introduced as a means to represent boolean functions. Since then they have been used in different fields such as in circuit verification, knowledge representation, and most recently, operations research. While decision diagrams have already been shown to be very promising methods for solving optimisation problems, we push the field forward as follows. In Chapter 5, we propose a decision diagram model for the kind of scheduling problems tackled in Part I of this thesis. We further perform a comparative study of the consequences of heuristic decisions made during the decision diagram compilation process in Chapter 6 and integrate reinforcement learning with decision-diagram-based branch-and-bound in Chapter 7. In Chapter 8 we go further into considering uncertainty in optimisation problems. We focus on the paradigm of finding the best solution while accepting some level of risk, i.e., chance constrained optimisation and present a chance constrained decision diagram formulation. We further provide theoretical guarantees for instances with normally distributed variables.
The contributions of this thesis cover different aspects of solving discrete optimisation problems with a focus on scheduling and logistic applications. The hope is that these advances further the adoption of state of the art research in solving optimisation problems in real-world contexts. ...
Optimisation problems are all around us and play a critical role in the outcomes of various sectors of society including scheduling, logistics, network design, and resource allocation. In this thesis, we look at a subset of problems where some or all the choices to be made can only take on values belonging to a discrete set of values – a limitation which increases the difficulty of finding a solution in most cases. We handle this thesis in two parts: first zooming in on a particular class of problems – scheduling – and then on a particular solution method – decision diagrams.
In Part I of this dissertation, we consider the problem of scheduling in manufacturing systems. This popular discrete optimisation problem has been studied extensively; however, advancements in modern manufacturing systems present new challenges and opportunities. A major driver of the changes in manufacturing systems is the integration of the physical processes with computation, networking, and automated control capabilities. Thus, the domain of activities that can directly be decided upon and actuated from software has expanded. We look at one such activity in Chapter 3 namely,
sequence-dependent maintenance and propose solution methods that directly integrate maintenance and production planning.
Part II of this thesis looks into decision diagrams as a solution method for discrete optimisation problems. Decision diagrams have existed since the 1950s and were originally introduced as a means to represent boolean functions. Since then they have been used in different fields such as in circuit verification, knowledge representation, and most recently, operations research. While decision diagrams have already been shown to be very promising methods for solving optimisation problems, we push the field forward as follows. In Chapter 5, we propose a decision diagram model for the kind of scheduling problems tackled in Part I of this thesis. We further perform a comparative study of the consequences of heuristic decisions made during the decision diagram compilation process in Chapter 6 and integrate reinforcement learning with decision-diagram-based branch-and-bound in Chapter 7. In Chapter 8 we go further into considering uncertainty in optimisation problems. We focus on the paradigm of finding the best solution while accepting some level of risk, i.e., chance constrained optimisation and present a chance constrained decision diagram formulation. We further provide theoretical guarantees for instances with normally distributed variables.
The contributions of this thesis cover different aspects of solving discrete optimisation problems with a focus on scheduling and logistic applications. The hope is that these advances further the adoption of state of the art research in solving optimisation problems in real-world contexts.
In Part I of this dissertation, we consider the problem of scheduling in manufacturing systems. This popular discrete optimisation problem has been studied extensively; however, advancements in modern manufacturing systems present new challenges and opportunities. A major driver of the changes in manufacturing systems is the integration of the physical processes with computation, networking, and automated control capabilities. Thus, the domain of activities that can directly be decided upon and actuated from software has expanded. We look at one such activity in Chapter 3 namely,
sequence-dependent maintenance and propose solution methods that directly integrate maintenance and production planning.
Part II of this thesis looks into decision diagrams as a solution method for discrete optimisation problems. Decision diagrams have existed since the 1950s and were originally introduced as a means to represent boolean functions. Since then they have been used in different fields such as in circuit verification, knowledge representation, and most recently, operations research. While decision diagrams have already been shown to be very promising methods for solving optimisation problems, we push the field forward as follows. In Chapter 5, we propose a decision diagram model for the kind of scheduling problems tackled in Part I of this thesis. We further perform a comparative study of the consequences of heuristic decisions made during the decision diagram compilation process in Chapter 6 and integrate reinforcement learning with decision-diagram-based branch-and-bound in Chapter 7. In Chapter 8 we go further into considering uncertainty in optimisation problems. We focus on the paradigm of finding the best solution while accepting some level of risk, i.e., chance constrained optimisation and present a chance constrained decision diagram formulation. We further provide theoretical guarantees for instances with normally distributed variables.
The contributions of this thesis cover different aspects of solving discrete optimisation problems with a focus on scheduling and logistic applications. The hope is that these advances further the adoption of state of the art research in solving optimisation problems in real-world contexts.
Industrial and academic interest converge on scheduling flow shops with sequence- and time-dependent maintenance. We posit that anticipatory, integrated scheduling of operational and maintenance tasks leads to superior performance to purely 'wait-then-fix' handling of the maintenance tasks. Motivated by an industrial problem with (sequence dependent) setup times, maximum separation constraints, and a combination of sequence- and time- dependent maintenance tasks, this paper introduces an integer programming solution, a constraint programming solution and a heuristic solution based on list scheduling. The motivating use case provides a unique combination of concerns that is to the best of our knowledge, not yet studied in the literature. We build on existing work where we can by extending models for sequence-dependent maintenance scheduling to accommodate sequence- and time-dependent maintenance scheduling and also propose other new models. We show the relative performances of our methods through empirical evaluations and also show significant improvements - up to 25% reduction in makespan - when compared to a reactive scheduling approach that does not consider maintenance in its planning. Based on our evaluations on exact methods, constraint programming models scale better than mixed integer programming models for this problem.
...
Industrial and academic interest converge on scheduling flow shops with sequence- and time-dependent maintenance. We posit that anticipatory, integrated scheduling of operational and maintenance tasks leads to superior performance to purely 'wait-then-fix' handling of the maintenance tasks. Motivated by an industrial problem with (sequence dependent) setup times, maximum separation constraints, and a combination of sequence- and time- dependent maintenance tasks, this paper introduces an integer programming solution, a constraint programming solution and a heuristic solution based on list scheduling. The motivating use case provides a unique combination of concerns that is to the best of our knowledge, not yet studied in the literature. We build on existing work where we can by extending models for sequence-dependent maintenance scheduling to accommodate sequence- and time-dependent maintenance scheduling and also propose other new models. We show the relative performances of our methods through empirical evaluations and also show significant improvements - up to 25% reduction in makespan - when compared to a reactive scheduling approach that does not consider maintenance in its planning. Based on our evaluations on exact methods, constraint programming models scale better than mixed integer programming models for this problem.