Approximate algorithms for unrelated machine scheduling to minimize makespan

Xianzhao  Zhang; Dachuan  Xu; Donglei  Du; Cuixia  Miao

doi:10.3934/jimo.2016.12.771

Article Contents

2016, Volume 12, Issue 2: 771-779. Doi: 10.3934/jimo.2016.12.771

This issue Previous Article The coordination of single-machine scheduling with availability constraints and delivery Next Article VISUAL MISER: An efficient user-friendly visual program for solving optimal control problems

Approximate algorithms for unrelated machine scheduling to minimize makespan

1.
School of Science, Linyi University, Linyi 276005
2.
Department of Information and Operations Research, Beijing University of Technology, Beijing 100124
3.
Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3
4.
School of Mathematical Sciences, Qufu Normal University, Qufu 273165

Received: July 2014

Revised: March 2015

Published: April 2016

Abstract / Introduction Related Papers Cited by

Abstract

We study two unrelated machine scheduling problems with machine dependent release dates to minimize the makespan. For the case with fixed processing time where processing job $j$ on machine $i$ requires time $p_{ij}$ and incurs a cost of $c_{ij}$, we derive a $2$-approximation algorithm. For the problem with variable processing times where the cost increases linearly as the processing time decreases, we propose a $(2+\epsilon)$-approximation algorithm.

Keywords:

Mathematics Subject Classification: Primary: 90C27, 90B35; Secondary: 68W25, 68W40.

Citation:

Related Papers

Cited by

References

[1]	L. Chen, W. C. Luo, and G. C. Zhang, Approximation algorithms for unrelated machine scheduling with an energy budget, in Proceedings of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM), (2011), 244-254.doi: 10.1007/978-3-642-21204-8_27.
[2]	J. R. Correa, A. Marchetti-Spaccamela, J. Matuschke, L. Stougie, O. Svensson, V. Verdugo, and J. Verschae, Strong LP formulations for scheduling splittable jobs on unrelated machines, in Proceedings of the 17th Integer Programming and Combinatorial Optimization (IPCO), (2014), 249-260.doi: 10.1007/978-3-319-07557-0_21.
[3]	T. Ebenlendr, M. Krcal, and J. Sgall, Graph balancing: a special case of scheduling unrelated parallel machines, Algorithmica, 68 (2014), 62-80.doi: 10.1007/s00453-012-9668-9.
[4]	N. K. Freemana, J. Mittenthala and S. H. Melouk, Parallel-machine scheduling to minimize overtime and waste costs, IIE Transactions, 46 (2014), 601-618.doi: 10.1080/0740817X.2013.851432.
[5]	R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287-326.doi: 10.1016/S0167-5060(08)70356-X.
[6]	A. Grigoriev, M. Sviridenko and M. Uetz, Machine scheduling with resource dependent processing times, Mathematical Programming, 110 (2007), 209-228.doi: 10.1007/s10107-006-0059-3.
[7]	J. K. Lenstra, D. B. Shmoys and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46 (1990), 259-271.doi: 10.1007/BF01585745.
[8]	W. Li, J. Li, X. Zhang and Z. Chen, Parallel-machine scheduling problem under the job rejection constraint, in Proceedings of the 8th Frontiers in Algorithmics (FAW), (2014), 158-169.doi: 10.1007/978-3-319-08016-1_15.
[9]	E. V. Shchepin and N. Vakhania, An optimal rounding gives a better approximation for scheduling unrelated machines, Operational Research Letters, 33 (2005), 127-133.doi: 10.1016/j.orl.2004.05.004.
[10]	D. B. Shmoys and É. Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming, 62 (1993), 461-474.doi: 10.1007/BF01585178.
[11]	O. Svensson, Santa clause schedules jobs on unrelated machines, SIAM Journal on Computing, 41 (2012), 1318-1341.doi: 10.1137/110851201.
[12]	V. V. Vazirani, Approximation Algorithms, Springer, Berlin, 2003.
[13]	D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, London, 2011.doi: 10.1017/CBO9780511921735.