Heuristics for Job Scheduling Reoptimization
Elad Iwanir, Tami Tamir
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 (2016)
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.
- 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.
- 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.
- J. Berlinskaa and M. Drozdowskib. Scheduling divisible MapReduce computations. In Journal of Parallel and Distributed Computing. vol.71(3):450-459, 2011.
- A. D. Birrell and B. J. Nelson. Implementing remote procedure calls. ACM Transactions on Computer Systems 2:39–59 ,1984.
- 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.
- 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.
- 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.
- R. W. Conway, W. L. Maxwell, and L. W. Miller. Theory of Scheduling. AddisonWesley, 1967.
- A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer, 2007
- 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.
- B. Escoffier, M. Milanic, and V.Th. Paschos. Simple and fast reoptimizations for the Steiner tree problem. DIMACS Technical Report 2007-01.
- 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.
- 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.
- 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.
- 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.
- W. Horn. Minimizing average flow-time with parallel machines. Operations Research, 21:846–847, 1973.
- Harold W. Kuhn. The Hungarian Method for the assignment problem, Naval Research Logistics Quarterly, vol. 2: 83–97, 1955.
- Parallels Virtuozzo http://www.parallels.com/products/pvc.
- L. M. Schmitt. Theory of Genetic Algorithms, Theoretical Computer Science vol. 259:1-61, 2001.
- 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.
- H. Shachnai, G. Tamir, and T. Tamir. A theory and algorithms for combinatorial reoptimization. In Proc. of 10th LATIN, 2012.
- W.E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly. vol. 3:59–66, 1956.
- M. Thorup, and D.R. Karger. Dynamic graph algorithms with applications. In Proc. of 7th SWAT, 2000.
- Xen Project, http://www.xenproject.org/.