Autonomous mobile robots (AMRs) are increasingly deployed in intralogistics to automate warehouse operations. A key advantage of AMRs is their continuous availability, enabling them to operate during off-peak hours. This work addresses the multi-bay unit-load pre-marshalling problem (MUPMP), an extension of the unit-load pre-marshalling problem to larger, more realistic warehouse environments with multiple bays. Unit-load pre-marshalling leverages off-peak time intervals to sort a block stacking warehouse in anticipation of future orders. These larger warehouse configurations require not only the minimization of the number of moves but also the consideration of time when making sorting decisions. Our step-based approach first determines the access direction for each stack, then finds a sequence of short-time moves to sort the warehouse. For the move search, we compare a time-efficient A* algorithm with a solution-optimal constraint programming approach. Further, we extend the multi-bay unit-load pre-marshalling problem to multiple AMRs. We introduce an additional routing step that assigns the pre-marshalling moves to a fleet of AMRs, minimizing either travel time or makespan. The results demonstrate that the presented approach is able to efficiently find and allocate the necessary reshuffling moves to transfer a multi-bay block stacking system into a blockage-free state using multiple AMRs.