Scheduling algorithms for procrastinators

DOI10.1007/S10951-007-0038-4zbMATH Open1168.90423arXivcs/0606067OpenAlexW1986250791MaRDI QIDQ835586FDOQ835586

Authors: Michael A. Bender, Raphaël Clifford, Kostas Tsichlas 

Publication date: 28 August 2009

Published in: Journal of Scheduling (Search for Journal in Brave)

Abstract: This paper presents scheduling algorithms for procrastinators, where the speed that a procrastinator executes a job increases as the due date approaches. We give optimal off-line scheduling policies for linearly increasing speed functions. We then explain the computational/numerical issues involved in implementing this policy. We next explore the online setting, showing that there exist adversaries that force any online scheduling policy to miss due dates. This impossibility result motivates the problem of minimizing the maximum interval stretch of any job; the interval stretch of a job is the job's flow time divided by the job's due date minus release time. We show that several common scheduling strategies, including the "hit-the-highest-nail" strategy beloved by procrastinators, have arbitrarily large maximum interval stretch. Then we give the "thrashing" scheduling policy and show that it is a Theta(1) approximation algorithm for the maximum interval stretch.

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

Recommendations

• scientific article; zbMATH DE number 2119737
• The lazy bureaucrat scheduling problem
• scientific article; zbMATH DE number 2185608
• Approximation algorithms for average stretch scheduling
• Algorithms and Data Structures

zbMATH Keywords

NP-completeonline schedulingstretchhit-the-highest-nailinterval stretchprocrastinateprocrastinatorsum-of-squares problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Cites Work

• Energy-Efficient Algorithms for Flow Time Minimization
• Speed scaling to manage energy and temperature
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Minimizing the total weighted completion time of deteriorating jobs
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Scheduling with time dependent processing times: Review and extensions
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Online scheduling of parallel programs on heterogeneous systems with applications to Cilk
• An efficient approximation algorithm for minimizing makespan on uniformly related machines.
• Title not available (Why is that?)
• STACS 2005
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms for Scheduling Tasks on Unrelated Processors
• Scheduling jobs with varying processing times
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Approximation and Online Algorithms
• The lazy bureaucrat scheduling problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Online scheduling to minimize maximum response time and maximum delay factor
• Title not available (Why is that?)
• Upper domination: complexity and approximation
• The many facets of upper domination
• OL-DEC-MDP model for multiagent online scheduling with a time-dependent probability of success

This page was built for publication: Scheduling algorithms for procrastinators

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