Skip to main content
SpringerLink
Log in

A Model for Minimizing Active Processor Time

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job J i has an integer length ℓ i as well as a set T i of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can schedule up to B jobs at a timeslot t so long as it is “active” at t. The goal is to schedule all the jobs in the fewest number of active timeslots. The machine consumes a fixed amount of energy per active timeslot, regardless of the number of jobs scheduled in that slot (as long as the number of jobs is non-zero). In other words, subject to ℓ i units of each job i being scheduled in its feasible region and at each slot at most B jobs being scheduled, we are interested in minimizing the total time during which the machine is active. We present a linear time algorithm for the case where jobs are unit length and each T i is a single interval, assuming that jobs are given in sorted order. For general T i , we show that the problem is NP-complete even for B=3. However when B=2, we show that it can be efficiently solved. In addition, we consider a version of the problem where jobs have arbitrary lengths and can be preempted at any point in time. For general B, the problem can be solved by linear programming. For B=2, the problem amounts to finding a triangle-free 2-matching on a special graph. We extend the algorithm of Babenko et al. (Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120–129, 2010) to handle our variant, and also to handle non-unit length jobs. This yields an \(O(\sqrt{L} m)\) time algorithm to solve the preemptive scheduling problem for B=2, where L=∑ i ℓ i . We also show that for B=2 and unit length jobs, the optimal non-preemptive schedule has active time at most 4/3 times that of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. If each job needs access to multiple memory banks in order to be satisfied, via a reduction from the k-densest subgraph problem, it is NP-complete to determine whether there exists a schedule satisfying C jobs and being active for at most A units of time.

  2. When the ordering of jobs by release times is the same as the ordering of jobs by deadlines.

  3. The problem can be solved in O(n 2 T 2(n+T)) time using Dynamic Programming as was shown by Even et al. [22], albeit the complexity of their solution is high. Their algorithm solves the problem of stabbing a collection of horizontal intervals with the smallest number of vertical stabbers, each stabber having a bounded capacity.

  4. By preprocessing jobs in order by release time, we can compress the intervals to enforce this property, since the jobs are unit length.

  5. This definition of a 2-matching scales the usual definition by a factor 1/2, i.e., the weights are usually 0,1 or 2.

  6. Our algorithm was developed independently of the authoritative algorithm of [5].

  7. In fact, we only use alternating cycles of odd length.

References

  1. Albers, S.: Algorithms for energy saving. In: Efficient Algorithms, pp. 173–186 (2009)

    Chapter  Google Scholar 

  2. Albers, S.: Energy-efficient algorithms. Commun. ACM 53(5), 86–96 (2010)

    Article  MathSciNet  Google Scholar 

  3. Albers, S., Antoniadis, A.: Race to idle: new algorithms for speed scaling with a sleep state. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1266–1285 (2012)

    Chapter  Google Scholar 

  4. Amur, H., Cipar, J., Gupta, V., Ganger, G.R., Kozuch, M.A., Schwan, K.: Robust and flexible power-proportional storage. In: Proceedings of the 1st ACM Symposium on Cloud Computing, pp. 217–228 (2010)

    Chapter  Google Scholar 

  5. Babenko, M., Gusakov, A., Razenshteyn, I.: Triangle-free 2-matchings revisited. In: Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120–129 (2010)

    Google Scholar 

  6. Baptiste, P.: Batching identical jobs. Math. Methods Oper. Res. 52(3), 355–367 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  7. Baptiste, P.: Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 364–367 (2006)

    Google Scholar 

  8. Baptiste, P., Chrobak, M., Dürr, C.: Polynomial time algorithms for minimum energy scheduling. In: Proceedings of the 15th Annual European Symposium on Algorithms, pp. 136–150 (2007)

    Google Scholar 

  9. Bar-Ilan, J., Kortsarz, G., Peleg, D.: How to allocate network centers. J. Algorithms 15(3), 385–415 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  10. Bodlaender, H.L., Fellows, M.R.: W[2]-hardness of precedence constrained k-processor scheduling. Oper. Res. Lett. 18(2), 93–97 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  11. Chang, J., Erlebach, T., Gailis, R., Khuller, S.: Broadcast scheduling: algorithms and complexity. ACM Trans. Algorithms 47, 1 (2011)

    Article  MathSciNet  Google Scholar 

  12. Charikar, M., Khuller, S.: A robust maximum completion time measure for scheduling. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 324–333 (2006)

    Google Scholar 

  13. Chudak, F., Williamson, D.: Improved approximation algorithms for capacitated facility location problems. In: Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization, pp. 99–113 (1999)

    Chapter  Google Scholar 

  14. Chuzhoy, J., Naor, J.: Covering problems with hard capacities. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 481–489 (2002)

    Google Scholar 

  15. Coffman, E.G. Jr., Garey, M.R.: Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling. J. ACM 40(5), 991–1018 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  16. Condotta, A., Knust, S., Shakhlevich, N.V.: Parallel batch scheduling of equal-length jobs with release and due dates. J. Sched. 13(5), 463–477 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  17. Cornuéjols, G., Pulleyblank, W.: A matching problem with side conditions. Discrete Math. 29(2), 135–159 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  18. Cornuéjols, G., Pulleyblank, W.: Perfect triangle-free 2-matchings. Math. Program. Stud. 13, 1–7 (1980)

    Article  MATH  Google Scholar 

  19. Demaine, E.D., Ghodsi, M., Hajiaghayi, M.T., Sayedi-Roshkhar, A.S., Zadimoghaddam, M.: Scheduling to minimize gaps and power consumption. In: Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 46–54 (2007)

    Google Scholar 

  20. Demaine, E.D., Zadimoghaddam, M.: Scheduling to minimize power consumption using submodular functions. In: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 21–29 (2010)

    Google Scholar 

  21. Erlebach, T., Hall, A.: Np-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 194–202 (2002)

    Google Scholar 

  22. Even, G., Levi, R., Rawitz, D., Schieber, B., Shahar, S.M., Sviridenko, M.: Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. ACM Trans. Algorithms 34, 1 (2008)

    Article  MathSciNet  Google Scholar 

  23. Even, S., Tarjan, R.: Network flow and testing graph connectivity. SIAM J. Comput. 4(4), 507–518 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  24. Flammini, M., Monaco, G., Moscardelli, L., Shachnai, H., Shalom, M., Tamir, T., Zaks, S.: Minimizing total busy time in parallel scheduling with application to optical networks. In: Proceedings of Interational Parallel Distributed Processing Symposium, pp. 1–12 (2009)

    Google Scholar 

  25. Frederickson, G.N.: Scheduling unit-time tasks with integer release times and deadlines. Inf. Process. Lett. 16(4), 171–173 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  26. Fujii, M., Kasami, T., Ninomiya, K.: Optimal sequencing of two equivalent processors. SIAM J. Appl. Math. 17(4), 784–789 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  27. Gabow, H.N.: An efficient implementation of Edmond’s’ algorithm for maximum matching on graphs. J. ACM 23(2), 221–234 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  28. Gabow, H.N.: An almost-linear algorithm for two-processor scheduling. J. ACM 29(3), 766–780 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  29. Gabow, H.N.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 448–456 (1983)

    Google Scholar 

  30. Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434–443 (1990)

    Google Scholar 

  31. Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209–221 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  32. Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815–853 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  33. Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., Srinivasan, A.: An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci. 72(1), 16–33 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  34. Garey, M., Johnson, D.S.: Two-processor scheduling with start-times and deadlines. SIAM J. Comput. 6(3), 416–426 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  35. Garey, M., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, New York (1979)

    Google Scholar 

  36. Garey, M.R., Johnson, D.S.: Scheduling tasks with nonuniform deadlines on two processors. J. ACM 23(3), 461–467 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  37. Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated vertex covering with applications. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 858–865 (2002)

    Google Scholar 

  38. Ikura, Y., Gimple, M.: Efficient scheduling algorithms for a single batch processing machine. Oper. Res. Lett. 5(2), 61–65 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  39. Irani, S., Pruhs, K.R.: Algorithmic problems in power management. SIGACT News 36(2), 63–76 (2005)

    Article  Google Scholar 

  40. Irani, S., Shukla, S., Gupta, R.: Algorithms for power savings. ACM Trans. Algorithms 3(4), 41 (2007)

    Article  MathSciNet  Google Scholar 

  41. Khandekar, R., Schieber, B., Shachnai, H., Tamir, T.: Minimizing busy time in multiple machine real-time scheduling. In: Proceedings of the Foundations of Software Technology and Theoretical Computer Science Conference, pp. 169–180 (2010)

    Google Scholar 

  42. Khuller, S., Sussmann, Y.: The capacitated k-center problem. SIAM J. Discrete Math. 13(3), 403–418 (2000)

    Article  MathSciNet  Google Scholar 

  43. Koehler, F., Khuller, S.: Optimal batch schedules for parallel machines. In: Proceedings of the 13th Annual Algorithms and Data Structures Symposium (2013)

    Google Scholar 

  44. Lawler, E.: Combinatorial Optimization. Holt, Rinehart & Winston, New York (1976)

    MATH  Google Scholar 

  45. Levi, R., Shmoys, D., Swamy, C.: Lp-based approximation algorithms for capacitated facility location. In: Proceedings of the 10th International Integer Programming and Combinatorial Optimization Conference, vol. 3064, pp. 206–218 (2004)

    Chapter  Google Scholar 

  46. Li, M., Yao, F.: An efficient algorithm for computing optimal discrete voltage schedules. SIAM J. Comput. 35(3), 658–671 (2005)

    Article  MathSciNet  Google Scholar 

  47. López-Ortiz, A., Quimper, C.-G.: A fast algorithm for multi-machine scheduling problems with jobs of equal processing times. In: Proceedings of Symposium on Theoretical Aspects of Computer Science, pp. 380–391 (2011)

    Google Scholar 

  48. Lovász, L., Plummer, M.: Matching Theory. North-Holland, Amsterdam (1986)

    MATH  Google Scholar 

  49. Micali, S., Vazirani, V.V.: An \(o(\sqrt{|V|} |e|)\) algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, pp. 17–27 (1980)

    Google Scholar 

  50. Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 248–255 (2004)

    Chapter  Google Scholar 

  51. Saha, B., Khuller, S.: Set cover revisited: hypergraph cover with hard capacities. In: Proceedings of the 39th International Conference on Automata, Languages and Programming, pp. 762–773 (2012)

    Chapter  Google Scholar 

  52. Simons, B.: Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. SIAM J. Comput. 12(2), 294–299 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  53. Simons, B., Warmuth, M.: A fast algorithm for multiprocessor scheduling of unit-length jobs. SIAM J. Comput. 18(4), 690–710 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  54. Winkler, P., Zhang, L.: Wavelength assignment and generalized interval graph coloring. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 830–831 (2003)

    Google Scholar 

  55. Wolsey, L.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385–393 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  56. Wu, H., Jaffar, J.: Two processor scheduling with real release times and deadlines. In: Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 127–132 (2002)

    Google Scholar 

  57. Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced cpu energy. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pp. 374–382 (1995)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science and Engineering, University of Washington, Seattle, WA, 98195, USA

    Jessica Chang

  2. University of Colorado, Boulder, CO, 80309, USA

    Harold N. Gabow

  3. Dept. of Computer Science, University of Maryland, College Park, MD, 20742, USA

    Samir Khuller

Authors
  1. Jessica Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Harold N. Gabow
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Samir Khuller
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jessica Chang.

Additional information

Research done while Jessica Chang was visiting the University of Maryland and was supported by an NSF Graduate Research Fellowship, NSF CCF-1016509, and NSF CCF-0937865.

Research of Samir Khuller supported by NSF CCF-0728839, NSF CCF-0937865 and a Google Research Award.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chang, J., Gabow, H.N. & Khuller, S. A Model for Minimizing Active Processor Time. Algorithmica 70, 368–405 (2014). https://doi.org/10.1007/s00453-013-9807-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-013-9807-y

Keywords

Search

Navigation