New valid inequalities for a time-indexed formulation of the flexible job shop scheduling problem

Abstract

In this thesis a family of valid inequalities originally formulated for single- and parallel machine scheduling problems are extended to a time-indexed, mixed integer linear programming formulation of the exible job shop scheduling problem. The model of the exible job shop scheduling problem that is used for this purpose was originally formulated in the licentiate thesis [22], and is based on the practical case of scheduling the production of aircraft engine components at a multitask production cell in Trollhättan, Sweden. The strength of the valid inequalities when applied to this model is assessed by means of computational testing. This has been performed using a cutting-plane method on Fattahi test instances, both with the objective of minimizing makespan as well as minimizing tardiness. For both objectives the new valid inequalities have yielded improved lower bounds, however with varying effect. Computational results are reported along with suggestions for implementation of the valid inequalities that are likely to grant the best results. Keywords: multipurpose machine, exible job shop scheduling problem, MILP, mathe- matical optimization, time-indexed decision variables, valid inequalities, polyhedral methods, cutting-plane methods, makespan-tardiness