Search Advanced

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 6: 5957-5967. doi: 10.3934/mbe.2022278
Previous Article Next Article
Research article

Resource dependent scheduling with truncated learning effects

  • 1.
    Business School, Northwest Normal University, Lanzhou 730070, China
  • 2.
    Department of Postal Communication and Management, Shijiazhuang Posts and Telecommunications Technical College, Shijiazhuang 050021, China

  • Academic Editor: Vladimir Mityushev
  • Received: 24 January 2022 Revised: 25 March 2022 Accepted: 31 March 2022 Published: 11 April 2022

  • In this article, we investigate the single-machine scheduling problem with truncated learning effect and resource allocation, where the actual processing time of a job is a general function of its additional resources and position in a sequence. The goal is to determine the optimal resource allocation and optimal sequence such that a weighted sum of scheduling cost and resource consumption cost is minimized. We show that the problem can be solved in $ O(n^3) $ time by using an assignment formulation, where $ n $ is the number of jobs.

    Citation: Xuyin Wang, Weiguo Liu, Lu Li, Peizhen Zhao, Ruifeng Zhang. Resource dependent scheduling with truncated learning effects[J]. Mathematical Biosciences and Engineering, 2022, 19(6): 5957-5967. doi: 10.3934/mbe.2022278

    Related Papers:

  • In this article, we investigate the single-machine scheduling problem with truncated learning effect and resource allocation, where the actual processing time of a job is a general function of its additional resources and position in a sequence. The goal is to determine the optimal resource allocation and optimal sequence such that a weighted sum of scheduling cost and resource consumption cost is minimized. We show that the problem can be solved in $ O(n^3) $ time by using an assignment formulation, where $ n $ is the number of jobs.


    加载中


    [1] M. Wu, N. Xiong, A. V. Vasilakos, V. C. M. Leung, C. L. P. Chen, RNN-K: A reinforced newton method for consensus-based distributed optimization and control over multiagent systems, IEEE Trans. Cybern., (2020), 1–15. https://doi.org/10.1109/TCYB.2020.3011819 doi: 10.1109/TCYB.2020.3011819
    [2] H. Zhang, H. Jiang, B. Li, F. Liu, A. V. Vasilakos, J. Liu, A framework for truthful online auctions in cloud computing with heterogeneous user demands, IEEE Trans. Comput., 65 (2015), 805–818. https://doi.org/10.1109/INFCOM.2013.6566946 doi: 10.1109/INFCOM.2013.6566946
    [3] M. Polverini, A. Cianfrani, S. Ren, A. V. Vasilakos, Thermal-aware scheduling of batch jobs in geographically distributed data centers, IEEE Trans. Cloud Comput., 2 (2013), 71–84. https://doi.org/10.1109/TCC.2013.2295823 doi: 10.1109/TCC.2013.2295823
    [4] H. Yang, J. Yuan, C. Li, G. Zhao, Z. Sun, Q. Yao, et al., BrainIoT: Brain-like productive services provisioning with federated learning in industrial IoT, IEEE Internet Things J., 9 (2021), 2014–2024. https://doi.org/10.1109/JIOT.2021.3089334 doi: 10.1109/JIOT.2021.3089334
    [5] A. Azzouz, M. Ennigrou, S. L. Ben, Scheduling problems under learning effects: classification and cartography, Int. J. Prod. Res., 56 (2018), 1642–1661. https://doi.org/10.1080/00207543.2017.1355576 doi: 10.1080/00207543.2017.1355576
    [6] J. Pei, B. Cheng, X. Liu, P. M. Pardalos, M. Kong, Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time, Ann. Oper. Res., 272 (2019), 217–241. https://doi.org/10.1007/s10479-017-2481-8 doi: 10.1007/s10479-017-2481-8
    [7] J. Qian, H. Lin, Y. Kong, Y. Wang, Tri-criteria single machine scheduling model with release times and learning factor, Appl. Math. Comput., 387 (2020), 124543. https://doi.org/10.1016/j.amc.2019.06.057 doi: 10.1016/j.amc.2019.06.057
    [8] J. B. Wang, M. Gao, J. J. Wang, L. Liu, H. He, Scheduling with a position-weighted learning effect and job release dates, Eng. Optim., 52 (2020), 1475–1493. https://doi.org/10.1080/0305215X.2019.1664498 doi: 10.1080/0305215X.2019.1664498
    [9] J. B. Wang, F. Liu, J. J. Wang, Research on $m$-machine flow shop scheduling with truncated learning effects, Int. Tran. Oper. Res., 26 (2019), 1135–1151. https://doi.org/10.1111/itor.12323 doi: 10.1111/itor.12323
    [10] X. X. Liang, B. Zhang, J. B. Wang, N. Yin, X. Huang, Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects, J. Appl. Math. Comput., 61 (2019), 373–388. https://doi.org/10.1007/s12190-019-01255-0 doi: 10.1007/s12190-019-01255-0
    [11] X. Sun, X. N. Geng, F. Liu, Flow shop scheduling with general position weighted learning effectsto minimise total weighted completion time, J. Oper. Res. Soc., 72 (2021), 2674–2689. https://doi.org/10.1080/01605682.2020.1806746 doi: 10.1080/01605682.2020.1806746
    [12] D. Shabtay, G. Steiner, A survey of scheduling with controllable processing times, Discrete Appl. Math., 155 (2007), 1643–1666. https://doi.org/10.1016/j.dam.2007.02.003 doi: 10.1016/j.dam.2007.02.003
    [13] G. Wei, A. V. Vasilakos, Z. Yao, N. Xiong, A game-theoretic method of fair resource allocation for cloud computing services, J. Supercomput., 54 (2010), 252–269. https://doi.org/10.1007/s11227-009-0318-1 doi: 10.1007/s11227-009-0318-1
    [14] J. B. Wang, M. Z. Wang, Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, Comput. Oper. Res., 39 (2012), 492–497. https://doi.org/10.1016/j.cor.2011.05.026 doi: 10.1016/j.cor.2011.05.026
    [15] L. Mashayekhy, M. M. Nejad, D. Grosu, A. V. Vasilakos, An online mechanism for resource allocation and pricing in clouds, IEEE Trans. Comput., 65 (2016), 1172–1184. https://doi.org/10.1109/TC.2015.2444843 doi: 10.1109/TC.2015.2444843
    [16] X. X. Liang, M. Liu, Y. B. Feng, J. B. Wang, L. S. Wen, Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology, Eng. Optim., 52 (2020), 1184–1197. https://doi.org/10.1080/0305215X.2019.1638920 doi: 10.1080/0305215X.2019.1638920
    [17] C. Liu, C. Xiong, Single machine resource allocation scheduling problems with deterioration effect and general positional effect, Math. Biosci. Eng., 18 (2021), 2562–2578. https://doi.org/10.3934/mbe.2021130 doi: 10.3934/mbe.2021130
    [18] Y. Y. Lu, G. Li, Y. B. Wu, P. Ji, Optimal due-date assignment problem with learning effect and resource-dependent processing times, Optim. Lett., 8 (2014), 113–127. https://doi.org/10.1007/s11590-012-0467-7 doi: 10.1007/s11590-012-0467-7
    [19] Z. Zhu, F. Chu, Y. Yu, L. Sun, Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect, RAIRO-Oper. Res., 50 (2016), 733–748. https://doi.org/10.1051/ro/2016007 doi: 10.1051/ro/2016007
    [20] J. Pei, X. Liu, B. Liao, P. M. Pardalos, M. Kong, Single-machine scheduling with learning effect and resource-dependent processing times in the serial-batching production, Appl. Math. Modell., 58 (2018), 245–253. https://doi.org/10.1016/j.apm.2017.07.028 doi: 10.1016/j.apm.2017.07.028
    [21] W. W. Liu, C. Jiang, Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation, Eng. Optim., 52 (2020), 74–89. https://doi.org/10.1080/0305215X.2019.1580705 doi: 10.1080/0305215X.2019.1580705
    [22] X. N. Geng, J. B. Wang, D. Bai, Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect, Eng. Optim., 51 (2019), 1301–1323. https://doi.org/10.1080/0305215X.2018.1521397 doi: 10.1080/0305215X.2018.1521397
    [23] W. W. Liu, C. Jiang, Flow shop resource allocation scheduling with due date assignment, learning effect and position-dependent weights, Asia-Pac. J. Oper. Res., 37 (2020), 2050014. https://doi.org/10.1142/S0217595920500141 doi: 10.1142/S0217595920500141
    [24] J. B. Wang, D. Y. Lv, J. Xu, P. Ji, F. Li, Bicriterion scheduling with truncated learning effects and convex controllable processing times, Int. Tran. Oper. Res., 28 (2021), 1573–1593. https://doi.org/10.1111/itor.12888 doi: 10.1111/itor.12888
    [25] D. Y. Lv, J. B. Wang, Study on resource-dependent no-wait flow shop scheduling with different due-window assignment and learning effects, Asia-Pac. J. Oper. Res., 38 (2021), 2150008. https://doi.org/10.1142/S0217595921500081 doi: 10.1142/S0217595921500081
    [26] J. J. Kanet, Minimizing variation of flow time in single machine systems, Manag. Sci., 27 (1981), 1453–1459. https://doi.org/10.1287/mnsc.27.12.1453 doi: 10.1287/mnsc.27.12.1453
    [27] U. B. Bagchi, Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems, Oper. Res., 37 (1989), 118–125. https://doi.org/10.1287/opre.37.1.118 doi: 10.1287/opre.37.1.118
    [28] S. S. Panwalkar, M. L. Smith, A. Seidmann, Common due-date assignment to minimize total penalty for the one machine scheduling problem, Oper. Res., 30 (1982), 391–399. https://doi.org/10.1287/opre.30.2.391 doi: 10.1287/opre.30.2.391
    [29] G. I. Adamopoulos, C. P. Pappis, Single machine scheduling with flow allowances, J. Oper. Res. Soc., 47 (1996), 1280–1285. https://doi.org/10.2307/3010040 doi: 10.2307/3010040
    [30] A. Seidmann, S. S. Panwalkar, M. L. Smith, Optimal assignment of due dates for a single processor scheduling problem, Int. J. Prod. Res., 19 (1981), 393–399. https://doi.org/10.1080/00207548108956667 doi: 10.1080/00207548108956667
    [31] S. D. Liman, S. S. Panwalkar, S. Thongmee, Determination of common due window location in a single machine scheduling problem, Eur. J. Oper. Res., 93 (1996), 68–74. https://doi.org/10.1016/0377-2217(95)00181-6 doi: 10.1016/0377-2217(95)00181-6
    [32] Y. B. Wu, L. Wan, X. Y. Wang, Study on due-window assignment scheduling based on common flow allowance, Int. J. Prod. Econ., 165 (2015), 155–157. http://dx.doi.org/10.1016/j.ijpe.2015.04.005 doi: 10.1016/j.ijpe.2015.04.005
    [33] J. B. Wang, L. Liu, C. Wang, Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs, Appl. Math. Modell., 37 (2013), 8394–8400. http://dx.doi.org/10.1016/j.apm.2013.03.041 doi: 10.1016/j.apm.2013.03.041
    [34] C. Koulamas, G. J. Kyparisis, Single-machine scheduling problems with past-sequence-dependent setup times, Eur. J. Oper. Res., 187 (2008), 1045–1049. https://doi.org/10.1016/j.ejor.2006.03.066 doi: 10.1016/j.ejor.2006.03.066
    [35] W. Liu, X. Wang, X. Wang, P. Zhao, Due-window assignment scheduling with past-sequence-dependent setup times, Math. Biosci. Eng., 19 (2022), 3110–3126. https://doi.org/10.3934/mbe.2021130 doi: 10.3934/mbe.2021130
    [36] X. Wang, W. Liu, L. Li, P. Zhao, R. Zhang, Single-machine scheduling with due date assignment, positional-dependent weights and proportional setup times, Math. Biosci. Eng., 19 (2022), 5104–5119. https://doi.org/10.3934/mbe.2022238 doi: 10.3934/mbe.2022238
    [37] G. H. Hardy, J. E. Littlewood, G. Polya, Inequalities, Cambridge University Press, 1988. https://doi.org/10.1017/s0025557200143451
    [38] X. Wu, X. Shen, L. Zhang, Solving the planning and scheduling problem simultaneously in a hospital with a bi-layer discrete particle swarm optimization, Math. Biosci. Eng., 16 (2019), 831–861. https://doi.org/10.3934/mbe.2019039 doi: 10.3934/mbe.2019039
    [39] Z. Zhuang, Z. Lu, Z. Huang, C. Liu, W. Qin, A novel complex network based dynamic rule selection approach for open shop scheduling problem with release dates, Math. Biosci. Eng., 16 (2019), 4491–4505. https://doi.org/10.3934/mbe.2019224 doi: 10.3934/mbe.2019224
  • Reader Comments
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Mathematical Biosciences and Engineering
3.9

Metrics

Article views(1368) PDF downloads(51) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(4)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog