×

Scheduling shared continuous resources on many-cores. (English) Zbl 1406.90033

Summary: We consider the problem of scheduling a number of jobs on \(m\) identical processors sharing a continuously divisible resource. Each job \(j\) comes with a resource requirement \(r \in [0,1]\). The job can be processed at full speed if granted its full resource requirement. If receiving only an \(x\)-portion of \(r_j\), it is processed at an \(x\)-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this article, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include a polynomial-time algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a \((2-1/m)\)-approximation algorithm for \(m\) processors.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Błażewicz, J., Ecker, K. H., & Pesch, E. (2007). Handbook on scheduling: From theory to applications. Berlin: Springer. · Zbl 1165.90009
[2] Błażewicz, J., Ecker, K. H., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling—From theory to applications. International handbooks on information systems. Berlin: Springer. · Zbl 1165.90009
[3] Chung, F; Graham, R; Mao, J; Varghese, G, Parallelism versus memory allocation in pipelined router forwarding engines, Theory of Computing Systems, 39, 829-849, (2006) · Zbl 1113.68036 · doi:10.1007/s00224-006-1249-3
[4] Epstein, L; Levin, A; Stee, R, Approximation schemes for packing splittable items with cardinality constraints, Algorithmica, 62, 102-129, (2012) · Zbl 1236.90067 · doi:10.1007/s00453-010-9445-6
[5] Epstein, L; Stee, R, Improved results for a memory allocation problem, Theory of Computing Systems, 48, 79-92, (2011) · Zbl 1209.68006 · doi:10.1007/s00224-009-9226-2
[6] Janiak, A; Janiak, W; Lichtenstein, M, Resource management in machine scheduling problems: A survey, Decision Making in Manufacturing and Services, 1, 59-89, (2007) · Zbl 1231.90199
[7] Józefowska, J; Mika, M; Różycki, R; Waligóra, G; Weglarz, J, Discrete-continuous scheduling to minimize the makespan for power processing rates of jobs, Discrete Applied Mathematics, 94, 263-285, (1999) · Zbl 0940.90034 · doi:10.1016/S0166-218X(99)00025-6
[8] Józefowska, J; Mika, M; Różycki, R; Waligóra, G; Weglarz, J, Solving the discrete-continuous project scheduling problem via its discretization, Mathematical Methods of Operations Research, 52, 489-499, (2000) · Zbl 1023.90027 · doi:10.1007/s001860000094
[9] Józefowska, J; Mika, M; Różycki, R; Waligóra, G; Weglarz, J, A heuristic approach to allocating the continuous resource in discrete-continuous scheduling problems to minimize the makespan, Journal of Scheduling, 5, 487-499, (2002) · Zbl 1029.90030 · doi:10.1002/jos.119
[10] Józefowska, J; Weglarz, J, Discrete-continuous scheduling problems—mean completion time results, European Journal of Operational Research, 94, 302-309, (1996) · Zbl 0953.90521 · doi:10.1016/0377-2217(96)00130-0
[11] Józefowska, J; Weglarz, J, On a methodology for discrete-continuous scheduling, European Journal of Operational Research, 107, 338-353, (1998) · Zbl 0943.90033 · doi:10.1016/S0377-2217(97)00346-9
[12] Kis, T, A branch-and-cut algorithm for scheduling of projects with variable-intensity activities, Mathematical Programming, 103, 515-539, (2005) · Zbl 1125.90019 · doi:10.1007/s10107-004-0551-6
[13] Leung, J. Y. T. (2004). Handbook of scheduling: Algorithms, models, and performance analysis. London: Chapman & Hall. · Zbl 1103.90002
[14] Różycki, R., Weglarz, J. (2011). Power-aware acheduling of preemptable jobs on identical parallel processors to minimize makespan. Annals of Operations Research. doi:10.1007/s10479-011-0957-5
[15] Różycki, R; Weglarz, J, Power-aware scheduling of preemptable jobs on identical parallel processors to meet deadlines, European Journal of Operational Research, 218, 68-75, (2012) · Zbl 1244.90101 · doi:10.1016/j.ejor.2011.10.017
[16] Waligóra, G, Heuristic approaches to discrete-continuous project scheduling problems to minimize the makespan, Computational Optimization and Applications, 48, 399-421, (2011) · Zbl 1219.90070 · doi:10.1007/s10589-010-9343-5
[17] Weglarz, J; Józefowska, J; Mika, M; Waligóra, G, Project scheduling with finite or infinite number of activity processing modes—A survey, European Journal of Operational Research, 208, 177-205, (2011) · Zbl 1208.90082 · doi:10.1016/j.ejor.2010.03.037
[18] Yao, F.F., Demers, A.J., Shenker, S. (1995). A scheduling model for reduced CPU energy. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 374-382. · Zbl 0938.68533
[19] Zhuravlev, S; Saez, JC; Blagodurov, S; Fedorova, A; Prieto, M, Survey of scheduling techniques for addressing shared resources in multicore processors, ACM Computing Surveys (CSUR), 45, 4:1-4:28, (2012) · Zbl 1293.68071 · doi:10.1145/2379776.2379780
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.