Scheduling with due dates and time-lags : new theoretical results and applications

Manufacturing and service environments involve decisions on sequencing activities. Some examples are assembly operations in workshops, the elaboration of data by computer systems and the handling of products by operators in warehouses. Scheduling theory studies the mathematical structures of such problems with the objective of designing theoretical models and solution algorithms that can be used in practice. In this thesis we investigate scheduling models with time-lags and release/due dates inspired by two realworld problems: transportation of goods and appointment scheduling for chemotherapy patients. The first part of this thesis studies the minimisation of the maximum lateness for two batch scheduling problems with release/due dates and equal processing times: one with a single machine and one with parallel machines. These theoretical models represent the problem of scheduling the delivery of goods within given time windows using one or more limited capacity vehicles. We design two enhanced polynomial-time algorithms that, for the single machine case, outperform the best algorithms known in literature, and, for the parallel machine case, establish the first solution algorithm. In the second part we investigate the coupled-operation scheduling model with timelags which characterises some important features of the problem of booking treatment appointments for chemotherapy patients. The objective is to develop a solution algorithm that minimises the maximum completion time (makespan). Initially we investigate a possible compact representation of a solution considering the sub-problem with a fixed sequence of the first operations of the jobs. We prove that this special case of the problem is NP-hard in the strong sense even in the case of unit processing times. Then we adapt a technique used for solving job shop problems with no-wait constraints to our coupled operation problem and develop an efficient tabu-search heuristic that outperforms the algorithms known in literature. In the last part, we introduce the problem of booking appointments for chemotherapy treatments in an outpatient clinic which is an example of real-world scheduling problem with complex time-lags and release/due dates constraints. We design an innovative 4-stage approach based on the concept of a multi-level template schedule which is generated solving a number of multi-objective integer linear programs. The evaluation of our approach using historical data shows that, using available resources, 20% additional appointments could be scheduled in the clinic eliminating peaks of workloads, maintaining short waiting days/times and improving the overall patient and staff experience.