[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, New Jersey (1993)

    Google Scholar 

  2. Ahuja, R.K., Orlin, J.B., Stein, C., Tarjan, R.E.: Improved algorithms for bipartite network flow. SIAM J. Comput. 23, 906–933 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  3. Błažewicz, J., Finke, G.: Minimizing mean weighted execution time loss on identical and uniform processors. Inf. Process. Lett. 24, 259–263 (1987)

    Article  MATH  Google Scholar 

  4. Błažewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., Weglarz, J.: Scheduling Computer and Manufacturing Processes. Springer, Berlin (2001)

    MATH  Google Scholar 

  5. Brucker, P.: Scheduling Algorithms, 4th edn. Springer, Berlin (2004)

    MATH  Google Scholar 

  6. Frank, A., Tardos, E.: Generalized polymatroids and submodular flows. Math. Program. 42, 489–563 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  7. Federgruen, A., Groenvelt, H.: Preemptive scheduling of uniform machines by ordinary network flow techniques. Manag. Sci. 32, 341–349 (1986)

    Article  MATH  Google Scholar 

  8. Gonzalez, T.F., Sahni, S.: Preemptive scheduling of uniform processor systems. J. ACM 25, 92–101 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  9. Jansen, K., Mastrolilli, M.: Approximation schemes for parallel machine scheduling problems with controllable processing times. Comput. Oper. Res. 31, 1565–1581 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  10. Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank, H.R. (ed.) Progress in Combinatorial Optimization, pp. 245–261. Academic, New York

  11. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Handbooks in Operations Research and Management Science, vol. 4, Logistics of Production and Inventory, pp. 445–522. North-Holland, Amsterdam (1993)

    Google Scholar 

  12. Leung, J.Y.-T.: Minimizing total weighted error for imprecise computation tasks. In: Leung, J.Y.-T. (ed.) Handbook of Scheduling: Algorithms, Models and Performance Analysis. Computer and Information Science Series, pp. 34-1–34-16. Chapman & Hall/CRC, London (2004)

    Google Scholar 

  13. Leung, J.Y.-T., Yu, V.K.M., Wei, W.-D.: Minimizing the weighted number of tardy task units. Discrete Appl. Math. 51, 307–316 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  14. Martel, C.: Preemptive scheduling with release times, deadlines, and due dates. J. ACM 29, 812–829 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  15. Mastrolilli, M.: Notes on max flow time minimization with controllable processing times. Computing 71, 375–386 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  16. Nowicki, E., Zdrzalka, S.: A survey of results for sequencing problems with controllable processing times. Discrete Appl. Math. 26, 271–287 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  17. Nowicki, E., Zdrzalka, S.: A bicriterion approach to preemptive scheduling of parallel machines with controllable job processing times. Discrete Appl. Math. 63, 271–287 (1995)

    Article  MathSciNet  Google Scholar 

  18. Sahni, S., Cho, Y.: Scheduling independent tasks with due times on a uniform processor system. J. ACM 27, 550–563 (1980)

    Article  MathSciNet  Google Scholar 

  19. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York (2003)

    MATH  Google Scholar 

  20. Shakhlevich, N.V., Strusevich, V.A.: Preemptive scheduling problems with controllable processing times. J. Sched. 8, 233–253 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  21. Shih, W.-K., Liu, J.W.S., Chung, J.-Y.: Fast algorithms for scheduling imprecise computations. In: Proceedings of the 10th Real-time Systems Symposium, Santa-Monica, pp. 12–19 (1989)

  22. Shih, W.-K., Liu, J.W.S., Chung, J.-Y.: Algorithms for scheduling imprecise computations with timing constraints. SIAM J. Comput. 20, 537–552 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  23. T’kindt, V., Billaut, J.-C.: Multicriteria Scheduling: Theory, Models and Algorithms. Springer, Berlin (2002)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing, University of Leeds, Leeds, LS2 9JT, UK

    Natalia V. Shakhlevich

  2. Department of Mathematical Sciences, University of Greenwich, Old Royal Naval College, Park Row, London, SE10 9LS, UK

    Vitaly A. Strusevich

Authors
  1. Natalia V. Shakhlevich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vitaly A. Strusevich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Natalia V. Shakhlevich.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shakhlevich, N.V., Strusevich, V.A. Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times. Algorithmica 51, 451–473 (2008). https://doi.org/10.1007/s00453-007-9091-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9091-9

Keywords

Search

Navigation