  Reallocation scheduling is one of the most fundamental problems in various
areas such as supply chain management, logistics, and transportation science.
In this paper, we introduce the reallocation problem that models the scheduling
in which products are with fixed cost, non-fungible, and reallocated in
parallel, and comprehensively study the complexity of the problem under various
settings of the transition time, product size, and capacities. We show that the
problem can be solved in polynomial time for a fundamental setting where the
product size and transition time are both uniform. We also show that the
feasibility of the problem is NP-complete even for little more general
settings, which implies that no polynomial-time algorithm constructs a feasible
schedule of the problem unless P$=$NP. We then consider the relaxation of the
problem, which we call the capacity augmentation, and derive a reallocation
schedule feasible with the augmentation such that the completion time is at
most the optimal of the original problem. When the warehouse capacity is
sufficiently large, we design constant-factor approximation algorithms under
all the settings. We also show the relationship between the reallocation
problem and the bin packing problem when the warehouse and carry-in capacities
are sufficiently large.
