Scheduling algorithms for procrastinators. (English) Zbl 1168.90423

Summary: 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.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI arXiv


[1] Albers, S., & Fujiwara, H. (2006). Energy-efficient algorithms for flow time minimization. In Lecture notes in computer science : Vol. 3884. Proceedings of the 23rd annual symposium on theoretical aspects of computer science (STACS) (pp. 621–633). Berlin: Springer. · Zbl 1136.68345
[2] Alidaee, B., & Womer, K. (1999). Scheduling with time dependent processing times: review and extensions. Journal of Operational Research Society, 50, 711–720. · Zbl 1054.90542
[3] Arkin, E. M., Bender, M. A., Mitchell, J. S. B., & Skiena, S. S. (1999). The lazy bureaucrat scheduling problem. In Proceedings of the 6th workshop on discrete algorithms WADS (pp. 122–133). · Zbl 1063.90530
[4] Arkin, E. M., Bender, M. A., Mitchell, J. S. B., & Skiena, S. S. (2003). The lazy bureaucrat scheduling problem. Information and Computation, 184(1), 129–146. · Zbl 1026.90037
[5] Bachman, A., Janiak, A., & Kovalyov, M. Y. (2002). Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters, 81(2), 81–84. · Zbl 1032.68019
[6] Bansal, N., & Pruhs, K. (2005). Speed scaling to manage temperature. In Lecture Notes in Computer Science : Vol. 3404. Proceedings of the 22nd annual symposium on theoretical aspects of computer science (STACS) (pp. 460–471). Berlin: Springer. · Zbl 1118.68769
[7] Bansal, N., Kimbrel, T., & Pruhs, K. (2004). Dynamic speed scaling to manage energy and temperature. In Proceedings of the 45th symposium on foundations of computer science (FOCS) (pp. 520–529). · Zbl 1326.68043
[8] Bender, M. A., Chakrabarti, S., & Muthukrishnan, S.(1998). Flow and stretch metrics for scheduling continuous job streams. In Proceedings of the 9th annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 270–279). · Zbl 0929.68012
[9] Bender, M. A., & Rabin, M. O. (2002). Online scheduling of parallel programs on heterogeneous systems with applications to Cilk. Theory of Computing Systems Special Issue on SPAA00, 35, 289–304. · Zbl 1017.68035
[10] Bunde, D. P. (2006). Power-aware scheduling for makespan and flow. In Proceedings of the 18th ACM symposium on parallelism in algorithms and architectures (SPAA) (pp. 190–196).
[11] Chekuri, C., & Bender, M. A. (2001). An efficient approximation algorithm for minimizing makespan on uniformly related machines. Journal of Algorithms, 41, 212–224. · Zbl 1051.68150
[12] Chudak, F. A., & Shmoys, D. B. (1999). Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. Journal of Algorithms, 30(2), 323–343. An earlier version appears in SODA ’97 · Zbl 0923.68012
[13] Davis, E., & Jaffe, J. M. (1981). Algorithms for scheduling tasks on unrelated processors. Journal of the ACM, 28(4), 721–736. · Zbl 0472.68020
[14] Demaine, E. D., Mitchell, J. S. B., & O’Rourke, J. (2005). The open problems project. Retrieved February 13, 2005 from http://maven.smith.edu/\(\sim\)orourke/TOPP/ .
[15] Eppstein, D. (2007). Geometry junkyard, computational and recreational geometry pointers. Retrieved April 6, 2007 from http://www.ics.uci.edu/\(\sim\)eppstein/junkyard/open.html .
[16] Fleischer, L., & Skutella, M. (2002). The quickest multicommodity flow problem. In Lecture notes in computer science : Vol. 2337. Proceedings of the 9th integer programming and combinatorial optimization (IPCO) conference (pp. 36–53). Berlin: Springer. · Zbl 1049.90106
[17] Fleischer, L., & Skutella, M. (2003). Minimum cost flows over time without intermediate storage. In Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 66–75). · Zbl 1094.90511
[18] Gawiejnowicz, S., & Pankowska, L. (1995). Scheduling jobs with varying processing times. Information Processing Letters, 54(3), 175–178. · Zbl 0875.68421
[19] Gawiejnowicz, S., Kurc, W., & Pankowska, L. (2002). A greedy approach for a time-dependent scheduling problem. In Lecture notes in computer science (Vol. 2328, pp. 79–86). Berlin: Springer. · Zbl 1057.68547
[20] Hepner, C., & Stein, C. (2002). Minimizing makespan for the lazy bureaucrat problem. In Lecture notes in computer science : Vol. 2368. Proceedings of the 8th Scandinavian workshop on algorithm theory (SWAT) (pp. 40–50). Berlin: Springer. · Zbl 1078.90530
[21] Irani, S., & Pruhs, K. R. (2005). Algorithmic problems in power management. SIGACT News, 36(2), 63–76.
[22] Jansen, K., & Porkolab, L. (1999). Improved approximation schemes for scheduling unrelated parallel machines. In Proceedings of the 31st annual ACM symposium on theory of computing (pp. 408–417). · Zbl 1082.90525
[23] Karger, D., Stein, C., & Wein, J. Scheduling algorithms. In Atallah M. J. (Ed.), Handbook of algorithms and theory of computation, CRC Press, Boca Raton, 1998
[24] Lawler, E. L., & Labetoulle, J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the ACM, 25(4), 612–619. · Zbl 0388.68027
[25] Orda, A., & Rom, R. (1990). Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM, 37(3), 607–625. · Zbl 0699.68074
[26] O’Rourke, J. (1981). Advanced problem 6369. In American mathematical monthly.
[27] Pruhs, K., van Stee, R., & Uthaisombut, P. (2005). Speed scaling of tasks with precedence constraints. In Proceedings of the 3rd workshop on approximation and online algorithms (WAOA) (pp. 307–319). · Zbl 1177.68035
[28] Uysal-Biyikoglu, E., Prabhakar, B., & El Gamal, A. (2002). Energy-efficient packet transmission over a wireless link. IEEE/ACM Transactions on Networking, 10(4), 487–499. · Zbl 05458906
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.