In English

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

David Leffler
Göteborg : Chalmers tekniska högskola, 2015. 65 s.
[Examensarbete på avancerad nivå]

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



Publikationen registrerades 2015-06-04. Den ändrades senast 2015-12-10

CPL ID: 217994

Detta är en tjänst från Chalmers bibliotek