Abstract
We study the dynamic scheduling problem for jobs with fixed start and end times on multiple machines. The problem is to maintain an optimal schedule under the update operations: insertions and deletions of jobs. Call the period of time in a schedule between two consecutive jobs in a given machine an idle interval. We show that for any set of jobs there exists a schedule such that the corresponding set of idle intervals forms a tree under the set-theoretic inclusion. Based on this result, we provide a data structure that updates the optimal schedule in \(O(d+\log n)\) worst-case time, where \(d\) is the depth of the set idle intervals and \(n\) is the number of jobs. Furthermore, we show this bound to be tight for any data structure that maintains a nested schedule.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arkin, E.M., Silverberg, E.B.: Scheduling jobs with fixed start and end times. Discrete Applied Mathematics 18(1), 1–8 (1987)
Diedrich, F., Jansen, K., Pradel, L., Schwarz, U.M., Svensson, O.: Tight approximation algorithms for scheduling with fixed jobs and nonavailability. ACM Transactions on Algorithms (TALG) 8(3), 27 (2012)
Gavruskin, A., Khoussainov, B., Kokho, M., Liu, J.: Dynamising Interval Scheduling: The Monotonic Case. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol. 8288, pp. 178–191. Springer, Heidelberg (2013)
Gertsbakh, I., Stern, H.I.: Minimal resources for fixed and variable job schedules. Operations Research 26(1), 68–85 (1978)
Gupta, U.I., Lee, D.T., Leung, J.T.: An optimal solution for the channel-assignment problem. IEEE Transactions on Computers 100(11), 807–810 (1979)
Kaplan, H., Molad, E., Tarjan, R.E.: Dynamic rectangular intersection with priorities. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 639–648. ACM (2003)
Kleinberg, J., Tardos, E.: Algorithm design. Pearson Education India (2006)
Kolen, A.W., Kroon, L.G.: On the computational complexity of (maximum) class scheduling. European Journal of Operational Research 54(1), 23–38 (1991)
Kolen, A.W., Kroon, L.G.: An analysis of shift class design problems. European Journal of Operational Research 79(3), 417–430 (1994)
Kolen, A.W., Lenstra, J.K., Papadimitriou, C.H., Spieksma, F.C.: Interval scheduling: A survey. Naval Research Logistics (NRL) 54(5), 530–543 (2007)
Kovalyov, M.Y., Ng, C.T., Cheng, T.C.: Fixed interval scheduling: Models, applications, computational complexity and algorithms. European Journal of Operational Research 178(2), 331–342 (2007)
Kroon, L.G., Salomon, M., Van Wassenhove, L.N.: Exact and approximation algorithms for the operational fixed interval scheduling problem. European Journal of Operational Research 82(1), 190–205 (1995)
Kroon, L.G., Salomon, M., Van Wassenhove, L.N.: Exact and approximation algorithms for the tactical fixed interval scheduling problem. Operations Research 45(4), 624–638 (1997)
Mehlhorn, K.: Data structures and algorithms. Multi-dimensional Searching and Computational Geometry, vol. 3. Springer, Berlin (1984)
Shamos, M.I., Hoey, D.: Geometric intersection problems. In: 17th Annual Symposium on Foundations of Computer Science, pp. 208–215. IEEE (1976)
Sleator, D., Tarjan, R.: A Data Structure for Dynamic Trees. Journal of Computer and System Sciences 26(3), 362–391 (1983)
Spieksma, F.C.: On the approximability of an interval scheduling problem. Journal of Scheduling 2(5), 215–227 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Gavruskin, A., Khoussainov, B., Kokho, M., Liu, J. (2014). Dynamic Interval Scheduling for Multiple Machines. In: Ahn, HK., Shin, CS. (eds) Algorithms and Computation. ISAAC 2014. Lecture Notes in Computer Science(), vol 8889. Springer, Cham. https://doi.org/10.1007/978-3-319-13075-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-13075-0_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13074-3
Online ISBN: 978-3-319-13075-0
eBook Packages: Computer ScienceComputer Science (R0)