Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Heuristics for Job Scheduling Reoptimization

,

DOI: http://dx.doi.org/10.15439/2016F201

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 561–570 ()

Full text

Abstract. Many real-life applications involve systems that change dynamically over time. Thus, throughout the continuous operation of such a system, it is required to compute solutions for new problem instances, derived from previous instances. Since the transition from one solution to another incurs some cost, a natural goal is to have the solution for the new instance close to the original one (under a certain distance measure). We study reoptimization problems arising in scheduling systems. Formally, due to changes in the environment (out-of-order or new machines, modified jobs' processing requirements, etc.), the schedule needs to be modified. That is, jobs might be migrated from their current machine to a different one. Migrations are associated with a cost -- due to relocation overhead and machine set-up times. In some systems, a migration is also associated with job extension. The goal is to find a good modified schedule, with a low transition cost from the initial one.

References

  1. G. Ausiello, B. Escoffier, J. Monnot, and V. Th. Paschos. Reoptimization of minimum and maximum traveling salesmans tours. J. of Discrete Algorithms 7(4):453–463, 2009.
  2. G. Baram and T. Tamir, Reoptimization of the Minimum Total Flow-Time Scheduling Problem. Sustainable Computing, Informatics and Systems. vol. 4(4):241–251, 2014.
  3. J. Berlinskaa and M. Drozdowskib. Scheduling divisible MapReduce computations. In Journal of Parallel and Distributed Computing. vol.71(3):450-459, 2011.
  4. A. D. Birrell and B. J. Nelson. Implementing remote procedure calls. ACM Transactions on Computer Systems 2:39–59 ,1984.
  5. H. J. Bockenhauer, L. Forlizzi, J. Hromkovic, J. Kneis, J. Kupke, G. Proietti, and P. Widmayer. On the approximability of TSP on local modifications of optimally solved instances. Algorithmic Operations Research 2(2), 2007.
  6. J. L. Bruno, E.G Coffman, and R. Sethi. Scheduling independent tasks to reduce mean finishing time. Communications of the ACM, 17:382–387, 1974.
  7. C. Clark, K. Fraser, S.Hand, J.G. Hansen, E. Jul, C. Limpach, I. Pratt, A. Warfield. Live migration of virtual machines. The 2nd Symp. on Networked Systems Design and Implementation (NSDI). 2005.
  8. R. W. Conway, W. L. Maxwell, and L. W. Miller. Theory of Scheduling. AddisonWesley, 1967.
  9. A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer, 2007
  10. D. Eppstein, Z. Galil, and G.F. Italiano. Dynamic graph algorithms, Chapter 8. In CRC Handbook of Algorithms and Theory of Computation, ed. M. J. Atallah, 1999.
  11. B. Escoffier, M. Milanic, and V.Th. Paschos. Simple and fast reoptimizations for the Steiner tree problem. DIMACS Technical Report 2007-01.
  12. M. R. Garey and D.S. Johnson. Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman and Co., New York, 1979.
  13. R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math. vol. 5:287–326, 1979.
  14. S. Hacking and B. Hudzia. Improving the live migration process of large enterprise applications. The 3rd international workshop on Virtualization technologies in distributed computing (VTDC), 2009.
  15. D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for scheduling problems: Practical and theoretical results. Journal of the ACM, 34(1):144–162, 1987.
  16. W. Horn. Minimizing average flow-time with parallel machines. Operations Research, 21:846–847, 1973.
  17. Harold W. Kuhn. The Hungarian Method for the assignment problem, Naval Research Logistics Quarterly, vol. 2: 83–97, 1955.
  18. Parallels Virtuozzo http://www.parallels.com/products/pvc.
  19. L. M. Schmitt. Theory of Genetic Algorithms, Theoretical Computer Science vol. 259:1-61, 2001.
  20. H. Shachnai, G. Tamir, and T. Tamir, Minimal cost reconfiguration of data placement in storage area network. Theoretical Computer Science. vol. 460:42–53, 2012.
  21. H. Shachnai, G. Tamir, and T. Tamir. A theory and algorithms for combinatorial reoptimization. In Proc. of 10th LATIN, 2012.
  22. W.E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly. vol. 3:59–66, 1956.
  23. M. Thorup, and D.R. Karger. Dynamic graph algorithms with applications. In Proc. of 7th SWAT, 2000.
  24. Xen Project, http://www.xenproject.org/.