Article ID: | iaor20063001 |
Country: | United Kingdom |
Volume: | 33 |
Issue: | 1 |
Start Page Number: | 132 |
End Page Number: | 157 |
Publication Date: | Jan 2006 |
Journal: | Computers and Operations Research |
Authors: | Bard Jonathan F., Zhang Xinhui |
Keywords: | heuristics, programming: integer |
Mail processing and distribution centers (P&DCs) are large factories that accept, sort, and sequence mail in preparation for delivery. A central problem in these facilities is how to schedule the equipment over the day to ensure batch production under tight equipment and workforce constraints. The problem falls into the general category of multi-level lot sizing and is notoriously difficult to solve. No exact algorithms exist that are efficient and can consistently provide high-quality solutions. In the paper, we investigate two specialized approaches for solving this problem. The first is a piece-by-piece LP-based heuristic and the second is a Benders decomposition. The heuristic uses the LP fractional solution as a target and attempts to find an integer solution that is as close to it as possible by minimizing the