Metaheuristic strategies for scheduling under uncertainty

Resumen

Scheduling problems are a kind of combinatorial problems that pose a great challenge to Artificial Intelligence researchers, being very hard to solve. They are well-known NP-complete problems which have had a great presence in the literature during the last decades. However, in the classical definition of these problems, well-defined information is assumed, which is not the case in most of real-world scenarios, especially when human factors are involved. For instance, the exact processing times of operations may be unknown in advance. The uncertainty that is present in real situations can drastically deteriorate the performance of a solution obtained assuming deterministic conditions. This has led many researchers to consider this uncertainty as part of the problem to solve. Among the different approaches to model the uncertainty, fuzzy sets have emerged as a very interesting tool and have been extensively used in different manners. When uncertainty is modelled by means of fuzzy numbers, we refer to fuzzy scheduling problems. In particular, for this PhD thesis we use the most extended representation in fuzzy scheduling, which is triangular fuzzy numbers or TFNs. Scheduling problems may have also due date constraints, which represent deadlines for each job. These are usually taken to be hard constraints, but in real scenarios, it is more common for them to be flexible. In this thesis we consider the use of flexible due dates together with uncertainty in processing times in three different scheduling problems: fuzzy open shop, fuzzy job shop and fuzzy flexible job shop. Among the different solving methods in the literature, we focus on metaheuristics, which are known to find very good solutions in a short amount of time. For these algorithms to perform well, it is important to define good sets of solutions in which look for the optimal solution. These are well defined for classical scheduling problems, but surprisingly, this is not the case in fuzzy scheduling. Here we provide a first formal definition of schedule categories and schedule generation schemes for fuzzy scheduling problems. This allows us to propose efficient solving methods for these problems. In particular, we consider the most common optimisation criteria, which is the makespan minimisation. Based on the ideas behind the best-known algorithms for the classical scheduling problems, we design new strategies for fuzzy scheduling and provide some insights and hints about the most promising ways of solving these problems. Furthermore, we also propose multi-criteria optimisation methods to minimise the makespan and maximise the agreement index, which is the degree to which the flexible due dates of jobs are fulfilled. We consider both the case in which one objective is given more relevance than the other and the case in which both objectives are equally relevant. An issue of great importance when scheduling under uncertainty is the robustness of solution quality. Indeed, solutions which are robust and reasonably good in quality may be preferred to solutions which in principle are optimal but perform poorly when slight variations in the input data occur. This is a factor that must be taken into account, but which is difficult to translate into a well-defined measure. Using as starting point a definition of semantics for fuzzy scheduling from the literature, we propose a new framework to measure robustness which distinguishes between two kinds of measures: a-priori measures, which are obtained before implementing a solution in a real environment, and a-posteriori measures, that are obtained after implementing the solution. Based on this framework, we propose different robustness measures for fuzzy scheduling. We also propose optimisation algorithms that allow optimising these robustness measures alone or together with a performance measure such as makespan in order to obtain high quality robust solutions.