CAREER: Designing Practical Scheduling Algorithms Based on Fluid Relaxations

Columbia University, New York NY

Investigators

Abstract

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.