A transportation type aggregate production model with bounds on inventory and backordering

We consider a certain T period aggregate production planning model, where the two sources of production are regular and overtime. The model allows for time varying production, holding and backordering costs and includes bounds on inventory and backorders. We show that the problem has a rather interesting network structure and exploit this structure to develop a greedy algorithm to solve the problem. The procedure is easy to implement and has a computational complexity of O(T²). We report computational experience with the greedy procedure and demonstrate its superiority to a well known network simplex code, Gnet, implemented on the classical network formulation of the problem.