Hybrid (meta-)heuristic optimization for single machine, parallel machine and job shop scheduling problems

In this doctoral thesis, we study a widely investigated branch of the operational research domain, i.e. the scheduling of production systems. Scheduling, in general, can be seen as the allocation of limited resources to tasks in order to optimize a certain objective function. Machine scheduling, in particular, refers to problems in a manufacturing environment where jobs have to be scheduled for processing on one or more machines to optimize one or more objectives. Within the machine scheduling field there is a large variety of problem types, based on the characteristics of the jobs, the restrictions of the process and the objectives to be optimized. In this dissertation, several machine scheduling problems, ranging from the single machine environment to the multi-stage job shop environment, with varying job characteristics, process restrictions and objective functions, are scrutinized. For these problems, various algorithmic optimization approaches as well as two practical case studies are discussed. Our study starts with the analysis of a number of single machine scheduling problems for which a number of meta-heuristic solution procedures are developed. We then make the extension to the parallel machine scheduling environment and present a novel hybrid solution approach. Our study is further extended to the multi-stage job shop environment with the development of priority rules as well as two meta-heuristic solution procedures. Finally, in order to bridge the gap between theory and practice, we discuss two real-life case studies in a manufacturing and a service industry environment. In a first case study, we develop a hybrid job shop scheduling procedure that serves as a simulation tool for a Belgian manufacturing company in order to improve its current scheduling approach. Next, a link to the health care environment is made by means of a case study performed at two Belgian hospitals. This study aims at investigating the usefulness of existing machine scheduling principles and procedures in a dynamic and uncertain patient scheduling environment and at formulating critical and well-defined guidelines to improve the current way of patient planning