Advanced Search
Article Contents
Article Contents

Approximate algorithms for unrelated machine scheduling to minimize makespan

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C27, 90B35; Secondary: 68W25, 68W40.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    D. B. Shmoys and É. Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming, 62 (1993), 461-474.doi: 10.1007/BF01585178.


    O. Svensson, Santa clause schedules jobs on unrelated machines, SIAM Journal on Computing, 41 (2012), 1318-1341.doi: 10.1137/110851201.


    V. V. Vazirani, Approximation Algorithms, Springer, Berlin, 2003.


    D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, London, 2011.doi: 10.1017/CBO9780511921735.

  • 加载中

Article Metrics

HTML views() PDF downloads(192) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint