Feasibility recovery for the Unit-capacity Constrained Permutation Problem

The Unit-capacity Constrained Permutation Problem with Feasibility Recovery (UCPPFR) is to find a sequence of moves for pieces over a set of locations. From a given location, a piece can be moved to a unit capacity location, i.e. the latter location must be free of its original piece. Each piece has a specific type, and in the end every location must contain a piece of a required type. A piece must be handled using a specific tool, thus incurring a setup cost whenever a tool changeover is required. It could be necessary to use some Steiner locations to find a solution, thus incurring a Steiner cost. The aim of the UCPPFR is to find a sequence of moves with a minimum total setup and Steiner cost. We give a necessary and sufficient condition to check whether an instance admits a solution with no Steiner location. We show that the UCPPFR reduces to finding simultaneously a vertex-disjoint path cover and a shortest common supersequence. Finally, using a compact encoding for solutions and integer linear programming tools, we solve real instances coming from the nuclear power plant fuel renewal problem.