In today’s highly complex multi-AGV systems key research objective is finding a scheduling and routing policy that avoids deadlock while assuring that vehicle utilization is as high as possible. It is well known that finding such an optimal policy is a NP-hard task in general case. Therefore, big part of the research is oriented towards finding various suboptimal policies that can be applied to real world plants. In this paper we propose modified Banker’s algorithm for scheduling in multi-AGV systems. A predetermined mission’s path is executed in a way that some non-safe states are allowed in order to achieve better utilization of vehicles. A graph-based method of polynomial complexity for verification of these states is given. Algorithm is tested on a layout of a real plant for packing and warehousing palettes. Results shown at the end of the paper demonstrate advantages of the proposed method compared with other methods based on Banker’s algorithm.