A General Heuristic for Production Planning Problems

摘要

We consider production planning problems with the restriction that all integer variables model Setups. Since finding a feasible solution of such problems is in general NP-complete, the classical approaches have been the use of heuristics to find good feasible Solutions on the one hand, or branch and cut on the other hand. In the case of the former, a dual bound is not available, and there is no guarantee of solution quality. For the latter, the accent has been on improving the dual bound and only the simplest schemes have been used to find good feasible Solutions. Here we first show that such simple schemes may run into trouble, even when applied to very simple problems. This motivates the proposed heuristic, IPE, which is designed to be used within a branch-and-cut approach. We test the Performance of the heuristic on various published lot-sizing and network-design problems, with and without tightened reformulations. We compare these results with other heuristics and with time truncated branch-and-bound searches. IPE appears to be the best choice for large problems with weak formulations.