Skip to main content
SpringerLink
Log in

Uniform parallel machine scheduling problems with fixed machine cost

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper considers two uniform parallel machine scheduling problems with fixed machine cost under the background of cloud manufacturing. The goal is to minimize the makespan with a given budget of total cost, \(\hat{U}\). All the jobs are homogeneous, i.e., the processing times of the jobs are identical. Non-preemptive and preemptive problems are studied. For the non-preemptive problem, we give a \(2[1+1{/}(h-1)]\)-approximation algorithm, where h is the number of the machine which can not be selected the first time. For the preemptive problem, we give an algorithm whose worst-case bound equals to \(1+1{/}(h-1)\). Preliminary experimental results indicate that the proposed algorithms are reasonably accurate compared with the lower bounds.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Alidaee, B.: A aeuristic solution procedure to minimize makespan on a single machine with non-linear cost functions. J. Oper. Res. Soc. 41(11), 1065–1068 (1990)

    Article  MATH  Google Scholar 

  2. Cao, D., Chen, M., Wan, G.: Parallel machine selection and job scheduling to minimize machine cost and job tardiness. Comput. Oper. Res. 32, 1995–2012 (2005)

    Article  MATH  Google Scholar 

  3. Dosa, G., He, Y.: Scheduling with machine cost and rejection. J. Comb. Optim. 12(4), 337–350 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Dosa, G., Tan, Z.: New upper and lower bounds for online scheduling with machine cost. Discr. Optim. 7, 125–135 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Edward, C.H., Shui, L., Ravi, S.: A level algorithm for preemptive scheduling. J. ACM 24, 32–43 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  6. He, Y., Cai, S.-Y.: Semi-online scheduling with machine cost. J. Comput. Sci. Technol. 17(6), 781–787 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  7. Huang, B., Li, C., Yin, C., Zhao, C.: Cloud manufacturing service platform for small- and medium-sized enterprises. Int. J. Adv. Manuf. Technol. 65, 1261–1272 (2013)

    Article  Google Scholar 

  8. Imreh, C., Noga, J.: Scheduling with machine cost. In: RANDOM-APPROX’99, Lecture Notes in Computer Science, 1671, pp 168–176

  9. Imreh, C.: Online scheduling with general machine cost functions. Discr. Appl. Math. 157, 2070–2077 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Jiang, Y., He, Y.: Semi-online algorithms for scheduling with machine cost. J. Comput. Sci. Technol. 21(6), 984–988 (2006)

    Article  MathSciNet  Google Scholar 

  11. Jiang, Y., He, Y.: Preemptive online algorithms for scheduling with machine cost. Acta Inf. 41, 315–340 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Laili, Y., Tao, F., Zhang, L., Bhaba, R.: A study of optimal allocation of computing resources in cloud manufacturing systems. Int. J. Adv. Manuf. Technol. 63, 671–690 (2012)

    Article  Google Scholar 

  13. Lee, C.Y., Vairaktarakis, G.L.: Comlpexity of single machine hierarchical scheduling: a Survey. In: Pardalos, P.M. (ed.) Complexity in Numerical Optimization, pp. 269–298. World Scientific Publishing Co.Pte.Ltd, Farrer Road Singapore (1993)

    Chapter  Google Scholar 

  14. Leung, J.Y.-T., Lee, K., Pinedo, M.L.: Bi-criteria scheduling with machine assignment costs. Int. J. Prod. Econ. 139, 321–329 (2012)

    Article  Google Scholar 

  15. Li, K., Zhang, X., Leung, J.Y.-T.: Parallel machine scheduling problems in green manufacturing Industry. J. Manuf. Syst. 38, 98–106 (2016)

    Article  Google Scholar 

  16. Li, W.H.: Single machine scheduling problem with release dates and two hierarchical criteria to minimize makespan and stocking cost. Chin. Q. J. Math. 21(1), 103–109 (2006)

    MathSciNet  Google Scholar 

  17. Linn, R.J., Yen, B., Zhang, W.: Just-in-time scheduling with machining economics for single-machine turning process. J. Manuf. Syst. 19(4), 219–228 (2000)

    Article  Google Scholar 

  18. Liu, F., Wang, J., Yang, D.-L.: Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics. J. Manuf. Syst. 32, 715–723 (2013)

    Article  Google Scholar 

  19. Macia-Perez, F., Berna-Martinez, J.V., Marcos-Jorquera, D., Lorenzo-Fonseca, I., Ferrandiz-Colmeiro, A.: Cloud agile manufacturing. Int. Org. Sci. Res. J. Eng. 2(5), 1045–1048 (2012)

    Google Scholar 

  20. Nagy-Gyorgy, J., Imreh, C.: Online scheduling with machine cost and rejection. Discr. Appl. Math. 155, 2546–2554 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  21. Pei, J., Liu, X.B., Pardalos, P.M., Fan, W.J., Yang, S.L.: Single machine serial-batching scheduling with independent setup time and deteriorating job processing times. Optim. Lett. 9(1), 91–104 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  22. Rauschecker, U., Meier, M., Muckenhirn, R., Arthur, Y.I.P., Jagadeesan, A., Corney, J.: Cloud-based manufacturing-as-a-service environment for customized Products. Int. Inf. Manag. Corp. ISBN: 978-1-905824-27-4 (2011)

  23. Rustogi, K., Strusevich, V.A.: Parallel machine scheduling: impact of adding extra machines. Oper. Res. 61(5), 1243–1257 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  24. Seiden, S.: A guessing game and randomized online algorithms. In: Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, ACM, New York, pp. 592–601 (2000)

  25. Zhang, L., Luo, Y., Tao, F., Li, B.H., Ren, L., Zhang, X., Guo, H., Cheng, Y., Hu, A., Liu, Y.: Cloud manufacturing:a new manufacturing paradigm. Enterp. Inf. Syst. 8(2), 167–187 (2014)

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by the fund from National Natural Science Foundation of China under Grant Nos. 71471052, 71521001, and 71531008. P.M. Pardalos was partially supported by a project of Distinguished International Professor by the Chinese Ministry of Education under Grant MS2014HFGY026.

Author information

Authors and Affiliations

  1. School of Management, Hefei University of Technology, Hefei, China

    Kai Li, Hui-Juan Zhang & Ba-Yi Cheng

  2. Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education, Hefei, China

    Kai Li & Ba-Yi Cheng

  3. Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Gainesville, USA

    Panos M. Pardalos

Authors
  1. Kai Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hui-Juan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ba-Yi Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hui-Juan Zhang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, K., Zhang, HJ., Cheng, BY. et al. Uniform parallel machine scheduling problems with fixed machine cost. Optim Lett 12, 73–86 (2018). https://doi.org/10.1007/s11590-016-1096-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-016-1096-3

Keywords

Search

Navigation