Estimating the makespan of the two-valued restricted assignment problem. (English) Zbl 1393.90057
The paper deals with a scheduling problem of unrelated machines, where each considered job from a finite set of jobs must be assigned to one of the machines which are able to process the job. Each couple job-machine is connected to an individual processing time of the job on the machine. The sum of all processing times of the jobs assigned to a machine is denoted as the makespan of the machine. Objective of the restricted assignment problem is to minimize the maximal makespan across the set of machines. The authors focused their effort on a theoretical research concerning a special case of the above problem, where only two different values of processing time are taken into account. The goal of the research consists in improvement of the integrality gap estimation, what is ratio of optimal objective function values of the original integer programming problem and the linear programming relaxation of the problem. The authors were successful in improving the integrality gap from the previously known value of 11/6 to the value of 5/3. This excellent result was achieved by utilizing and improving the Svensson’s bound and search technique. The presented research is properly described by a sequence of theorems and lemmas and carefully performed proofs. Generally, the paper constitutes a valuable piece of work for community of professionals in the theory of algorithms.
Reviewer: Jaroslav Janáček (Žilina)
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B80 | Discrete location and assignment |
Keywords:
unrelated scheduling; restricted assignment; configuration LP; integrality gap; estimation algorithmReferences:
| [1] | Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, (STOC 2006), pp. 31-40 (2006) · Zbl 1301.90057 |
| [2] | Chakrabarty, D., Khanna, S., Li, S.: On \[(1, \epsilon )\](1,ϵ)-restricted assignment makespan minimization. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 1087-1101 (2015) · Zbl 1372.68044 |
| [3] | Ebenlendr, T., Krčál, M., Sgall, J.: Graph balancing: a special case of scheduling unrelated parallel machines. Algorithmica 68(1), 62-80 (2014) · Zbl 1295.68214 · doi:10.1007/s00453-012-9668-9 |
| [4] | Huang, C.-C., Ott, S.: A combinatorial approximation algorithm for graph balancing with light hyper edges. CoRR. arxiv:abs/1507.07396 (2015) · Zbl 0804.90077 |
| [5] | Kolliopoulos, S.G., Moysoglou, Y.: The 2-valued case of makespan minimization with assignment constraints. Inf. Process. Lett. 113(1), 39-43 (2013) · Zbl 1259.68238 · doi:10.1016/j.ipl.2012.09.004 |
| [6] | Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1-3), 259-271 (1990) · Zbl 0715.90063 · doi:10.1007/BF01585745 |
| [7] | Shchepin, E.V., Vakhania, N.: An optimal rounding gives a better approximation for scheduling unrelated machines. Oper. Res. Lett. 33(2), 127-133 (2005) · Zbl 1099.90024 · doi:10.1016/j.orl.2004.05.004 |
| [8] | Shmoys, D.B., Tardos, É.: An approximation algorithm for the generalized assignment problem. Math. Program. 62(1-3), 461-474 (1993) · Zbl 0804.90077 · doi:10.1007/BF01585178 |
| [9] | Svensson, O.: Santa Claus schedules jobs on unrelated machines. SIAM J. Comput. 41(5), 1318-1341 (2012) · Zbl 1257.68083 · doi:10.1137/110851201 |
| [10] | Verschae, J., Wiese, A.: On the configuration-LP for scheduling on unrelated machines. In: Algorithms—ESA 2011. Springer, pp. 530-542 (2011) · Zbl 1348.90317 |
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.
