Mixed integer linear programming models for machine scheduling

The primary subject of this thesis is mixed integer linear programming (MILP) formulations for the non-preemptive single machine scheduling problem (SMSP), in which a set of jobs must be processed by a machine. Scheduling has been the focus of much research for over 50 years, finding strong motivation and application in the areas of production planning and manufacturing. Many real world scheduling problems that are based on the SMSP are both theoretically and computationally difficult to solve. A variety of MILP formulations have been proposed for the SMSP including several that require the planning horizon to be divided into contiguous periods of time for modelling purposes. These include the classical time indexed (TI) model and the interval indexed formulation (IIF). The size of these MILP formulations are dependent on the number of time periods, and instances of the SMSP with a large planning horizon are often not computationally solvable with these models in a reasonable time. The TI model boasts a tight linear relaxation, while the IIF does not. The IIF, however, permits a much coarser discretisation of the planning horizon and as such has relatively fewer variables and constraints. In this thesis we propose several new MILP formulations for the SMSP, which we call bucket indexed (BI) models, that generalise the TI model. These models, like the IIF may permit a much coarser discretisation of the planning horizon, but like the TI model have a strong linear relaxation. We present computational results to show the models we propose perform exceptionally well when the processing time of the smallest job is large. In addition to proposal of these BI models, several improvements and extensions are made to the IIF. We also investigate strong formulations for sequencing models, with particular application to lot sizing problems.