Skip to main content

2021 | OriginalPaper | Buchkapitel

A New Integer Programming Model for the File Transfer Scheduling Problem

verfasst von : Jingwen Yang, Jiaxin Li, Xin Han

Erschienen in: Parallel and Distributed Computing, Applications and Technologies

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Scheduling the transfer of files in distributed computer systems is an increasing concern. The purpose of this paper is to propose a new time-index integer programming model for the file transfer scheduling problem with integer file length and port restrictions, which is to design a schedule to transfer series of files with different file length while minimizing overall completion time. By different formulations of variables and constraints, our new model contains fewer constraints and variables. And we also propose an enhanced technique to reduce the number of constraints further by utilizing the elementary lower bound and upper bound. Experimental results show that compared to existing best model, our model with the enhanced technique can solve the same instance with only 14.3% of the time. Moreover, our model can solve larger instances (up to 100 vertices and 600 files) to optimality that can not be solved by existing models.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Akbari, M.K., Nezhad, M., Kalantari, M.: A neural network realization of file transfer scheduling. CSI J. Comput. Sci. Eng. 2, 19–29 (2004) Akbari, M.K., Nezhad, M., Kalantari, M.: A neural network realization of file transfer scheduling. CSI J. Comput. Sci. Eng. 2, 19–29 (2004)
2.
Zurück zum Zitat Coffman Jr., E.G., Garey, M.R., Johnson, D.S., LaPaugh, A.S.: Scheduling file transfers. SIAM J. Comput. 14(3), 744–780 (1985)MathSciNetCrossRef Coffman Jr., E.G., Garey, M.R., Johnson, D.S., LaPaugh, A.S.: Scheduling file transfers. SIAM J. Comput. 14(3), 744–780 (1985)MathSciNetCrossRef
3.
Zurück zum Zitat Dražić, Z.: Variable neighborhood search for the file transfer scheduling problem. Serdica J. Comput. 6(3), 333–348 (2012)MathSciNet Dražić, Z.: Variable neighborhood search for the file transfer scheduling problem. Serdica J. Comput. 6(3), 333–348 (2012)MathSciNet
4.
Zurück zum Zitat Dražić, Z.: Modifications of the variable neighborhood search method and their applications to solving the file transfer scheduling problem. Ph.D. thesis, University of Belgrade, Faculty of Mathematics (2014) Dražić, Z.: Modifications of the variable neighborhood search method and their applications to solving the file transfer scheduling problem. Ph.D. thesis, University of Belgrade, Faculty of Mathematics (2014)
5.
Zurück zum Zitat Dražić, Z.: Gaussian variable neighborhood search for the file transfer scheduling problem. Yugoslav J. Oper. Res. 26(2), 173–188 (2016)MathSciNetCrossRef Dražić, Z.: Gaussian variable neighborhood search for the file transfer scheduling problem. Yugoslav J. Oper. Res. 26(2), 173–188 (2016)MathSciNetCrossRef
6.
Zurück zum Zitat Dražić, Z., Savić, A., Filipović, V.: An integer linear formulation for the file transfer scheduling problem. TOP 22(3), 1062–1073 (2014)MathSciNetCrossRef Dražić, Z., Savić, A., Filipović, V.: An integer linear formulation for the file transfer scheduling problem. TOP 22(3), 1062–1073 (2014)MathSciNetCrossRef
7.
Zurück zum Zitat Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130(3), 449–467 (2001)MathSciNetCrossRef Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130(3), 449–467 (2001)MathSciNetCrossRef
8.
Zurück zum Zitat Higuero, D., Tirado, J.M., Isaila, F., Carretero, J.: Enhancing file transfer scheduling and server utilization in data distribution infrastructures. In: 2012 IEEE 20th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 431–438. IEEE (2012) Higuero, D., Tirado, J.M., Isaila, F., Carretero, J.: Enhancing file transfer scheduling and server utilization in data distribution infrastructures. In: 2012 IEEE 20th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp. 431–438. IEEE (2012)
9.
Zurück zum Zitat Jia, S., Jin, X., Ghasemiesfeh, G., Ding, J., Gao, J.: Competitive analysis for online scheduling in software-defined optical wan. In: IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pp. 1–9 (2017) Jia, S., Jin, X., Ghasemiesfeh, G., Ding, J., Gao, J.: Competitive analysis for online scheduling in software-defined optical wan. In: IEEE INFOCOM 2017 - IEEE Conference on Computer Communications, pp. 1–9 (2017)
10.
Zurück zum Zitat Mao, W.: Directed file transfer scheduling. In: ACM 31st Annual Southeast Conference (ACM-SE 1993), pp. 199–203 (1993) Mao, W.: Directed file transfer scheduling. In: ACM 31st Annual Southeast Conference (ACM-SE 1993), pp. 199–203 (1993)
11.
12.
Zurück zum Zitat Sousa, J.P., Wolsey, L.A.: A time indexed formulation of non-preemptive single machine scheduling problems. Math. Program. 54, 353–367 (1992)CrossRef Sousa, J.P., Wolsey, L.A.: A time indexed formulation of non-preemptive single machine scheduling problems. Math. Program. 54, 353–367 (1992)CrossRef
13.
Zurück zum Zitat Whitehead, J.: The complexity of file transfer scheduling with forwarding. SIAM J. Comput. 19(2), 222–245 (1990)MathSciNetCrossRef Whitehead, J.: The complexity of file transfer scheduling with forwarding. SIAM J. Comput. 19(2), 222–245 (1990)MathSciNetCrossRef
Metadaten
Titel
A New Integer Programming Model for the File Transfer Scheduling Problem
verfasst von
Jingwen Yang
Jiaxin Li
Xin Han
Copyright-Jahr
2021
DOI
https://doi.org/10.1007/978-3-030-69244-5_22