transparent gif


Ej inloggad.

Göteborgs universitets publikationer

On the Optimization of Schedules of a Multitask Production Cell

Författare och institution:
Karin Thörnblad (Institutionen för matematiska vetenskaper, Chalmers/GU)
Utgiven i serie vid Göteborgs universitet:
Preprint - Department of Mathematical Sciences, Chalmers University of Technology and Göteborg University, ISSN 1652-9715; nr 2011:19
Antal sidor:
Chalmers University of Technology
Datum för examination:
Tidpunkt för examination:
Sal Pascal, Matematiska Vetenskaper, Chalmers Tvärgata 3, Chalmers Tekniska Högskola
Stefan Engevall, Institutionen för Teknik och Naturvetenskap, Linköpings Universitet
Inkluderade delarbeten:
Fulltextlänk (lokalt arkiv):
Sammanfattning (abstract):
Volvo Aero has invested in a complex production cell containing a set of multipurpose machines. The problem of finding optimal schedules for this multitask cell is a complex combinatorial optimization problem which is recognized as a flexible job shop problem. This thesis proposes an approach to find such schedules using mathematical optimization. The mathematical models developed so far are presented together with a study of their interrelations, both from a computational and from a modelling perspective. One result of the study is that one of these models, a time-indexed model with nail variables, outperforms all the others presented. To our knowledge, this model is the first for the flexible job shop problem using this type of variables. In order to reduce the number of variables in the time-indexed models, a heuristic has been developed which finds an upper bound on the optimal value of the makespan. Computational results are presented for several variants of the time-indexed model and the engineer’s model, the latter belonging to a family of models widely used in job shop scheduling. The objective employed for the computations is the minimization of a weighted sum of the total tardiness and the sum of job completion times. A comparison is made between optimal schedules emanating from the timeindexed model and schedules resulting from the use of three well-known dispatching rules, using the data from 21 real production scenarios. The tardiness and the sum of job completion times are on average 6–22% larger in the schedules resulting from the use of the dispatching rules compared to those obtained in the optimal schedules. The first appended paper provides the results from a similar comparison for a number of scenarios, constructed by using data emanating from the multitask cell. The computational complexity of the problem of scheduling the multitask cell is also investigated. The second appended paper contains a proof of a complexity result for a related scheduling problem, namely flow-shop scheduling with deteriorating jobs. This thesis has been written in close cooperation with the Department of Logistics Development at Volvo Aero Corporation.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
Matematik ->
Beräkningsmatematik ->
Tillämpad matematik
Maskinteknik ->
Produktionsteknik, arbetsvetenskap och ergonomi ->
Industriell teknik och ekonomi
mathematical optimization, flexible job shop scheduling, mixed integer linear programming (MILP), complexity analysis, mathematical modelling, production planning, multi-purpose machine, dispatching rule, priority function, total flowtime, total tardiness, release date, due date
Chalmers styrkeområden:
Postens nummer:
Posten skapad:
2011-08-25 09:42
Posten ändrad:
2011-09-02 08:37

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007