Online interval scheduling to maximize total satisfaction

DOI10.1016/J.TCS.2019.10.046MaRDI QIDQ2285162zbMATHOpenAlexWikidataFDO

Authors Koji M. Kobayashi

Publication date 16 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

competitive analysisonline algorithmscheduling probleminterval schedulingbest-effort service

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Abstract: The interval scheduling problem is one variant of the scheduling problem. In this paper, we propose a novel variant of the interval scheduling problem, whose definition is as follows: given jobs are specified by their {em release times}, {em deadlines} and {em profits}. An algorithm must start a job at its release time on one of $m$ identical machines, and continue processing until its deadline on the machine to complete the job. All the jobs must be completed and the algorithm can obtain the profit of a completed job as a user's satisfaction. It is possible to process more than one job at a time on one machine. The profit of a job is distributed uniformly between its release time and deadline, that is its interval, and the profit gained from a subinterval of a job decreases in reverse proportion to the number of jobs whose intervals intersect with the subinterval on the same machine. The objective of our variant is to maximize the total profit of completed jobs. This formulation is naturally motivated by best-effort requests and responses to them, which appear in many situations. In best-effort requests and responses, the total amount of available resources for users is always invariant and the resources are equally shared with every user. We study online algorithms for this problem. Specifically, we show that for the case where the profits of jobs are arbitrary, there does not exist an algorithm whose competitive ratio is bounded. Then, we consider the case in which the profit of each job is equal to its length, that is, the time interval between its release time and deadline. For this case, we prove that for $m=2$ and $mgeq3$, the competitive ratios of a greedy algorithm are at most $4/3$ and at most $3$, respectively. Also, for each $mgeq2$, we show a lower bound on the competitive ratio of any deterministic algorithm.

Recommendations

• Online Interval Scheduling to Maximize Total Satisfaction
• Interval scheduling on related machines
• scientific article; zbMATH DE number 1003261
• Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines
• Online Job Admission

Cites work

• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• An improved randomized on-line algorithm for a weighted interval selection problem
• Bounding the Power of Preemption in Randomized Scheduling
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Improved randomized online scheduling of intervals and jobs
• Improved randomized results for the interval selection problem
• Interval scheduling on identical machines
• Interval scheduling: A survey
• Note on scheduling intervals on-line
• On the \(k\)-coloring of intervals
• On-line scheduling of equal-length intervals on parallel machines
• On-line scheduling of jobs with fixed start and end times
• Online interval scheduling: Randomized and multiprocessor cases
• Online real-time preemptive scheduling of jobs with deadlines on multiple machines
• Randomized online interval scheduling
• Scheduling jobs with fixed start and end times
• The power of migration for online slack scheduling

Cited in

(6)

• Online Interval Scheduling to Maximize Total Satisfaction
• scientific article; zbMATH DE number 7051282 (Why is no real title available?)
• Approximating Interval Scheduling Problems with Bounded Profits
• Scheduling to Maximize Participation
• Online scheduling with interval conflicts
• Scheduling to maximize participation

This page was built for publication: Online interval scheduling to maximize total satisfaction

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