American Institute of Mathematical Sciences

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

Approximate algorithms for unrelated machine scheduling to minimize makespan

Xianzhao Zhang 1, , Dachuan Xu 2, , Donglei Du 3, and  Cuixia Miao 4,

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.
Keywords: Scheduling, linear programming, rounding., unrelated parallel machine, approximation algorithm.
Mathematics Subject Classification: Primary: 90C27, 90B35; Secondary: 68W25, 68W4.
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]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115
[2]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[3]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
[4]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058
[5]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041
[6]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017
[7]

Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271
[8]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[9]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[10]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[11]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
[12]

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
[13]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[14]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[15]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[16]

Yang Woo Shin, Dug Hee Moon. Throughput of flow lines with unreliable parallel-machine workstations and blocking. Journal of Industrial & Management Optimization, 2017, 13 (2) : 901-916. doi: 10.3934/jimo.2016052
[17]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011
[18]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825
[19]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040
[20]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (15)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences