Metaheuristic strategies for scheduling problems with uncertainty

Abstract

Scheduling problems have formed an important body of research during the last decades. A scheduling problem consists in scheduling a set of jobs {J1, . . . , Jn} on a set of physical resources or machines {M1, . . . , Mm}. Each job Ji is composed of m tasks or operations {θi1, . . . , θim} with processing time pij . At the same time, we usually have constraints that establish that two task belonging to the same job cannot overlap their execution in time and that each task requires the uninterrupted and exclusive use of one of the machines for its whole processing time. Depending on the additional constraints we define, we may obtain different families of problems. The most popular in the literature are the job shop (JSP), the open shop (OSP) and the flow shop (FSP) but there exists also variants of them as the flexible job shop (FJSP) among others. Commonly, the objective function to optimise is the earliest time in which all jobs can be finished or makespan. However many other objectives may be optimised, being the most popular the tardiness, the idleness and the total flow time. In classical scheduling problems all input data are assumed to be well defined and all constraints are assumed to be hard, which is not so common in real-life applications. To reduce the gap between theory and practice, this thesis focuses on solving scheduling problems considering that uncertainty and vagueness. For instance, we shall consider uncertain task durations as well as flexible due-date constraints