A primal-dual approach for capacity-constrained production planning with variable and fixed costs

A primal-dual approach is proposed to solve capacity-constrained production planning problems with variable and fixed costs. Fixed costs are modelled by an assignment sub-problem, variable costs lead to a transportation sub-problem. The principle of resource employments allows us to link the assignment sub-problem with the transportation sub-problem. A primal-dual method is defined to solve these two linked problems which are unified by a transhipment model. The heuristic is specified and its main characteristics are justified. Some experiments allow the reader to judge our approach quality. (C) 1999 Elsevier Science Ltd. All rights reserved.