April  2016, 12(2): 771-779. doi: 10.3934/jimo.2016.12.771

Approximate algorithms for unrelated machine scheduling to minimize makespan

1. 

School of Science, Linyi University, Linyi 276005, China

2. 

Department of Information and Operations Research, Beijing University of Technology, Beijing 100124, China

3. 

Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3

4. 

School of Mathematical Sciences, Qufu Normal University, Qufu 273165, China

Received  July 2014 Revised  March 2015 Published  June 2015

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.
Citation: Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771
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.  doi: 10.1007/978-3-642-21204-8_27.  Google Scholar

[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.  doi: 10.1007/978-3-319-07557-0_21.  Google Scholar

[3]

T. Ebenlendr, M. Krcal, and J. Sgall, Graph balancing: a special case of scheduling unrelated parallel machines,, Algorithmica, 68 (2014), 62.  doi: 10.1007/s00453-012-9668-9.  Google Scholar

[4]

N. K. Freemana, J. Mittenthala and S. H. Melouk, Parallel-machine scheduling to minimize overtime and waste costs,, IIE Transactions, 46 (2014), 601.  doi: 10.1080/0740817X.2013.851432.  Google Scholar

[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.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[6]

A. Grigoriev, M. Sviridenko and M. Uetz, Machine scheduling with resource dependent processing times,, Mathematical Programming, 110 (2007), 209.  doi: 10.1007/s10107-006-0059-3.  Google Scholar

[7]

J. K. Lenstra, D. B. Shmoys and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines,, Mathematical Programming, 46 (1990), 259.  doi: 10.1007/BF01585745.  Google Scholar

[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.  doi: 10.1007/978-3-319-08016-1_15.  Google Scholar

[9]

E. V. Shchepin and N. Vakhania, An optimal rounding gives a better approximation for scheduling unrelated machines,, Operational Research Letters, 33 (2005), 127.  doi: 10.1016/j.orl.2004.05.004.  Google Scholar

[10]

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

[11]

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

[12]

V. V. Vazirani, Approximation Algorithms,, Springer, (2003).   Google Scholar

[13]

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

show all references

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.  doi: 10.1007/978-3-642-21204-8_27.  Google Scholar

[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.  doi: 10.1007/978-3-319-07557-0_21.  Google Scholar

[3]

T. Ebenlendr, M. Krcal, and J. Sgall, Graph balancing: a special case of scheduling unrelated parallel machines,, Algorithmica, 68 (2014), 62.  doi: 10.1007/s00453-012-9668-9.  Google Scholar

[4]

N. K. Freemana, J. Mittenthala and S. H. Melouk, Parallel-machine scheduling to minimize overtime and waste costs,, IIE Transactions, 46 (2014), 601.  doi: 10.1080/0740817X.2013.851432.  Google Scholar

[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.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[6]

A. Grigoriev, M. Sviridenko and M. Uetz, Machine scheduling with resource dependent processing times,, Mathematical Programming, 110 (2007), 209.  doi: 10.1007/s10107-006-0059-3.  Google Scholar

[7]

J. K. Lenstra, D. B. Shmoys and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines,, Mathematical Programming, 46 (1990), 259.  doi: 10.1007/BF01585745.  Google Scholar

[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.  doi: 10.1007/978-3-319-08016-1_15.  Google Scholar

[9]

E. V. Shchepin and N. Vakhania, An optimal rounding gives a better approximation for scheduling unrelated machines,, Operational Research Letters, 33 (2005), 127.  doi: 10.1016/j.orl.2004.05.004.  Google Scholar

[10]

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

[11]

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

[12]

V. V. Vazirani, Approximation Algorithms,, Springer, (2003).   Google Scholar

[13]

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

[1]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[2]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[3]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[4]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[5]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[6]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004

[7]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[8]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[9]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[10]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[11]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[12]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

[13]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055

[14]

Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (60)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]