The Unit-capacity Constrained Permutation Problem

Pascale Bendotti

doi:10.1016/j.ejor.2018.01.049

The Unit-capacity Constrained Permutation Problem

2018-07-01

0

PRE

AI

DOI：10.1016/j.ejor.2018.01.049

原文链接

原文求助

摘要

En 中文

The Unit-capacity Constrained Permutation Problem (UCPP) is to find a sequence of moves for pieces over a set of locations. From a given location, a piece can be moved towards a location with a unit capacity constraint, i.e. the latter location must be free of its original piece. Each piece has a specific type and at the end every location must contain a piece of a required type. A piece must be handled using a specific tool incurring a setup cost whenever a tool changeover is required. The aim of the UCPP is finding a sequence of moves with a minimum total setup cost. This problem arises in the Nuclear power plant Fuel Renewal Problem (NFRP) where locations correspond to fuel assemblies and pieces to fuel assembly inserts. We first show that the UCPP is NP-hard. We exhibit some symmetry and dominance properties and propose a dynamic programming algorithm. Using this algorithm, we prove that the UCPP is polynomial when two tools and two types are considered. Experimental results showing the efficiency of the algorithm for some instances coming from the NFRP are presented. (C) 2018 Elsevier B.V. All rights reserved.

Keyword:

Combinatorial optimization

OR in energy

Complexity theory

Dynamic programming

Dominance and symmetry properties

The Unit-capacity Constrained Permutation Problem

摘要

AI总结

期刊

机构