Approximation Algorithms for Scheduling, Packing, and Related Logistics Problems
Approximation Algorithms for Scheduling, Packing, and Related Logistics Problems
批准号:
0430682
负责人:
David Shmoys
金额:
$0.0万
依托单位:
依托单位国家:
美国
项目类别:
Continuing grant
财政年份:
2004
资助国家:
美国
项目状态:
已结题
起止时间:
2004-09-01 至 2007-08-31
中文摘要
大多数物流问题,从大规模网络的设计,库存管理,制造企业供应链的协调,到化学加工设施的生产调度,都是NP难的,因此,不太可能有保证快速找到最优解的算法。 尽管如此,这些问题必须以自动化的方式来解决,因此人们试图设计出即使不是最佳解决方案也能产生良好解决方案的算法。在许多情况下,这是以一种特别的方式进行的,人们几乎不能保证找到的解决方案确实接近于我们所能做的最好的解决方案。 算法理论的目标是研究简化的模型,以便提取某些算法范例,然后将其应用于更现实的设置。通过研究理论模型,人们的目标是证明关于所找到的解决方案的质量的强定理所需的洞察力,转化为算法原理,这些算法可以很好地解决行业需要解决的问题。这一建议的智力价值是基于概述了一些具体的物流问题,主要集中在调度库存管理和网络设计的问题,并给出了具体的算法方法,应导致改进的近似算法的细节:算法,其中一个可以证明,找到的解决方案是保证偏离最优的一个小的量。具体地说,我们考虑了联合补货问题,一个仓库,多个零售商的分销问题,能力限制的设施选址问题,装箱问题,非对称旅行商问题,和无等待流水车间调度问题。 寻找良好的方法来提高物流规划的新效率是一个对美国整体经济非常重要的问题,这也是该提案的重要影响之一。此外,重要的是,美国劳动力拥有足够的专业知识,以应对即将到来的世纪的技术挑战。这项提案寻求资金,将有助于培养博士生,在这个非常重要的领域,为美国的经济竞争力,谁将成为下一代教师教我们的大学人口。 最后,当前的本科课程需要反映当前对优化物流算法基本原理的理解,以便我们的毕业生,明天的劳动力,准备迎接未来的挑战。
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Stochastic Optimization Models and Methods for the Sharing Economy
-
批准号:1537394
-
项目类别:Standard Grant
-
资助金额:$20.0万
-
财政年份:2015
-
负责人:David Shmoys
-
依托单位:
AF: Small: Approximation Algorithms for Problems in Logistics
-
批准号:1526067
-
项目类别:Standard Grant
-
资助金额:$40.0万
-
财政年份:2015
-
负责人:David Shmoys
-
依托单位:
IEEE Symposium on Foundations of Computer Science (FOCS) 2013, Berkeley, CA Oct 27-29, 2013
-
批准号:1348020
-
项目类别:Standard Grant
-
资助金额:$2.0万
-
财政年份:2013
-
负责人:David Shmoys
-
依托单位:
AF: Small: AAdvances in the Design of Approximation Algorithms for Optimization Problems
-
批准号:1017688
-
项目类别:Standard Grant
-
资助金额:$49.96万
-
财政年份:2010
-
负责人:David Shmoys
-
依托单位:
Approximation algorithms for discrete stochastic and deterministic optimization problems
-
批准号:0635121
-
项目类别:Continuing Grant
-
资助金额:$32.0万
-
财政年份:2006
-
负责人:David Shmoys
-
依托单位:
The Design, Analysis and Application of Approximation Algorithms
-
批准号:9912422
-
项目类别:Standard Grant
-
资助金额:$27.08万
-
财政年份:2000
-
负责人:David Shmoys
-
依托单位:
U.S.-Canada Joint Workshop on Approximation Algorithms for NP-Hard Problems, Toronto, Canada, Sept. 26 - Oct. 1, 1999
-
批准号:9904068
-
项目类别:Standard Grant
-
资助金额:$1.5万
-
财政年份:1999
-
负责人:David Shmoys
-
依托单位:
Approximation Algorithms via Linear Programming
-
批准号:9700029
-
项目类别:Standard Grant
-
资助金额:$0.0万
-
财政年份:1997
-
负责人:David Shmoys
-
依托单位:
Near-Optimal Solutions for Combinatorial Problems: Algorithms and Complexity
-
批准号:9307391
-
项目类别:Continuing grant
-
资助金额:$0.0万
-
财政年份:1994
-
负责人:David Shmoys
-
依托单位:
PYI: The Design and Analysis of Efficient Algorithms
-
批准号:8996272
-
项目类别:Continuing Grant
-
资助金额:$15.05万
-
财政年份:1989
-
负责人:David Shmoys
-
依托单位:
Presidential Young Investigator Award (Computer Research)
-
批准号:8657688
-
项目类别:Continuing Grant
-
资助金额:$11.34万
-
财政年份:1987
-
负责人:David Shmoys
-
依托单位:
海外基金