The problem of scheduling a given set of equipments in a single-stage, multi-item compatible environment, with the objective of maximizing capacity utilization is formulated as a maximal flow problem in a Multiple Arc Network (MAN). The production is usually planned against customers’ orders, and different customers are assigned different priorities. The model aims to provide optimal production schedule with an objective of maximizing capacity utilization, so that the customer-wise delivery schedules are fulfilled, keeping in view the customer priorities. Algorithms have been presented for solving the MAN formulation of the production planning with customer priorities. The suitability of the algorithms has been demonstrated with small examples. Key Words: Scheduling, Maximal Flow Problem, Multiple Arc Network Model, Optimization.