Logo PTI Logo FedCSIS

Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 43

The Power of Preemptions in Scheduling on Shareable Resources

,

DOI: http://dx.doi.org/10.15439/2025F6496

Citation: Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 43, pages 553–563 ()

Full text

Abstract. Many combinatorial optimization problems arise in the context of resource allocation. In this paper, we study the problem of allocating shareable resources of different types to jobs, where each job consists of multiple tasks, and each task has a demand of a given duration to a single resource type. All resources are available over a common time interval. Several copies from each resource may be allocated. In a valid solution, at any given time, each job may be processed by at most one resource, and each resource may process at most one job. The objective is to complete all jobs while minimizing the total cost of the allocated resources. We focus on the power of preemptions in this model, analyzing how much the total cost can be reduced when jobs are allowed to be preempted --- that is, when the processing of tasks can be split across multiple intervals. We present both theoretical and experimental results, distinguishing between environments where jobs may be preempted but all intervals of a task must be processes on the same resource copy (weak preemptions), and environments where jobs may split the processing of a task among different resource copies (strong preemptions). Without preemptions, the problem is clearly NP-hard, as it generalizes the classical Bin Packing problem. We provide an optimal polynomial-time algorithm for the strong-preemption model, as well as a polynomial-time algorithm for the non-preemption model under a restricted class of task durations. Our empirical evaluation investigates the performance of several greedy heuristics, showing that even simple methods can achieve near-optimal results.

References

  1. H. Bräsel, D. Kluge, and F. Werner, A polynomial algorithm for the [n/m/0, ti j = 1, tree/Cmax ] open shop problem, European Journal of Operational Research, 72(1):125–134, 1994.
  2. R. Canetti and S. Irani. Bounding the power of preemption in randomized scheduling. SIAM Journal on Computing, 27(4):993–1015, 1998.
  3. I. G. Drobouchevitch. Three-machine open shop with a bottleneck machine revisited. Journal of Scheduling, 24(2):197–208, 2021.
  4. T. Fiala. An algorithm for the open-shop problem. Mathematics of Operations Research, 8(1):100–109, 1983.
  5. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.
  6. T. Gonzalez and S. Sahni. Open shop scheduling to minimize finish time. J. ACM, 23(4):665–679, 1976.
  7. J.R.Correa, M.Skutella, and J.Verschae. The power of preemption on unrelated machines and applications to scheduling orders. Mathematics of Operations Research, 37(2):379–398, 2012.
  8. N. Karmakar and R. Karp. An efficient approximation scheme for the one-dimensional bin packing problem. In Proc. 23rd IEEE Symp. on Foundations of Computer Science, pages 312–320, 1982.
  9. A. Levin. Approximation schemes for the generalized extensible bin packing problem. Algorithmica, 84(2):325–343, 2022.
  10. C. Liu and R. Bulfin. Scheduling open shops with unit execution times to minimize functions of due dates. Operations Research, 36(4):553–559, 1988.
  11. R. McNaughton. Scheduling with deadlines and loss functions. Manage. Sci., 6:1–12, 1959.
  12. B. Naderi, M. Zandieh, and M. Yazdani. Polynomial time approximation algorithms for proportionate open-shop scheduling. International Transactions in Operational Research, 21(6):1031–1044, 2014.
  13. A. S. Schulz and M. Skutella. Scheduling unrelated machines by randomized rounding. SIAM Journal on Discrete Mathematics, 15(4):450–469, 2002.
  14. S. Sevastyanov and G. Woeginger. Makespan minimization in open shops: A polynomial time approximation scheme. Math. Program., 82:191–198, 1998.
  15. H. Shachnai and T. Tamir. Multiprocessor scheduling with machine allotment and parallelism constraints. Algorithmica, 32(4):651–678, 2002.
  16. B. Takand. Towards power of preemption on parallel machines. MPhil thesis, University of Greenwich, 2016.
  17. D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast’janov, and D. B. Shmoys. Short shop schedules. Operations Research, 45(2):288–294, 1997.
  18. R. Zhang, N. Horesh, E. Kontou, and Y, Zhou, Electric vehicle community charging hubs in multi-unit dwellings: Scheduling and techno-economic assessment, Transportation Research Part D: Transport and Environment, Vol. 120, 2023.