Approximation Algorithms for Scheduling, Packing, and Related Logistics Problems

点击翻译按钮获取中文摘要

Most logistics problems, ranging from the design of large-scale networks, the management of inventory, the coordination of the supply-chain for a manufacturing enterprise, to the scheduling of production in a chemical processing facility, are NP-hard, and hence, unlikely to have algorithms that are guaranteed to find optimal solutions quickly. Nonetheless, these problems must be tackled in an automated way, and so one tries to design algorithms that produces good solutions, if not optimal ones. In many cases, this is done in an ad hoc way, and one has little assurance that the solutions found are really close to the best one can do. The goal of the theory of algorithms is to study simplified models, so as to extract certain algorithmic paradigms that can then be applied to more realistic settings. By studying theoretical models, one has the aim that the insight needed to prove strong theorems about the quality of the solutions found, translates into algorithmic principles that lead to algorithms that work well on the problems that industry needs to solve. The intellectual merit of this proposal is based on outlining a number of specific logistics problems, focusing primarily on problems from scheduling inventory management and network design, and giving details of specific algorithmic approaches that should lead to improved approximation algorithms: algorithms for which one can prove that the solutions found are guaranteed to deviate from the optimal by a small amount. Specifically, we consider the joint replenishment problem, the one-warehouse, multi-retailer distribution problem, the capacitated facility location problem, the bin-packing problem, the asymmetric traveling salesman problem, and the no-wait flow-shop scheduling problem. Finding good approaches to gain new efficiencies in logistical planning is an issue that is important for the overall US economy, and this is one of the significant broader impacts of this proposal. Furthermore, it is important that the US workforce has sufficient expertise to meet the technological challenges of the coming century. This proposal seeks funds that will aid in the training of doctoral students, in this very important area for the economic competitiveness of the US, who will become the next generation of faculty teaching our college population. Finally, current undergraduate courses need to reflect the current understanding of the basic principles of algorithms in optimizing logistics, so that our graduates, tomorrow's workforce, are prepared to meet the challenges ahead.