Flexible job shop scheduling with blockages

R. Hansmann (), T. Rieger () and U. Zimmermann ()

Mathematical Methods of Operations Research, 2014, vol. 79, issue 2, 135-161

Abstract: Motivated by an application in rail car maintenance, we study a variant of makespan-minimizing flexible job shop scheduling with work centers (FJc). In standard FJc a work center contains parallel machines, i.e. any machine in the work center is accessible whenever idle. In our variant, a work center consists of a linearly ordered set of machines with restricted accessibility, i.e. a busy machine blocks access to all succeeding machines. In rail car maintenance, the machines of a work center are located sequentially along a track. Therefore, a rail car waiting before or after some maintenance step can neither reach nor leave an idle machine if another rail car blocks the access path on the track. We call the resulting problem FJc with blockages. It turns out to be weakly $$\fancyscript{N\!\!\!P}$$ N P -hard even for a single work center with two machines, and strongly $$\fancyscript{N\!\!\!P}$$ N P -hard for a single work center. We derive a mixed integer linear optimization model, we present heuristic as well as exact solution methods, and we discuss computational results. In particular, we observe that our implementation of a branch&bound procedure is quite competitive with the commercial solvers Cplex 12.4 and Gurobi 5.0. Copyright Springer-Verlag Berlin Heidelberg 2014

Keywords: Flexible job shop scheduling; Discrete optimization; Mixed integer programming; Rail car maintenance (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-013-0456-3 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:79:y:2014:i:2:p:135-161

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-013-0456-3

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().