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

Scheduling with multiple servers

  • Multi-Machine and Multi-Stage Scheduling Environments
  • Published:
Automation and Remote Control Aims and scope Submit manuscript

Abstract

In this paper, we consider the problem of scheduling a set of jobs on a set of identical parallel machines. Before the processing of a job can start, a setup is required which has to be performed by a given set of servers. We consider the complexity of such problems for the minimization of the makespan. For the problem with equal processing times and equal setup times we give a polynomial algorithm. For the problem with unit setup times, m machines and m − 1 servers, we give a pseudopolynomial algorithm. However, the problem with fixed number of machines and servers in the case of minimizing maximum lateness is proven to be unary NP-hard. In addition, recent algorithms for some parallel machine scheduling problems with constant precessing times are generalized to the corresponding server problems for the case of constant setup times. Moreover, we perform a worst case analysis of two list scheduling algorithms for makespan minimization.

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. Hall, N.G., Potts, C.N., and Sriskandarajah, C., Parallel Machine Scheduling with a Common Server, Discret. Appl. Math., 2000, vol. 102, pp. 223–243.

    Article  MATH  MathSciNet  Google Scholar 

  2. Koulamas, C.P., Scheduling on Two Parallel Machines for Minimizing Machine Interference, Working Paper, 1993.

  3. Koulamas, C.P. and Smith, M.L., Look-ahead Scheduling for Minimizing Machine Interference, Int. J. Product. Res., 1988, vol. 26, pp. 1523–1533.

    Article  Google Scholar 

  4. Kravchenko, S.A. and Werner, F., Parallel Machine Scheduling Problems with a Single Server, Math. Comput. Model., 1997, vol. 26, pp. 1–11.

    Article  MATH  MathSciNet  Google Scholar 

  5. Brucker, P., Dhaenens-Flipo, C., Knust, S., Kravchenko, S.A., and Werner, F., Complexity Results for Parallel Machine Problems with a Single Server, J. Schedul., 2002, vol. 5, pp. 429–457.

    Article  MATH  MathSciNet  Google Scholar 

  6. Allahverdi, A., Ng, C.T., Cheng, T.C.E., and Kovalyov, M.Y., A Survey of Scheduling Problems with Setup Times or Costs, Eur. J. Oper. Res., 2008, vol. 187, pp. 985–1032.

    Article  MATH  MathSciNet  Google Scholar 

  7. Ou, J., Qi, X., and Lee, C.-Y., ParallelMachine Scheduling withMultiple Unloading Servers, J. Schedul., 2009, vol. 13, no. 3, pp. 213–226.

    Article  MathSciNet  Google Scholar 

  8. Huang, S., Cai, L., and Zhang, X., Parallel Dedicated Machine Scheduling Problem with Sequencedependent Setups and a Single Server, Comput. & Indust. Eng., 2010, vol. 58, no. 1, pp. 165–174.

    Google Scholar 

  9. Aronson, J.E., Two Heuristics for the Deterministic, Single Operator, Multiple Machine, Multiple Run Cyclic Scheduling Problem, J. Oper. Manage., 1984, vol. 4, pp. 159–773.

    Article  Google Scholar 

  10. Wilhelm, W.E. and Sarin, S.C., A Structure for Sequencing Robot Activities in Machine Loading Applications, Int. J. Product. Res., 1985, vol. 23, pp. 47–64.

    Article  Google Scholar 

  11. Hall, N.G., Kamoun, H., and Sriskandarajah, C., Scheduling in Robotic Cells: Classification, Two and Three Machine Cells, Oper. Res., 1997, vol. 45, pp. 421–439.

    Article  MATH  Google Scholar 

  12. Hall, N.G., Kamoun, H., and Sriskandarajah, C., Scheduling in Robotic Cells, Complexity and Sready State Analysis, Eur. J. Oper. Res., 1998, vol. 109, pp. 43–65.

    Article  MATH  Google Scholar 

  13. Kamoun, H., Hall, N.G., and Sriskandarajah, C., Scheduling in Robotic Cells: Heuristics and Cell Design, Oper. Res., 1999, vol. 47, pp. 821–835.

    Article  MATH  Google Scholar 

  14. Ganesharajah, T., Hall, N.G., and Sriskandarajah, C., Design and Operational Issues in AGV-served Manufacturing Systems, Ann. Oper. Res., 1998, vol. 76, pp. 109–154.

    Article  MATH  Google Scholar 

  15. Sethi, S.P., Sriskandarajah, C., Sorger, G., Blazewicz, J., and Kubiak, W., Sequencing of Parts and Robot Moves in a Robotic Cell, Int. J. Flexible Manufactur. Syst., 1992, vol. 4, pp. 331–358.

    Article  Google Scholar 

  16. Dobson, G. and Kamarkar, U.S., Simultaneous Resource Scheduling to Minimize Weighted Flow Time, Oper. Res., 1988, vol. 37, pp. 1523–1533.

    Google Scholar 

  17. Sahney, V.K., Single-server, Two-machine Sequencing with Switching Time, Oper. Res., 1972, vol. 20, pp. 24–26.

    Article  MATH  MathSciNet  Google Scholar 

  18. Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G., Optimization and Approximation in Deterministic Machine Scheduling: A Survey, Ann. Discret. Math., 1979, vol. 5, pp. 287–326.

    Article  MATH  MathSciNet  Google Scholar 

  19. Hall, N.G., Potts, C.N., and Sriskandarajah, C., Parallel Machine Scheduling with a Common Server, in The Fifth International Workshop on Project Management and Scheduling, Abstracts, 1997, pp. 102–106.

  20. Tanaev, V.S., Gordon, V.S., and Shafransky, Y.M., Scheduling Theory, Single-Stage Systems, Dordrecht: Kluwer, 1994.

    MATH  Google Scholar 

  21. Brucker, P. and Kravchenko, S.A., Scheduling Jobs with Equal Processing Times and Time Windows on Identical Parallel Machines, J. Schedul., 2008, vol. 11, pp. 229–237.

    Article  MATH  MathSciNet  Google Scholar 

  22. Kravchenko, S.A. and Werner, F., On a Parallel Machine Scheduling Problem with Equal Processing Times, Discret. Appl. Math., 2009, vol. 157, pp. 848–852.

    Article  MATH  MathSciNet  Google Scholar 

  23. Kravchenko, S.A. and Werner, F., On a Parallel Machine Scheduling Problem with Equal Processing Times, Preprint of Otto-von-Guericke-Universität, Magdeburg, 2007, no. 26/07.

Download references

Author information

Authors and Affiliations

  1. Otto-von-Guericke-Universität, Magdeburg, Germany

    F. Werner

  2. United Institute of Informatics Problems, Belarussian National Academy of Sciences, Minsk, Belarus

    S. A. Kravchenko

Authors
  1. F. Werner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. A. Kravchenko
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Original Russian Text © F. Werner, S.A. Kravchenko, 2010, published in Avtomatika i Telemekhanika, 2010, No. 10, pp. 107–121.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Werner, F., Kravchenko, S.A. Scheduling with multiple servers. Autom Remote Control 71, 2109–2121 (2010). https://doi.org/10.1134/S0005117910100103

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0005117910100103

Keywords

Search

Navigation