Scheduling uniform machines with restricted assignment

Shuguang Li; Zhimeng Liu; Shuguang Li; Zhimeng Liu

doi:10.3934/mbe.2022450

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 9: 9697-9708. doi: 10.3934/mbe.2022450

Previous Article Next Article

Research article

Scheduling uniform machines with restricted assignment

Shuguang Li ^,,
Zhimeng Liu

College of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China

Academic Editor: Shengqiang Liu

Received: 27 February 2022 Revised: 26 May 2022 Accepted: 13 June 2022 Published: 04 July 2022

The problem of minimizing makespan (maximum completion time) on uniform machines with restricted assignment is considered. The machines differ in their speeds and functionalities. Each job has a set of machines to which it can be assigned, called its processing set. The goal is to finish the jobs as soon as possible. There exist 4/3-approximation algorithms for the cases of inclusive and tree-hierarchical assignment restrictions, under an assumption that machines with higher capabilities also run at higher speeds. We eliminate the assumption and present algorithms with approximation ratios 2 and 4/3 for both cases.
- scheduling,
- uniform machines,
- inclusive restriction,
- tree-hierarchical restriction,
- makespan
Citation: Shuguang Li, Zhimeng Liu. Scheduling uniform machines with restricted assignment[J]. Mathematical Biosciences and Engineering, 2022, 19(9): 9697-9708. doi: 10.3934/mbe.2022450

Related Papers:

Abstract

The problem of minimizing makespan (maximum completion time) on uniform machines with restricted assignment is considered. The machines differ in their speeds and functionalities. Each job has a set of machines to which it can be assigned, called its processing set. The goal is to finish the jobs as soon as possible. There exist 4/3-approximation algorithms for the cases of inclusive and tree-hierarchical assignment restrictions, under an assumption that machines with higher capabilities also run at higher speeds. We eliminate the assumption and present algorithms with approximation ratios 2 and 4/3 for both cases.

References

[1]	B. Chen, C. N. Potts, G. J. Woeginger, A review of machine scheduling: Complexity, algorithms and approximability, in Handbook of combinatorial optimization, Springer, (1998), 1493–1641. https://doi.org/10.1007/978-1-4613-0303-9_25
[2]	J. Y. Leung, Handbook of scheduling: algorithms, models, and performance analysis, CRC Press, 2004.
[3]	M. Drozdowski, Classic scheduling theory, in Scheduling for Parallel Processing, Springer, (2009), 55–86.
[4]	R. L. Graham, E. L. Lawler, J. K. Lenstra, A. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5 (1979), 287–326. https://doi.org/10.1016/S0167-5060(08)70356-X doi: 10.1016/S0167-5060(08)70356-X
[5]	P. Brucker, Scheduling Algorithms, fifth edition, Springer, 2007.
[6]	J. Y. Leung, C. L. Li, Scheduling with processing set restrictions: A literature update, Int.J. Prod. Econ., 175 (2016), 1–11. https://doi.org/10.1016/j.ijpe.2014.09.038 doi: 10.1016/j.ijpe.2014.09.038
[7]	J. Y. Leung, Ng C, Fast approximation algorithms for uniform machine scheduling with processing set restrictions, Eur. J. Oper. Res., 260 (2017), 507–513. https://doi.org/10.1016/j.ejor.2017.01.013 doi: 10.1016/j.ejor.2017.01.013
[8]	L. Epstein, A. Levin, Scheduling with processing set restrictions: PTAS results for several variants, Int.J. Prod. Econ., 133 (2011), 586–595. https://doi.org/10.1016/j.ijpe.2011.04.024 doi: 10.1016/j.ijpe.2011.04.024
[9]	J. Ou, J. Y. Leung, C. L. Li, Scheduling parallel machines with inclusive processing set restrictions, Nav. Res. Log., 55 (2008), 328–338.
[10]	C. L. Li, X. Wang, Scheduling parallel machines with inclusive processing set restrictions and job release times, Eur. J. Oper. Res., 200 (2010), 702–710. https://doi.org/10.1016/j.ejor.2009.02.011 doi: 10.1016/j.ejor.2009.02.011
[11]	D. G. Kafura, V. Y. Shen, Task scheduling on a multiprocessor system with independent memories, SIAM J. Comput., 6 (1977), 167–187. https://doi.org/10.1137/0206014 doi: 10.1137/0206014
[12]	H. C. Hwang, S. Y. Chang, K. Lee, Parallel machine scheduling under a grade of service provision, Comput. Opera. Res., 31 (2004), 2055–2061. https://doi.org/10.1016/S0305-0548(03)00164-3 doi: 10.1016/S0305-0548(03)00164-3
[13]	C. A. Glass, H. Kellerer, Parallel machine scheduling with job assignment restrictions, Nav. Res. Log., 54 (2007), 250–257. https://doi.org/10.1002/nav.20202 doi: 10.1002/nav.20202
[14]	A. Bar-Noy, A. Freund, J. Naor, On-line load balancing in a hierarchical server topology, SIAM J. Comput., 31 (2001), 527–549. https://doi.org/10.1137/S0097539798346135 doi: 10.1137/S0097539798346135
[15]	Y. Huo, J. T. Leung, Fast approximation algorithms for job scheduling with processing set restrictions, Theor. Comput. Sci., 411 (2010), 3947–3955. https://doi.org/10.1016/j.tcs.2010.08.008 doi: 10.1016/j.tcs.2010.08.008
[16]	Y. Lin, W. Li, Parallel machine scheduling of machine-dependent jobs with unit-length, Eur. J. Oper. Res., 156 (2004), 261–266. https://doi.org/10.1016/S0377-2217(02)00914-1 doi: 10.1016/S0377-2217(02)00914-1
[17]	C. L. Li, Scheduling unit-length jobs with machine eligibility restrictions, Eur. J. Oper. Res., 174 (2006), 1325–1328. https://doi.org/10.1016/j.ejor.2005.03.023 doi: 10.1016/j.ejor.2005.03.023
[18]	K. Lee, J. Y. Leung, M. L. Pinedo, Scheduling jobs with equal processing times subject to machine eligibility constraints, J. Scheduling, 14 (2011), 27–38. https://doi.org/10.1007/s10951-010-0190-0 doi: 10.1007/s10951-010-0190-0
[19]	C. L. Li, Q. Li, Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions, J. Oper. Res. Soc., 66 (2015), 516–523. https://doi.org/10.1057/jors.2014.22 doi: 10.1057/jors.2014.22
[20]	C. L. Li, K. Lee, A note on scheduling jobs with equal processing times and inclusive processing set restrictions, J. Oper. Res. Soc., 67 (2016), 83–86. https://doi.org/10.1057/jors.2015.56 doi: 10.1057/jors.2015.56
[21]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, third edition, MIT press, 2009.
[22]	T. Liu, D. Tao, Classification with noisy labels by importance reweighting, IEEE Trans. Pattern Anal. Mach. Intell., 38 (2015), 447–461. https://doi.org/10.1109/TPAMI.2015.2456899 doi: 10.1109/TPAMI.2015.2456899
[23]	Z. An, X. Wang, B. Li, Z. Xiang, B. Zhang, Robust visual tracking for UAVs with dynamic feature weight selection, Appl. Intell., 2022 (2022), 1–14. https://doi.org/10.1007/s10489-022-03719-6 doi: 10.1007/s10489-022-03719-6
[24]	S. Xia, Y. Liu, X. Ding, G. Wang, H. Yu, Y. Luo, Granular ball computing classifiers for efficient, scalable and robust learning, Infor. Sci., 483 (2019), 136–152. https://doi.org/10.1016/j.ins.2019.01.010 doi: 10.1016/j.ins.2019.01.010
[25]	S. Xia, G. Wang, Z. Chen, Y. Duan, Complete random forest based class noise filtering learning for improving the generalizability of classifiers, IEEE. Trans. Knowl. Data Eng., 31 (2018), 2063–2078. https://doi.org/10.1109/TKDE.2018.2873791 doi: 10.1109/TKDE.2018.2873791

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)