CAREER: Approximate Scheduling Algorithms via Mathematical Relaxations

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

The problem of scheduling a set of possibly dependent tasks over a collection of machines arises in many modern application domains. In spite of intensive study, however, the general understanding of many fundamental scheduling problems is still far from satisfactory. This research will enhance understanding of the mathematical relaxation techniques to solve scheduling problems that appear in many contexts. Successful completion of the project will yield improved approximation algorithms for fundamental scheduling problems. This project will provide research and educational opportunities to both graduate and undergraduate students, and foster cross-field collaborations between different institutions. The major goal of the project is to leverage cutting-edge techniques in mathematical programming to close the gaps in the understanding of scheduling problems. The specific techniques the investigator intends to explore include: (1) leveraging the LP (linear programming) hierarchy in approximating precedence-constrained scheduling problems on identical machines, (2) exploring time-indexed LP relaxations to solve scheduling problems with weighted-sum objectives, and (3) the use of knapsack covering inequalities in capturing resource constraints arising naturally in scheduling problems. The project is centered around three mathematical-programming techniques. (1) The recent breakthrough result of Levey and Rothvoss gave a (1 + epsilon)-approximation algorithm for the makespan minimization problem for scheduling precedence-constrained unit-size jobs on constant number of machines, based on the Sherali-Adams hierarchy lift of the natural time-indexed LP relaxation for the problem. The investigator will continue this line of research, by improving these results from various angles and extending them to many other settings. What if jobs have different sizes? How can the problem with the weighted completion-time objective be handled? Can the results be extended to more general machine models? (2) Time-indexed LP relaxations are natural ones for scheduling problems, given the important role the notion of time plays in the problems. However, for many problems, their power in deriving improved algorithms has not been fully exploited. This investigation will advance the understanding of the technique by studying the scheduling problem on unrelated machines to minimize weighted completion time, directed-acyclic job scheduling and coflow scheduling problems. (3) The knapsack covering inequalities have been introduced to strengthen the basic LP relaxation for the many problems with knapsack covering constraints, and have been used to derive LP-based algorithms for many scheduling and other types of problems. The investigator aims to further advance the understanding of the technique in tackling relevant scheduling problems including weighted flow time minimization for open-shop scheduling, the single-machine scheduling problem with general cost functions, and the capacitated lot-sizing problem.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.