PORTO @ 
Archivio Istituzionale della Ricerca
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishCombinatorial Optimization Problems (COPs) are widespread in computer science and operations management areas. COPs are defined based on an objective function and logical constraints. A feasible solution of COPs, satisfying all the constraints, is composed of discrete decisions. Every decision may affect the total value of the objective function and the feasibility of the solution. The optimal solution is the best feasible one, distinguished based on the objective function value of candidates in a finite (and huge) discrete set. Depending on the problem, any COP can be represented as a minimization or maximization problem. Of course, an exhaustive search to solve COPs, which consists of enumerating all possible solutions and choose the best one, is far to be suitable. In realistic situations, this approach becomes intractable due to the combinatorial nature of such problems. Several exact methods have been developed to provide an optimal solution to COPs, and, in some cases, efficient exact algorithms can optimize the problem in polynomial time. When efficient algorithms are not available for more complex situations, the problem can be mathematically formulated and then solved by a solver (e.g., Cplex, GAMS, Gurobi, AMPL, OPL, etc.). However, solving most COPs by the solvers is computationally demanding as the CPU time may grow exponentially. Due to the inner complexity of most COPs (e.g., an NP-Hard problem) and being computationally challenging to provide a solution, other approaches like heuristic, metaheuristic, and approximation approaches can be advisable to apply instead of exact methods. Many COPs are concerned with scheduling decisions on various activities and resources, such as machines, airplanes, and people, to meet desired objectives. Dealing with COPs implies different levels of decisions such as strategic (long-term), tactical (mid-term), operational (short-term). The usual assumption in COPs is that all the problem elements are precisely known, which provides a deterministic setting. Within this framework, it is assumed that the perfect information about the problem inputs is known and available in advance. In practice, the COPs may be expressed under uncertainty or dynamicity since the data may be partially known or changed dynamically over the entire decision horizon. Because of incomplete information or the dynamics of the environment, the outcome of any specific plan is uncertain. It is easy to understand that, in those cases, ignoring the parameter variability and uncertainty may lead to inferior or, even worse, non-feasible decisions. It is well-known that explicitly addressing uncertainty in optimization problems generally increases the decision-making process’s complexity and poses significant computational challenges. Therefore, it always makes sense to see whether it is possible to incorporate stochasticity in an approximated way, converting the stochastic model into a deterministic one and, if so, how accurate this approximation is. Stochastic Programming is one of the main existing paradigms in dealing with uncertain data assuming that the random input data follow probability distributions and pursues optimality in the average sense, adopting a risk-neutral perspective. However, it is not easy to measure the probabilistic distribution of input data in practice. Even if an estimate of such a distribution is available, many scenarios are necessarily needed to approximate it accurately. Unfortunately, as the number of scenarios increases, the problem becomes more complex since the number of decision variables and constraints grows. In this spirit, three main parts corresponding to deterministic, stochastic and dynamic COPs are proposed in this thesis. In the first part, we aim to address deterministic COPs motivated by two applications from Vehicle Routing Problems (VRPs). The objective of this part is twofold. The first one is describing multi-trip single-vehicle routing problem with AND-type precedence constraints, modeling and solving that using logic based benders decomposition algorithm. Our second objective is describing vehicle routing problem with AND/OR precedence constraints and time windows, mathematically formulating the problem and solving that through a developed hybrid algorithm. The second part of the thesis is associated to the stochastic COPs focusing on solving multi-stage decision making problems under uncertainty. Two research problems are proposed and addressed using the asymptotic deterministic approximation approach. The first problem seeks an optimal path on a multi-stage stochastic decision network, while the second research deals with stochastic single machine scheduling problem considering learning effect on processing times, sequence-dependent setup times, and machine configuration selection, simultaneously. In the third part, online single machine scheduling problem as an application in dynamic COPs is proposed and addressed using reinforcement learning approaches.
Combinatorial Optimization Problems under Deterministic, Stochastic, and Dynamic Scheduling Decisions / Roohnavazfar, Mina. - (2021).
| Titolo: | Combinatorial Optimization Problems under Deterministic, Stochastic, and Dynamic Scheduling Decisions | |
| Autori: | ||
| Data di pubblicazione: | 2021 | |
| Abstract: | Combinatorial Optimization Problems (COPs) are widespread in computer science and operations management areas. COPs are defined based on an objective function and logical constraints. A feasible solution of COPs, satisfying all the constraints, is composed of discrete decisions. Every decision may affect the total value of the objective function and the feasibility of the solution. The optimal solution is the best feasible one, distinguished based on the objective function value of candidates in a finite (and huge) discrete set. Depending on the problem, any COP can be represented as a minimization or maximization problem. Of course, an exhaustive search to solve COPs, which consists of enumerating all possible solutions and choose the best one, is far to be suitable. In realistic situations, this approach becomes intractable due to the combinatorial nature of such problems. Several exact methods have been developed to provide an optimal solution to COPs, and, in some cases, efficient exact algorithms can optimize the problem in polynomial time. When efficient algorithms are not available for more complex situations, the problem can be mathematically formulated and then solved by a solver (e.g., Cplex, GAMS, Gurobi, AMPL, OPL, etc.). However, solving most COPs by the solvers is computationally demanding as the CPU time may grow exponentially. Due to the inner complexity of most COPs (e.g., an NP-Hard problem) and being computationally challenging to provide a solution, other approaches like heuristic, metaheuristic, and approximation approaches can be advisable to apply instead of exact methods. Many COPs are concerned with scheduling decisions on various activities and resources, such as machines, airplanes, and people, to meet desired objectives. Dealing with COPs implies different levels of decisions such as strategic (long-term), tactical (mid-term), operational (short-term). The usual assumption in COPs is that all the problem elements are precisely known, which provides a deterministic setting. Within this framework, it is assumed that the perfect information about the problem inputs is known and available in advance. In practice, the COPs may be expressed under uncertainty or dynamicity since the data may be partially known or changed dynamically over the entire decision horizon. Because of incomplete information or the dynamics of the environment, the outcome of any specific plan is uncertain. It is easy to understand that, in those cases, ignoring the parameter variability and uncertainty may lead to inferior or, even worse, non-feasible decisions. It is well-known that explicitly addressing uncertainty in optimization problems generally increases the decision-making process’s complexity and poses significant computational challenges. Therefore, it always makes sense to see whether it is possible to incorporate stochasticity in an approximated way, converting the stochastic model into a deterministic one and, if so, how accurate this approximation is. Stochastic Programming is one of the main existing paradigms in dealing with uncertain data assuming that the random input data follow probability distributions and pursues optimality in the average sense, adopting a risk-neutral perspective. However, it is not easy to measure the probabilistic distribution of input data in practice. Even if an estimate of such a distribution is available, many scenarios are necessarily needed to approximate it accurately. Unfortunately, as the number of scenarios increases, the problem becomes more complex since the number of decision variables and constraints grows. In this spirit, three main parts corresponding to deterministic, stochastic and dynamic COPs are proposed in this thesis. In the first part, we aim to address deterministic COPs motivated by two applications from Vehicle Routing Problems (VRPs). The objective of this part is twofold. The first one is describing multi-trip single-vehicle routing problem with AND-type precedence constraints, modeling and solving that using logic based benders decomposition algorithm. Our second objective is describing vehicle routing problem with AND/OR precedence constraints and time windows, mathematically formulating the problem and solving that through a developed hybrid algorithm. The second part of the thesis is associated to the stochastic COPs focusing on solving multi-stage decision making problems under uncertainty. Two research problems are proposed and addressed using the asymptotic deterministic approximation approach. The first problem seeks an optimal path on a multi-stage stochastic decision network, while the second research deals with stochastic single machine scheduling problem considering learning effect on processing times, sequence-dependent setup times, and machine configuration selection, simultaneously. In the third part, online single machine scheduling problem as an application in dynamic COPs is proposed and addressed using reinforcement learning approaches. | |
| Appare nelle tipologie: | 8.2 Doctoral thesis di enti esterni |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| main.pdf | Main Thesis | Tesi di dottorato |  | Visibile a tuttiVisualizza/Apri |
| Roohnavazfar-abstract.pdf | Abstract | | Visibile a tuttiVisualizza/Apri |
http://hdl.handle.net/11583/2924342
Copyright © 2021