Approximation Algorithms for Scheduling, Packing, and Related Logistics Problems

调度、包装和相关物流问题的近似算法

• 批准号: 0430682
• 负责人: David Shmoys
• 金额: --
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430682&HistoricalAwards=false
• 关键词: Approximation; Algorithms; Scheduling; Packing; Related

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.

大多数物流问题，从大规模网络的设计、库存管理、制造企业供应链的协调，到化学处理设施的生产调度，都是np困难的，因此，不太可能有保证能快速找到最佳解决方案的算法。尽管如此，这些问题必须以自动化的方式解决，因此人们试图设计出能够产生良好解决方案的算法，即使不是最优解决方案。在许多情况下，这是以一种特别的方式完成的，并且很难保证找到的解决方案真的接近于最好的解决方案。算法理论的目标是研究简化模型，从而提取某些算法范式，然后将其应用于更现实的设置。通过研究理论模型，人们的目标是将证明所发现的解决方案质量的强大定理所需的洞察力转化为算法原理，从而产生能够很好地解决行业需要解决的问题的算法。这一建议的智力价值是基于概述了一些具体的物流问题，主要集中在调度库存管理和网络设计的问题上，并给出了具体算法方法的细节，这些算法应该导致改进的近似算法：人们可以证明所找到的解决方案保证与最优解有少量偏差的算法。具体来说，我们考虑了联合补货问题、一个仓库、多个零售商的配送问题、有能力的设施选址问题、装箱问题、不对称旅行商问题和无等待流车间调度问题。找到提高物流规划效率的好方法对整个美国经济来说都是一个重要的问题，这也是该提案的重要影响之一。此外，重要的是，美国劳动力必须具备足够的专业知识，以应对下个世纪的技术挑战。该提案寻求资金，以帮助培养博士研究生，在这个对美国经济竞争力非常重要的领域，他们将成为教育我们大学人口的下一代教师。最后，当前的本科课程需要反映当前对优化物流的算法基本原理的理解，以便我们的毕业生，未来的劳动力，准备好迎接未来的挑战。