CAREER: Designing Practical Scheduling Algorithms Based on Fluid Relaxations

该学院早期职业发展(Career)项目的研究目标是开发一种基于液体放松的排序、路线和入学控制理论。在这个项目中开发的技术，以及从它们派生的算法将有可能提高几个现实生活中系统的实际性能。这项研究将解决一系列问题，例如：(1)资源应该如何最优地将其精力分配给竞争对手？(2)额外的物理和技术约束的存在如何影响系统性能？(3)确定性调度模型和随机调度模型之间的方法论联系？(4)系统参数的随机性对最优策略有什么影响？这项研究的结果将为深入了解日程安排与其他运营和战略决策(如交货期设定和定价)的相互作用提供依据。这项工作也将有助于动态优化的发展，并有助于我们对连续线性规划问题的理解。教育计划的主要目标是介绍本科生和研究生课程安排方面令人振奋的最新发展。为此目的，将开设两门关于日程安排及其应用的课程。第一门课程将在本科阶段进行，将作为生产计划中出现的排程问题的入门课程。本课程将涵盖确定性调度和随机调度的基本概念，并将以考察调度在其他领域的作用为结束，包括物流和供应链管理。第二门课程将涵盖确定性和随机调度中的算法和结构结果，重点是最近的研究。研究生将有机会阅读和展示研究论文，参加问题会议，和/或研究问题。除了开发新课程外，该计划的教育部分将通过分发讲解文章，使本科生参与研究和推广活动。确定性和随机调度模型已成功地用于分析和控制复杂系统，其中几类工作竞争有限的共享资源。示例包括生产不同类型产品的制造系统、共享计算机系统和电信系统，其中不同的业务类型(例如，电子邮件、文件传输、视频)共享公共资源(例如，局域网中的总线、路由器)。尽管在激励问题上有相似之处，但用于分析确定性调度模型的方法与随机调度文献中的方法几乎没有共同点。这个职业发展项目的中心目标是开发一种统一的方法来分析不同应用领域中出现的确定性和随机调度模型。

The research objective of this Faculty Early Career Development (CAREER) project is to develop a theory of sequencing, routing, and admission control, based on fluid relaxations. The techniques developed in this project, and the algorithms derived from them will have the potential to improve the practical performance of several real-life systems. This research will address a variety of questions such as: (1) How should a resource optimally allocate its effort to competing jobs? (2)How do the presence of additional physical and technological constraints affect system performance? (3)What are the methodological connections between deterministic and stochastic scheduling models? (4) What effect does the stochastic nature of the system parameters have on the optimal policy? The results of this research will provide insight into how scheduling interacts with other operational and strategic decisions such as due-date setting and pricing. The work will also contribute to the development of dynamic optimization, and to our understanding of continuous linear programming problems. The main objective of the education plan is the introduction of the exciting recent developments in the area of scheduling in the undergraduate and graduate curriculum. To that end, two courses on scheduling and its applications will be developed. The first course will be at the undergraduate level and will serve as an introduction to scheduling problems that arise in production planning. This course will cover basic concepts in deterministic and stochastic scheduling, and will conclude with an examination of the role of scheduling in other areas, including logistics and supply chain management. The second course will cover algorithmic and structural results in deterministic and stochastic scheduling, with an emphasis on recent research. Graduate students will have an opportunity to read and present research papers, participate in problem sessions, and/or work on a research problem. In addition to the development of new courses, the education component of this plan will result in the involvement of undergraduates in research, and in outreach activities through the dissemination of expository articles.Deterministic and stochastic scheduling models have been successfully used to analyze and control complex systems in which several classes of jobs compete for a limited number of shared resources. Examples include manufacturing systems that produce different types of products, shared computer systems, and telecommunications systems where heterogeneous traffic types (e.g., email, file transfers, video) share common resources (e.g., buses in a local area network, routers). In spite of the similarities in the motivating problems, the methods used in analyzing deterministic scheduling models have little in common with those of the stochastic scheduling literature. The central aim of this career development project is to develop a unified approach to analyze both deterministic and stochastic scheduling models arising in diverse application domains.