Robust min-max regret approach for a single machine scheduling problem with common due date

This thesis aims to give to firms a tool that supports short-term decisions about the processing order of different jobs on a single machine. In particular, a lot of companies often face scheduling problems where the goal is to minimize the number of overdue jobs or, simply, delays. The importance to find a good solution has impact not only for customer loyalty but, most of all, in terms of production costs: usually delays, due to contractual constraints, involve the payment of penalties related to the number of late jobs or related to the overall amount of delay. In these situations, if the order scheduling is not computed by a robust tool, decisions follow, in most cases, the importance of jobs or the importance of the customer without having an overall view of the different effects that the entire schedule entails. Unfortunately, these soft resolution methods don’t ensure an optimal solution but only a solution that may or may not be considered good enough. The idea behind this thesis is to present and to explain an algorithm that, given a number n of jobs and parameters for each one, returns a schedule order with the objective to minimize the weighted number of jobs completed after a specific due-date. It’s very important to understand that the presented algorithm doesn’t ensure the calculation of the optimal solution but simply a solution that we can consider sufficiently close to the optimal one: we might be lucky and get the best schedule, but if that doesn’t happen we are sure to obtain a sufficiently good solution. The difference between the proposed solution method and a simply subjective scheduling method, since both don’t ensure the optimal schedule, is given by the reliability of the solution: behind the first one there is a defined scientific criterion described by the concept of maximum regret, while in the second one there may not be a criterion that makes the scheduling completely reliable in terms of achieving the objective function. Finally, we have to emphasize a strong assumption: the jobs, which will be processed in the same machine (single machine scheduling problem), have uncertain processing times described by intervals. However, there is also no information about the probability distribution of processing times within the intervals. So, we have to face a scheduling problem in which the timing scenario is not deterministic for each job but completely random between a lower and an upper bound. In Chapter 1, we discuss the topic of Combinatorial Optimization that is the basis of our solution algorithm; in Chapter 2, we analyze the concept of robustness of an algorithm in Combinatorial Optimization by distinguish the deterministic case and uncertain variables case; Chapter 3 is dedicated to the concept of scheduling which will lead us, subsequently, to a complete description and formulation of the problem (Chapter 4); in Chapter 5, a solution approach and its execution are described from a logical and demonstrative point of view; in the Chapter 6, some tests are performed and explained to verify the robustness of the solution. Finally, in Chapter 7, the results obtained and the general conclusions are discussed.