Feasibility recovery for the Unit-capacity Constrained Permutation Problem

作者：Bendotti Pascale; Fouilhoux Pierre^*

来源：Discrete Optimization, 2016, 22: 66-86.

DOI：10.1016/j.disopt.2015.09.004

• Discrete location and assignment
• Integer linear programming
• Vertex-disjoint path cover
• Shortest common supersequence

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.

• 出版日期2016-11