Application of exact and approximate optimization methods to novel scheduling problems

The application of exact and heuristic optimization techniques to scheduling problems pertaining to production processes has been widely investigated over the last decades by the relevant scientific literature in the field of industrial systems design and analysis. In general, the term scheduling is used with reference to the allocation of resources to tasks over time, so to execute all planned activities according to a given performance objective (minimization of costs, minimization of production time, due dates fulfilment, etc.). Even though basic scheduling problems have been effectively solved long time ago, this topic still remains attractive for expert and practitioners, as the technological innovation of production processes and the need for effective planning activities emerging from new sectors still set new frontiers to the scheduling optimization research. The aim of the present Thesis is to investigate three scheduling problems that have not been addressed yet by the literature, even though they have a clear correspondence to real-world manufacturing environments. The first problem addressed is the minimization of makespan in an unrelated parallel machine system with sequence-dependent setup times and limited human resources. Workers are needed to perform setup operations before each job is processed; they are supposed to be a critical resource as their number is assumed to be lower than the number of workstations available in the production shop. In addition, each worker is characterized by a provided skill level, which affects the time required for completing setup operations. Firstly, a Mixed Integer Linear Programming (MILP) model suitable for tackling small instances of the problem in hand is illustrated. Then, an optimization framework based on Genetic Algorithms (GAs) is presented with the aim of effectively addressing larger test cases. Three different procedures are proposed, namely a permutation based GA, a multi-encoding GA, and a hybrid GA. An extensive benchmark including both small-and large-sized instances is taken as reference for both calibration and comparison of the proposed methods, which have been performed by means of ANOVA analysis. The second problem addressed is the minimization of makespan in a Flow Shop Sequence Dependent Group Scheduling (FSDGS) problem entailing the worker allocation issue. As first, a Mixed Integer Linear Programming (MILP) formulation for the problem is given. Then, a well-known benchmark arisen from literature is adopted for carrying out an extensive comparison campaign among three specifically developed metaheuristic methods based on a GA framework. Afterwards, the best procedure among those tested is compared with a well-performing algorithm recently proposed in the field of FSDGS problems. The third problem addressed is the minimization of makespan in a hybrid flow shop inspired to a truly observed micro-electronics manufacturing environment, is illustrated. Overlap between jobs, waiting time limit of jobs within inter-stage buffers as well as machine unavailability time intervals represent just a part of the constraints which characterize the problem here investigated. A MILP model of the problem has been developed with the aim to validate the performance concerning the proposed optimization technique, based on a two-phase metaheuristics (MEs). In the first phase the proposed ME algorithm evolves similarly to a genetic algorithm equipped with a regular permutation encoding. Subsequently, a random search algorithm equipped with an m-stage permutation encoding is launched for improving the algorithm strength in terms of both exploration and exploitation. Extensive numerical studies on a benchmark of problems, along with a properly arranged ANOVA analysis, demonstrate the statistical outperformance of the proposed approach with respect to the traditional optimization approach based on a single encoding.