A decision support system for single machine scheduling problems

Production planning often implies scheduling a set of tasks, involving very complex product routings. Nevertheless, it is often possible to identify critical points for which a careful planning leads to clear gains in productivity. The paper describes a real situation of this type, and identifies a particular scheduling problem where there are ‘time windows’ for the tasks, and ‘setup times’ exist. This problem was modelled as a Travelling Salesman Problem with additional constraints. Given the complexity and the size of the practical situation under study, a local search algorithm was developed. After constructing an initial feasible schedule, this algorithm iteratively improves that solution, by an exchange procedure specially designed for this case. Finally, illustrative computational results are presented, and a practically useful Decision Support System, which integrates the algorithm, is described.