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

Typ
Examensarbete för masterexamen
Master Thesis
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2015
Författare
Leffler, David
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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
Beskrivning
Ämne/nyckelord
Matematik , Grundläggande vetenskaper , Mathematics , Basic Sciences
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material
Index