Abstract
In this paper, we propose a new integer linear programming (ILP) formulation for solving a file transfer scheduling problem (FTSP), which is to minimize the overall time needed to transfer all files to their destinations for a given collection of various sized files in a computer network. Each computer in this network has a limited number of communication ports. The described problem is proved to be NP-hard in a general case. Our formulation enables solving the problem by standard ILP solvers like CPLEX or Gurobi. To prove the validity of the proposed ILP formulation, two new reformulations of FTSP are presented. The results obtained by CPLEX and Gurobi solvers, based on this formulation, are presented and discussed.
Similar content being viewed by others
References
Akbari MK, Nezhad MH, Kalantari M (2004) Neural network realization of file transfer scheduling. CSI J Comput Sci Eng 2(2, 4):19–29
Coffman EG, Garey MR, Johnson DS, Lapaugh AS (1985) Scheduling file transfers. SIAM J Comput 14(3):744–765
CPLEX solver (2013) IBM-ILOG company. http://www.ibm.com
Dražić Z (2012) Variable neighbohood search for the file transfer scheduling problem. Serdica J Comput 3(6):333–348
Gouveia L, Moura P (2012) Enhancing discretized formulations: the knapsack reformulation and the star reformulation. Top 20(1):52–74
Gurobi Optimization (2012) Gurobi optimizer reference manual. http://www.gurobi.com
Havill JT, Mao W (1997) Greedy on-line file transfer routing. In: Proceedings of IASTED international conference on parallel and distributed systems, pp 225–230
Higuero D, Tirado JM, Isaila F, Carretero J (2012) Enhancing file transfer scheduling and server utilization in data distribution infrastructures. In: Proceedings of IEEE 20th international symposium on modeling, analysis and simulation of computer and telecommunication systems (MASCOTS), pp 431–438
Mao W (1993) Directed file transfer scheduling. In: Proceedings of the ACM 31st annual southeast conference, pp 199–203
Nakano S, Zhou X, Nishizeki T (1995) Edge-coloring algorithms. Computer Science Today, pp 172–183
Sherali HD, Smith JC (2012) Dynamic Lagrangian dual and reduced RLT constructs for solving 01 mixed-integer programs. Top 20(1):173–189
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by Serbian Ministry of Education and Science under the grant no. 174010.
Rights and permissions
About this article
Cite this article
Dražić, Z., Savić, A. & Filipović, V. An integer linear formulation for the file transfer scheduling problem. TOP 22, 1062–1073 (2014). https://doi.org/10.1007/s11750-013-0312-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-013-0312-x