Competitive Flow Time Algorithms for Polyhedral Scheduling

Many scheduling problems can be viewed as allocating rates to jobs, subject to convex packing constraints on the rates. In this paper, we consider the problem of rate allocation when jobs of unknown size arrive online (non-clairvoyant setting), with the goal of minimizing weighted delay or flow time. Though this problem has strong lower bounds on competitive ratio in its full generality, we show positive results for natural and fairly broad sub-classes. More specifically, the subclasses we consider not only generalize several well-studied models such as scheduling with speedup curves and related machine scheduling, but also capture as special cases hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We establish several first positive results by making connections with two disparate disciplines: Economics and Queueing theory. First, we view the instantaneous allocation of rates as a resource allocation problem. We analyze the natural proportional fairness algorithm from economics. To do this, we extend results from market clearing literature, particularly the Eisenberg-Gale markets and the notions of Walrasian equilibria and Gross Substitutes. This yields the first constant competitive algorithm with constant speed augmentation for single-sink flow routing, routing multicast trees, and multidimensional resource allocation with substitutes resources. Next, we consider the general scheduling problem with packing constraints on rates, but with the restriction that the number of different job types is fixed. We model this problem as a non-stochastic queueing problem. We generalize a natural algorithm from queueing literature and analyze it by extending queueing theoretic ideas. We show that the competitive ratio, for any constant speed, depends polynomially only on the number of job types. Further, such a dependence on the number of job types is unavoidable for non-clairvoyant algorithms. This yields the first algorithm for scheduling multicommodity flows whose competitive ratio depends polynomially on the size of the underlying graph, and not on the number of jobs.

Authors

• Sungjin Im
• Janardhan Kulkarni
• Kamesh Munagala

Keywords

• Resource management
• Algorithm design and analysis
• Routing
• Queueing analysis
• Single machine scheduling
• Biological system modeling
• Economics
• Flow Time
• Competitive Algorithm
• Lower Bound
• Resource Allocation
• Number Of Types
• Job Type
• Queueing System
• Resource Allocation Problem
• Flow Routing
• Rate Allocation
• Machine Scheduling
• Proportional Fairness
• Competitive Ratio
• Optimal Conditions
• Total Weight
• Total Rate
• Rate Set
• Convex Optimization
• Time Instants
• Lyapunov Function
• Earliest Due Date
• Clairvoyant
• Discontinuous Change
• Concave Function
• Arrival Process
• Intensive Resources
• Optimal Schedule
• Job Completion
• Concavity
• Job Processing
• Online Algorithms
• Scheduling
• Flow-time minimization