Search Advanced

Mathematical Biosciences and Engineering

2021, Volume 18, Issue 3: 2562-2578. doi: 10.3934/mbe.2021130
Previous Article Next Article
Research article

Single machine resource allocation scheduling problems with deterioration effect and general positional effect

  • 1.
    Management School, Hangzhou Dianzi University, China
  • 2.
    School of Business, University of North Carolina at Pembroke, USA
  • Received: 02 November 2020 Accepted: 08 March 2021 Published: 16 March 2021

  • This paper investigates single machine scheduling problems where the actual processing time of a job is dependent on its starting time, processing position and the amount of resource allocation. We present two unified models and provide a bicriteria analysis for the general scheduling criteria and the total weighted resource consumption. We consider two different versions for treating the two criteria and show that the unified models can be applied to solve scheduling problems under various due window assignment considerations. We prove that two different versions of the problems can be solved in polynomial time, respectively.

    Citation: Chunlai Liu, Chuanhui Xiong. Single machine resource allocation scheduling problems with deterioration effect and general positional effect[J]. Mathematical Biosciences and Engineering, 2021, 18(3): 2562-2578. doi: 10.3934/mbe.2021130

    Related Papers:

  • This paper investigates single machine scheduling problems where the actual processing time of a job is dependent on its starting time, processing position and the amount of resource allocation. We present two unified models and provide a bicriteria analysis for the general scheduling criteria and the total weighted resource consumption. We consider two different versions for treating the two criteria and show that the unified models can be applied to solve scheduling problems under various due window assignment considerations. We prove that two different versions of the problems can be solved in polynomial time, respectively.


    加载中


    [1] E. B. Edis, C. Oguz, I. Ozkarahan, Parallel machine scheduling with additional resources: Notation, classification, models and solution methods, Eur. J. Oper. Res., 230 (2013), 449–463.
    [2] Y Leyvand, D Shabtay, G Steiner, L. Yedidsion, Just-in-time scheduling with controllable processing times on parallel machines, J. Comb. Optim., 19 (2010), 347–368. doi: 10.1007/s10878-009-9270-5
    [3] M. Ji, D. Yao, Q. Yang, T. C. E. Cheng, Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity, Int. Trans. Oper. Res., 22 (2015), 997–1015.
    [4] G. Wan, S. R. Vakati, J. Y. T. Leung, M. Pinedo, Scheduling two agents with controllable processing times, Eur. J. Oper. Res., 205 (2010), 528–539. doi: 10.1016/j.ejor.2010.01.005
    [5] B. Mor, G. Mosheiov, Batch scheduling of identical jobs with controllable processing times, Comput. Oper. Res., 41 (2014), 115–124. doi: 10.1016/j.cor.2013.08.007
    [6] D. Shabtay, G. Steiner, A survey of scheduling with controllable processing times, Discrete Appl. Math., 155 (2007), 1643–1666. doi: 10.1016/j.dam.2007.02.003
    [7] A. Shioura, N. V. Shakhlevich, V. A. Strusevich, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches, Eur. J. Oper. Res., 266 (2018), 795–818. doi: 10.1016/j.ejor.2017.08.034
    [8] C. Low, G. H. Wu, Unrelated parallel-machine scheduling with controllable processing times and eligibility constraints to minimize the makespan, J. Ind. Prod. Eng., 33 (2016), 286–293.
    [9] A. Shioura, N. V. Shakhlevich, V. A. Strusevich, Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times, Math. Program., 153 (2015), 495–534. doi: 10.1007/s10107-014-0814-9
    [10] Y. Yin, D. J. Wang, T. C. E. Cheng, C. C. Wu, Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times, J. Oper. Res. Soc., 67 (2016), 1169–1183. doi: 10.1057/jors.2016.14
    [11] D. Shabtay, G. Steiner, R. Zhang, Optimal coordination of resource allocation, due date assignment and scheduling decisions, Omega, 65 (2016), 41–54.
    [12] L. Tang, H. Gong, J. Liu, F. Li, Bicriteria scheduling on a single batching machine with job transportation and deterioration considerations, Naval Res. Logistics, 61 (2014), 269–285. doi: 10.1002/nav.21582
    [13] D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res., 115 (1999), 173–178. doi: 10.1016/S0377-2217(98)00246-X
    [14] D. Oron, Scheduling controllable processing time jobs in a deteriorating environment, J. Oper. Res. Soc., 65 (2014), 49–56. doi: 10.1057/jors.2013.5
    [15] T. C. E. Cheng, Q. Ding, B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. Res., 152 (2004), 1–13. doi: 10.1016/S0377-2217(02)00909-8
    [16] D. Biskup, A state-of-the-art review on scheduling with learning effects, Eur. J. Oper. Res., 188 (2008), 315–329. doi: 10.1016/j.ejor.2007.05.040
    [17] S. Gawiejnowicz, Time-Dependent Scheduling, Springer, 2008.
    [18] Y. Wang, X Li, R. Ruiz, An exact algorithm for the shortest path problem with position-based learning effects, IEEE Trans. Sys. Man Cyber. Syst., 47 (2016), 3037–3049.
    [19] V. S. Gordon, V. A. Strusevich, Single machine scheduling and due date assignment with positionally dependent processing times, Eur. J. Oper. Res., 198 (2009), 57–62. doi: 10.1016/j.ejor.2008.07.044
    [20] C. Zhao, H. Tang, Due-window assignment for a single machine scheduling with both deterioration and positional effects, Asia Pac. J. Oper. Res., 32 (2015), 1550014. doi: 10.1142/S0217595915500141
    [21] Y. Yin, W. H. Wu, T. C. E. Cheng, C. C. Wu, Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities, Int. J. Prod. Res., 52 (2014), 2311–2326. doi: 10.1080/00207543.2013.855833
    [22] K. Rustogi, V. A. Strusevich, Single machine scheduling with general positional deterioration and rate-modifying maintenance, Omega, 40 (2012), 791–804. doi: 10.1016/j.omega.2011.12.007
    [23] K. Rustogi, V. A. Strusevich, Combining time and position dependent effects on a single machine subject to rate-modifying activities, Omega, 42 (2014), 166–178. doi: 10.1016/j.omega.2013.05.005
    [24] R. Rudek, Scheduling on parallel processors with varying processing times, Comput. Oper. Res., 81 (2017), 90–101. doi: 10.1016/j.cor.2016.12.007
    [25] A. Rudek, R. Rudek, A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models, Comput. Math. Appl., 62 (2011), 1870–1878. doi: 10.1016/j.camwa.2011.06.030
    [26] A. Rudek, R. Rudek, On flowshop scheduling problems with the aging effect and resource allocation, Int. J. Adv. Manuf. Technol., 62 (2012), 135–145. doi: 10.1007/s00170-011-3809-1
    [27] M. Ji, D. Yao, Q. Yang, T. C. E. Cheng, Single-machine common flow allowance scheduling with aging effect, resource allocation, and a rate-modifying activity, Int. Trans. Oper. Res., 22 (2015), 997–1015.
    [28] L. H. Sun, K. Cui, J. Chen, J. Wang, Due date assignment and convex resource allocation scheduling with variable job processing times, Int. J. Prod. Res., 54 (2016), 3551–3560. doi: 10.1080/00207543.2015.1083628
    [29] Y. Y. Lu, J. Jin, P. Ji, J. B. Wang, Resource-dependent scheduling with deteriorating jobs and learning effects on unrelated parallel machine, Neural Comput. Appl., 27 (2016), 1993–2000. doi: 10.1007/s00521-015-1993-x
    [30] J. B. Wang, J. J. Wang, Research on scheduling with job-dependent learning effect and convex resource-dependent processing times, Int. J. Prod. Res., 53 (2015), 5826–5836. doi: 10.1080/00207543.2015.1010746
    [31] C. Zhao, C. J. Hsu, W. H. Wu, S. R. Cheng, C. C. Wu, Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation, J. Manuf. Syst., 38 (2016), 134–140. doi: 10.1016/j.jmsy.2015.12.002
    [32] Y. Tian, M. Xu, C. Jiang, J. B. Wang, X. Y. Wang, No-wait resource allocation flowshop scheduling with learning effect under limited cost availability, Comput. J., 62 (2019), 90–96. doi: 10.1093/comjnl/bxy034
    [33] G. Mosheiov, A. Sarig, V. Strusevich, Minmax scheduling and due-window assignment with position-dependent processing times and job rejection, 4OR, 2019 (2019), 1–18.
    [34] S. D. Liman, S. S. Panwalkar, S. Thongmee, Common due window size and location determination in a single machine scheduling problem, J. Oper. Res. Soc., 49 (1998), 1007–1010. doi: 10.1057/palgrave.jors.2600601
    [35] 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. doi: 10.1016/j.ijpe.2015.04.005
    [36] Q. Yue, G. Wan, Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects, J. Oper. Res. Soc., 67 (2016), 872–883. doi: 10.1057/jors.2015.107
    [37] D. Shabtay, N. Gaspar, L. Yedidsion, A bicriteria approach to scheduling a single machine with job rejection and positional penalties, J. Comb. Optim., 23 (2012), 395–424. doi: 10.1007/s10878-010-9350-6
    [38] JC Yepes-Borrero, F Villa, F Perea, J. PabloCaballero-Villalobos, GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources, Expert Syst. Appl., 141 (2020), 1–12.
    [39] J. C. Yepes-Borrero, F. Perea, R. Ruiz, F. Villa, Bi-objective parallel machine scheduling with additional resources during setups, Eur. J. Oper. Res., Forthcoming, 2020.
    [40] D. Wang, Z. Li, Bicriterion scheduling with a negotiable common due window and resource-dependent processing times, Inf. Sci., 478 (2019), 258–274. doi: 10.1016/j.ins.2018.11.023
  • Reader Comments
  • © 2021 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(2350) PDF downloads(104) Cited by(6)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(2)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog