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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\fancyscript{N\!\!\!P}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="script">N</mi> <mspace width="-0.166667em"/> <mspace width="-0.166667em"/> <mspace width="-0.166667em"/> <mi mathvariant="script">P</mi> </mrow> </math> </EquationSource> </InlineEquation>-hard even for a single work center with two machines, and strongly <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$\fancyscript{N\!\!\!P}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="script">N</mi> <mspace width="-0.166667em"/> <mspace width="-0.166667em"/> <mspace width="-0.166667em"/> <mi mathvariant="script">P</mi> </mrow> </math> </EquationSource> </InlineEquation>-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
