Paper Info
Title
Comparative approaches to equipment scheduling in high volume factories
Abstract
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 L1-norm. The procedure consists of solving the LP relaxation of the original model and two reduced mixed-integer programs. The process is similar to what has been called 'piece-by-piece decomposition' in nonlinear programming. While the goal there is to find better initial starting points for the nonlinear code, our goal is to improve solution quality.Computational testing using data provided by the Dallas P&DC confirmed the superiority of the piece-by-piece LP-based heuristic with respect to branch and bound, which proved to be computational expensive, and the Benders algorithm which took several hours to find feasible solutions. In general, the LP-based heuristic was an order of magnitude faster than branch and bound and provided solutions that were able to process more than 99.75% of the daily volume.
Year
DOI
Venue
2006
10.1016/j.cor.2004.07.003
Computers & OR
Keywords
DocType
Volume
Equipment scheduling,LP fractional solution,LP-based heuristic,Postal operations,Multi-level lot sizing,equipment scheduling,Piece-by-piece decomposition,Benders decomposition,high-quality solution,feasible solution,solution quality,Integer programming,piece-by-piece decomposition,central problem,Benders algorithm,high volume factory,piece-by-piece LP-based heuristic,comparative approach,integer solution
Journal
33
Issue
ISSN
Citations 
1
Computers and Operations Research
2
PageRank 
References 
Authors
0.42
4
2
Name
Order
Citations
PageRank
Xinhui Zhang1253.03
Jonathan F. Bard21428144.29