Production planning is an important task in manufacturing systems. We consider a real-world capacitated lot-sizing problem (CLSP) from the process industry. Because the problem requires discrete lot-sizes, domain-specific methods from the literature are not directly applicable. We therefore approach the problem with W_(SAT) (OIP), a new domain-independent heuristic for integer optimization which generalizes the Walksat algorithm. W_(SAT) (OIP) performs stochastic tabu search and operates on over-constrained integer programs. We empirically compare W_(SAT) (OIP) to a state-of-the-art mixed integer programming branch-and-bound solver (CPLEX 4.0) on real problem data. We find that integer local search is considerbly more robust than MIP branch-and-bound in finding feasible solutions in limited time, and branch-and-bound can only solve a sub-class of the CLSP with discrete lot-sizes. With respect to production cost, both methods find solutions of similar quality.
展开▼
