A linear-time algorithm for determining the order of moving products in reallocation problems

The reallocation problem is defined as determining whether products can be moved from their current storehouses to their target storehouses in a number of moves that is less than or equal to a given number. This problem is defined simply and has many practical applications. We previously presented the necessary and sufficient condition whether an instance of the reallocation problem is feasible, as well as a linear-time algorithm that determines whether all products can be moved, when the volume of the products is restricted to one. However, a linear-time algorithm that generates the order of moving the products has not been reported yet. Such an algorithm is proposed in this paper. We have also previously proved that the reallocation problem is NP-complete in the strong sense when the volume of the products is not restricted and the products have evacuation storehouses into which they can temporarily be evacuated. In this paper we show that the reallocation problem is NP-complete in the strong sense even when none of the products has evacuation storehouses.