The problem of optimization of cutting modes for multi-position machines with multi-spindle heads is considered. Parts of several types are groped into batches. Each tool can be used for machining different parts of a batch. Cutting modes to be defined should provide the required throughput, meet the constraints on the cutting process characteristics and minimize the production cost. Decomposition techniques are proposed. These techniques are based on the method of Lagrange multipliers and the concept of fragmentary parameterization.