A consideration on a sliding palette problem in a two-dimensional automatic warehouse

An automatic warehouse in which n×m-k palettes are arranged two-dimensionally on a grid with m rows and n columns is considered. The palettes in the warehouse can slide independently and simultaneously with the use of k spaces, unless they collide. The minimum number of sliding operations of palettes necessary to move the specified palette to the specified position is shown, where one sliding operation is a set of slides of palettes which are executed simultaneously in a unit time without any collision. Proofs of the theorems are given which include constructions of optimum solutions