×

Complexity and inapproximability results for parallel task scheduling and strip packing. (English) Zbl 1477.68119

In the parallel task scheduling problem a set \(J\) of jobs needs to be processed on a group of \(m\) machines; each job \(j\) has processing time \(p_j \in \mathbb{N}\) and it needs the simultaneous use of \(q_j \in \mathbb{N}\) machines. The goal is to to schedule the jobs on the machines so that each machine processes at most one job at any given moment and each job is processed on the required number of machines; the goal is to minimize the makespan, or completion time, of the last job.
The problem is known to be NP-hard for the case when the number \(m\) of machines is at least 5, and when the number of machines is at most 3 there is a pseudo-polynomial time algorithm for it. The complexity of the case when the number of machines is 4 was a long-standing question, that was finally answered in this paper as the authors prove that the problem when \(m = 4\) is NP-hard.
The NP-hardness proof uses a reduction from the 3-partition problem, which is known to be NP-hard. In the 3-partition problem, a list \(I\) of \(3z\) positive numbers is given whose total sum is \(zD\), a multiple of \(z\), and in which each number \(i\) has value larger than \(D/4\) and smaller than \(D/2\). The problem is to determine whether the set of numbers can be partitioned into \(z\) sets such that the sum of values in each set is equal to \(D\). The reduction from the 3-partition problem to the parallel task scheduling problem is very technical and it relies on a clever idea of using a set of structure jobs. Structure jobs are jobs such that in any optimal schedule these jobs leave \(z\) idle gaps of length \(D\) in the schedule. Hence, constructing a schedule for the jobs of minimum makespan implies also a solution for the 3-partition problem.
In the above reduction, the considered schedules place the jobs on adjacent machines. This allows the authors to obtain a lower bound for the complexity of a related problem: the strip packing problem. In this problem a group of rectangles has to be packed in a strip of integer width and minimum height so that the rectangles do not overlap. Note that a job can be represented as a rectangle if the job is scheduled on a group of consecutive machines. The authors show that there is no pseudo-polynomial time algorithm for the strip packing problem with approximation ratio smaller than \(5/4\) unless \(\mathrm{P} = \mathrm{NP}\).

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adamaszek, A.; Kociumaka, T.; Pilipczuk, M.; Pilipczuk, M., Hardness of approximation for strip packing, TOCT, 9, 3, 14,1-14,7 (2017) · Zbl 1427.68100 · doi:10.1145/3092026
[2] Amoura, Ak; Bampis, E.; Kenyon, C.; Manoussakis, Y., Scheduling independent multiprocessor tasks, Algorithmica, 32, 2, 247-261 (2002) · Zbl 0990.68023 · doi:10.1007/s00453-001-0076-9
[3] Baker, Bs; Brown, Dj; Howard, Pk, 5/4 algorithm for two-dimensional packing, J. Algor., 2, 4, 348-368 (1981) · Zbl 0472.68032 · doi:10.1016/0196-6774(81)90034-1
[4] Baker, Bs; Coffman, Egjr; Rivest, Rl, Orthogonal packings in two dimensions, SIAM J. Comput., 9, 4, 846-855 (1980) · Zbl 0447.68080 · doi:10.1137/0209064
[5] Bansal, N.; Correa, J/R; Kenyon, C.; Sviridenko, M., Bin packing in multiple dimensions Inapproximability results and approximation schemes, Math. Oper. Res., 31, 1, 31-49 (2006) · Zbl 1278.90324 · doi:10.1287/moor.1050.0168
[6] Bougeret, M.; Dutot, P-F; Jansen, K.; Robenek, C.; Trystram, D., Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms, Discret. Math. Algor. Appl., 3, 4, 553-586 (2011) · Zbl 1253.68356 · doi:10.1142/S1793830911001413
[7] Christensen, Henrik I.; Khan, Arindam; Pokutta, Sebastian; Tetali, Prasad, Approximation and online algorithms for multidimensional bin packing: A survey, Computer Science Review, 24, 63-79 (2017) · Zbl 1398.68007 · doi:10.1016/j.cosrev.2016.12.001
[8] Coffman, Egjr; Garey, Mr; Johnson, Ds; Tarjan, Re, Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Comput., 9, 4, 808-826 (1980) · Zbl 0447.68079 · doi:10.1137/0209062
[9] Jianzhong, D.; Leung, Jy-T, Complexity of scheduling parallel task systems, SIAM J. Discret. Math., 2, 4, 473-487 (1989) · Zbl 0676.90029 · doi:10.1137/0402042
[10] Feldmann, A.; Sgall, J.; Teng, S-H, Dynamic scheduling on parallel machines, Theor. Comput. Sci., 130, 1, 49-72 (1994) · Zbl 0811.68060 · doi:10.1016/0304-3975(94)90152-X
[11] Gȧlvez, W., Grandoni, F., Ingala, S., Khan, A.: Improved pseudo-polynomial-time approximation for strip packing. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 9:1-9:14. 10.4230/LIPIcs.FSTTCS.2016.9 (2016) · Zbl 1393.68189
[12] Garey, Mr; Graham, Rl, Bounds for multiprocessor scheduling with resource constraints, SIAM J. Comput., 4, 2, 187-200 (1975) · Zbl 0333.68041 · doi:10.1137/0204015
[13] Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the theory of NP-completeness (1979) · Zbl 0411.68039
[14] Golan, I., Performance bounds for orthogonal oriented two-dimensional packing algorithms, SIAM J. Comput., 10, 3, 571-582 (1981) · Zbl 0461.68076 · doi:10.1137/0210042
[15] Harren, R.; Jansen, K.; PrȧDel, L.; Rob Van, S., A (5/3 + 𝜖)-approximation for strip packing, Comput. Geom., 47, 2, 248-267 (2014) · Zbl 1283.52024 · doi:10.1016/j.comgeo.2013.08.008
[16] Harren, Rolf; Van Stee, Rob, Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 177-189 (2009), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1255.68304
[17] Jansen, K.: A (3/2+) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: 24th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pp. 224-235. 10.1145/2312005.2312048 (2012)
[18] Jansen, K., Land, F.: Scheduling monotone moldable jobs in linear time. In: 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018, pp. 172-181. 10.1109/IPDPS.2018.00027 (2018)
[19] Jansen, K.; Porkolab, L., Linear-time approximation schemes for scheduling malleable parallel tasks, Algorithmica, 32, 3, 507-520 (2002) · Zbl 1009.68013 · doi:10.1007/s00453-001-0085-8
[20] Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. arXiv:1712.04922 (2017) · Zbl 1427.68368
[21] Jansen, Klaus; Rau, Malin, Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width, WALCOM: Algorithms and Computation, 409-420 (2017), Cham: Springer International Publishing, Cham · Zbl 1427.68368
[22] Jansen, K.; Solis-Oba, R., Rectangle packing with one-dimensional resource augmentation, Discret. Optim., 6, 3, 310-323 (2009) · Zbl 1167.90632 · doi:10.1016/j.disopt.2009.04.001
[23] Jansen, K.; ThȯLe, R., Approximation algorithms for scheduling parallel jobs, SIAM J. Comput., 39, 8, 3571-3615 (2010) · Zbl 1209.68064 · doi:10.1137/080736491
[24] Kenyon, C.; Rėmila, E., A near-optimal solution to a two-dimensional cutting stock problem, Math. Oper. Res., 25, 4, 645-656 (2000) · Zbl 0977.90043 · doi:10.1287/moor.25.4.645.12118
[25] Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167-176 (1994) · Zbl 0873.68004
[26] Nadiradze, G., Wiese, A.: On approximating strip packing with a better ratio than 3/2. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1491-1510. 10.1137/1.9781611974331.ch10210.1137/1.9781611974331.ch102 (2016) · Zbl 1394.68442
[27] Schiermeyer, Ingo, Reverse-Fit: A 2-optimal algorithm for packing rectangles, Algorithms — ESA ’94, 290-299 (1994), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg
[28] Sleator, Dd, A 2.5 times optimal algorithm for packing in two dimensions, Inf. Process. Lett., 10, 1, 37-40 (1980) · Zbl 0426.05023 · doi:10.1016/0020-0190(80)90121-0
[29] Steinberg, A., A strip-packing algorithm with absolute performance bound 2, SIAM J. Comput., 26, 2, 401-409 (1997) · Zbl 0874.68140 · doi:10.1137/S0097539793255801
[30] Sviridenko, M., A note on the kenyon-remila strip-packing algorithm, Inf. Process. Lett., 112, 1-2, 10-12 (2012) · Zbl 1233.68141 · doi:10.1016/j.ipl.2011.10.003
[31] Turek, J., Wolf, J.L., Philip, S.: Approximate algorithms scheduling parallelizable tasks. In: 4th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 323-332. 10.1145/140901.141909 (1992)
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.