Competitive algorithms from competitive equilibria, non-clairvoyant scheduling under polyhedral constraints

DOI10.1145/3136754zbMATH Open1426.68309arXiv1404.1097OpenAlexW2772039599MaRDI QIDQ3177891FDOQ3177891

Authors: Sungjin Im, Janardhan Kulkarni, Kamesh Munagala 

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We introduce and study a general scheduling problem that we term the Packing Scheduling problem. In this problem, jobs can have different arrival times and sizes; a scheduler can process job $j$ at rate $x_j$, subject to arbitrary packing constraints over the set of rates ($vecx$) of the outstanding jobs. The PSP framework captures a variety of scheduling problems, including the classical problems of unrelated machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling. In this paper, we design non-clairvoyant online algorithms for PSP and its special cases -- in this setting, the scheduler is unaware of the sizes of jobs. Our two main results are, 1) a constant competitive algorithm for minimizing total weighted completion time for PSP and 2)a scalable algorithm for minimizing the total flow-time on unrelated machines, which is a special case of PSP.

Full work available at URL: https://arxiv.org/abs/1404.1097

Recommendations

• Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints
• scientific article; zbMATH DE number 6861895
• Online non-clairvoyant scheduling to simultaneously minimize all convex functions
• Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation
• Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines

zbMATH Keywords

market equilibriumonline schedulingnon-clairvoyanttotal completion timetotal flow timeproportional fairnesspolytope constraintsadversarial input

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Special types of economic equilibria (91B52)

Cited In (6)

• Non-Clairvoyant Precedence Constrained Scheduling.
• Ascending-price algorithms for unknown markets
• Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling
• An improved greedy algorithm for stochastic online scheduling on unrelated machines
• An Optimal Control Framework for Online Job Scheduling with General Cost Functions
• Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints

This page was built for publication: Competitive algorithms from competitive equilibria, non-clairvoyant scheduling under polyhedral constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177891)