Search

In classical scheduling models, it is normally assumed that the processing times of jobs are fixed. However, in the recent years, there has been a growing interest in models with variable processing times. Some of the common rationales provided for considering such models, is as follows: the machine conditions may deteriorate as more jobs are processed, resulting in higher than normal processing times, or conversely, the machine’s operator may gain more experience as more jobs are processed, so he/she can process the jobs faster. Another direction of improving the practical relevance of models is by introducing certain rate-modifying activities, such as maintenance periods, in the schedule. In this thesis, we mainly focus on the study of integrated models which allow changing processing times and rate-modifying activities. When this project was started, it was felt that there was a major scope of improvement in the area, both in terms of creating more general, practically relevant models and developing faster algorithms that are capable of handling a wide variety of problems. In this thesis, we address both these issues. We introduce several enhanced, practically relevant models for scheduling problems with changing times that allow various types of rate-modifying activities, various effects or a combination of effects on the processing times. To handle these generalised models, we developed a unified framework of algorithms that use similar general principles, through which, the effects of rate-modifying activities can be systematically studied for many different scenarios.

Scheduling Theory studies planning and timetabling of various industrial and human activities and, therefore, is of constant scientific interest. Being a branch of Operational Research, Theory of Scheduling mostly deals with problems of practical interest which can be easily (from a mathematical point of view) solved by full enumeration and at the same time usually require enormous time to be solved optimally. Therefore, one attempts to develop algorithms for finding optimal or near optimal solutions of the problems under consideration in reasonable time. If the output of an algorithm is not always an optimal solution then the worst-case analysis of this algorithm is undertaken in order to estimate either a relative error or an absolute error that holds for any given instance of the problem. Scheduling problems which are usually considered in the literature assume that the processing facilities are constantly available throughout the planning period. However, in practice, the processing facility, e.g. a machine, a labour, etc. can become non-available due to various reasons, e.g. breakdowns, lunch breaks, holidays, maintenance work, etc. All these facts stimulate research in the area of scheduling with non-availability constraints. This branch of Scheduling Theory has recently received a lot of attention and a considerable number of research papers have been published. This thesis is fully dedicated to scheduling with non-availability constraints under various assumptions on the structure of the processing system and on the types of non-availability intervals.