CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

An efficient algorithm for solving the flexible job shop scheduling problem

Karin Thörnblad ; Ann-Brith Strömberg (Institutionen för matematiska vetenskaper, matematik) ; Michael Patriksson (Institutionen för matematiska vetenskaper) ; Torgny Almgren
25th NOFOMA conference proceedings, June 3-5 2013, Göteborg, Sweden p. 15. (2013)
[Konferensbidrag, refereegranskat]

Purpose: To investigate the efficiency of a discretization procedure utilizing a time-indexed mathe-matical optimization model for finding accurate solutions to flexible job shop scheduling problems considering objectives comprising makespan and tardiness, respectively. Design/methodology/approach: A time-indexed mixed integer programming model is used to find solutions by iteratively employing time steps of decreasing length. The solutions and computation times are compared with results from a known benchmark formulation and an alternative model. Findings: The proposed method finds significantly better solutions for the largest instances within the same time frame. Both the other models are better choices for some smaller instances, which is expected since the new method is designed for larger problems. Only our alter-native model is able to solve two of the largest instances when minimizing the tardiness. Research limitations/implications: Interesting future research topics include the introduction of constraints representing other relevant entities such as the availability of tools and fixtures, and the scheduling of maintenance activities and personnel. Practical implications: Real cases of flexible job shop problems typically yield very large models. Since the new procedure quickly finds solutions of good quality to such instances, our findings imply that the new procedure is beneficially utilized for scheduling real flexible job shops. Original/value: We show that real flexible job shop problems can be solved through the solution of a series of carefully formulated discretized mathematical optimization models.

Nyckelord: Flexible job shop scheduling, Linear integer optimization, Linear mixed integer programming, Discretization procedure, Benchmarking, Minimize makespan, Tardiness

Denna post skapades 2013-08-19. Senast ändrad 2014-10-27.
CPL Pubid: 181796


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)
Institutionen för matematiska vetenskaperInstitutionen för matematiska vetenskaper (GU)


Optimeringslära, systemteori

Chalmers infrastruktur