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 and 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-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.

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-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.

[1]

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

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190
[3]

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

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174
[5]

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

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124
[7]

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

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 and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041
[9]

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

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

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 and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[12]

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 and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057
[13]

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 and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[14]

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 and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
[15]

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

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

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 and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009
[18]

Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132
[19]

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

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

2021 Impact Factor: 1.411

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy