A maintenance activity scheduling with time-and-position dependent deteriorating effects

Weiguo Liu; Xuyin Wang; Lu Li; Peizhen Zhao; Weiguo Liu; Xuyin Wang; Lu Li; Peizhen Zhao

doi:10.3934/mbe.2022547

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 11: 11756-11767. doi: 10.3934/mbe.2022547

Previous Article Next Article

Research article

A maintenance activity scheduling with time-and-position dependent deteriorating effects

Business School, Northwest Normal University, Lanzhou 730070, China
Academic editor: Sharon Crook

Received: 12 June 2022 Revised: 26 July 2022 Accepted: 11 August 2022 Published: 16 August 2022

We deal with a single-machine scheduling problem with an optional maintenance activity (denoted by $ ma $), where the actual processing time of a job is a function of its starting time and position. The optional $ ma $ means that the machine will perform a $ ma $, after $ ma $ is completed, the machine will return to the initial state. The objective is to determine an optimal job sequence and the location of the maintenance activity such that makespan is to be minimized. Based on some properties of an optimal sequence, we introduce a polynomial time algorithm to solve the problem, and the time complexity is $ O({n}^4) $, where $ {n} $ is the number of jobs.
- scheduling,
- deterioration effect,
- maintenance activity,
- single-machine
Citation: Weiguo Liu, Xuyin Wang, Lu Li, Peizhen Zhao. A maintenance activity scheduling with time-and-position dependent deteriorating effects[J]. Mathematical Biosciences and Engineering, 2022, 19(11): 11756-11767. doi: 10.3934/mbe.2022547

Related Papers:

Abstract

We deal with a single-machine scheduling problem with an optional maintenance activity (denoted by $ ma $), where the actual processing time of a job is a function of its starting time and position. The optional $ ma $ means that the machine will perform a $ ma $, after $ ma $ is completed, the machine will return to the initial state. The objective is to determine an optimal job sequence and the location of the maintenance activity such that makespan is to be minimized. Based on some properties of an optimal sequence, we introduce a polynomial time algorithm to solve the problem, and the time complexity is $ O({n}^4) $, where $ {n} $ is the number of jobs.

References

[1]	J. B. Wang, M. Z. Wang, Minimizing makespan in three-machine flow shops with deteriorating jobs, Comput. Oper. Res., 40 (2013), 547–557. http://dx.doi.org/10.1016/j.cor.2012.08.006 doi: 10.1016/j.cor.2012.08.006
[2]	J. B. Wang, J. J. Wang, Single machine group scheduling with time dependent processing times and ready times, Inform. Sci., 275 (2014), 226–231. http://dx.doi.org/10.1016/j.ins.2014.02.034 doi: 10.1016/j.ins.2014.02.034
[3]	J. B. Wang, J. J. Wang, Single-machine scheduling problems with precedence constraints and simple linear deterioration, Appl. Math. Modell., 39 (2015), 1172–1182. http://dx.doi.org/10.1016/j.apm.2014.07.028 doi: 10.1016/j.apm.2014.07.028
[4]	T. C. E. Cheng, S. C. Tseng, P. J. Lai, W. C. Lee, Single-machine scheduling with accelerating deterioration effects, Optim. Lett., 8 (2014), 543–554. https://doi.org/10.1007/s11590-012-0539-8 doi: 10.1007/s11590-012-0539-8
[5]	Y. Yin, T. C. E. Cheng, L. Wan, C. C. Wu, J. Liu, Two-agent single-machine scheduling with deteriorating jobs, Comput. Ind. Eng., 81 (2015), 177–185. https://doi.org/10.1016/j.cie.2015.01.002 doi: 10.1016/j.cie.2015.01.002
[6]	X. Zhang, W. C. Lin, W. H. Wu, C. C. Wu, Single-machine common/slack due window assignment problems with linear decreasing processing times, Eng. Optim., 49 (2017), 1388–1400. https://doi.org/10.1080/0305215X.2016.1248180 doi: 10.1080/0305215X.2016.1248180
[7]	F. Liu, J. Yang, Y. Y. Lu, Solution algorithms for single-machine group scheduling with ready times and deteriorating jobs, Eng. Optim., 51 (2019), 862–874. https://doi.org/10.1080/0305215X.2018.1500562 doi: 10.1080/0305215X.2018.1500562
[8]	J. B. Wang, X. X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Eng. Optim., 51 (2019), 231–246. https://doi.org/10.1080/0305215X.2018.1454442 doi: 10.1080/0305215X.2018.1454442
[9]	S. Gawiejnowicz, Models and algorithms of time-dependent scheduling, Springer, Berlin, 2020.
[10]	Y. Ma, C. Chu, C. Zuo, A survey of scheduling with deterministic machine availability constraints, Comput. Ind. Eng., 58 (2010), 199–211. http://dx.doi.org/10.1016/j.cie.2009.04.014 doi: 10.1016/j.cie.2009.04.014
[11]	J. B. Wang, C. M. Wei, Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties, Appl. Math. Comput., 177 (2011), 8093–8099. http://dx.doi.org/10.1016/j.amc.2011.03.010 doi: 10.1016/j.amc.2011.03.010
[12]	C. J. Hsu, T. C. E. Cheng, D. L. Yang, Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time, Inform. Sci., 181 (2015), 4799–4803. http://dx.doi.org/10.1016/j.ins.2011.06.010 doi: 10.1016/j.ins.2011.06.010
[13]	P. Ji, G. Li, Y. Huo, J. B. Wang, Single-machine common flow allowance scheduling with job-dependent aging effects and a deteriorating maintenance activity, Optim. Lett., 8 (2014), 1389–1400. http://dx.doi.org/10.1007/s11590-012-0504-6 doi: 10.1007/s11590-012-0504-6
[14]	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. http://dx.doi.org/10.1016/j.omega.2013.05.005 doi: 10.1016/j.omega.2013.05.005
[15]	K. Rustogi, V. A. Strusevich, Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance, J. Oper. Res. Soc., 66 (2015), 500–515. http://dx.doi.org/10.1057/jors.2014.18 doi: 10.1057/jors.2014.18
[16]	C. L. Liu, Y. Fan, C. L. Zhao, J. J. Wang, Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs, J. Ind. Manag. Optim., 13 (2017), 713–720. http://dx.doi.org/10.3934/jimo.2016042 doi: 10.3934/jimo.2016042
[17]	X. Xiong, D. Wang, T. C. E. Cheng, C. C. Wu, Y. Yin, Single-machine scheduling and common due date assignment with potential machine disruption, Int. J. Prod. Res., 56 (2018), 1345–1360. http://dx.doi.org/10.1080/00207543.2017.1346317 doi: 10.1080/00207543.2017.1346317
[18]	Z. Zhu, M. Liu, C. Chu, J. Li, Multitasking scheduling with multiple rate-modifying activities, Intl. Trans. Oper. Res., 26 (2019), 1956–1976. https://doi.org/10.1111/itor.12393 doi: 10.1111/itor.12393
[19]	X. Zhang, W. H. Wu, W. C. Lin, C. C. Wu, Machine scheduling problems under deteriorating effects and deteriorating rate-modifying activities, J. Oper. Res. Soc., 69 (2018), 439–448. https://doi.org/10.1057/s41274-017-0200-0 doi: 10.1057/s41274-017-0200-0
[20]	J. B. Wang, L. Li, Machine scheduling with deteriorating jobs and modifying maintenance activities, Comput. J., 61 (2018), 47–53. https://doi.org/10.1093/comjnl/bxx032 doi: 10.1093/comjnl/bxx032
[21]	X. Zhang, S. C. Liu, W. C. Lin, C. C. Wu, Parallel-machine scheduling with linear deteriorating jobs and preventive maintenance activities under a potential machine disruption, Comput. Ind. Eng., 145 (2020), 106482. https://doi.org/10.1016/j.cie.2020.106482 doi: 10.1016/j.cie.2020.106482
[22]	X. Zhang, D. Y. Bai, W. C. Lin, S. R. Cheng, C. C. Wu, Single-machine slack due-window assignment scheduling with multi-maintenance activities and position-and-resource-dependent processing times, Int. J. Syst. Sci. Oper. Logist., 2021 (2021), 1–12. https://doi.org/10.1080/23302674.2021.1921305 doi: 10.1080/23302674.2021.1921305
[23]	X. Y. Sun, X. N. Geng, Single machine scheduling with deteriorating effects and machine maintenance, Int. J. Prod. Res., 57 (2019), 3186–3199. https://doi.org/10.1080/00207543.2019.1566675 doi: 10.1080/00207543.2019.1566675
[24]	J. B. Wang, Y. Hu, B. Zhang, Common due-window assignment for single-machine scheduling with generalized earliness/tardiness penalties and a rate-modifying activity, Eng. Optim., 53 (2021), 496–512. https://doi.org/10.1080/0305215X.2020.1740921 doi: 10.1080/0305215X.2020.1740921
[25]	X. Jia, D. Y. Lv, Y. Hu, J. B. Wang, Z. Wang, E. Wang, Slack due-window assignment scheduling problem with deterioration effects and a deteriorating maintenance activity, Asia Pac. J. Oper. Res., 2022 (2022), forthcoming. https://doi.org/10.1142/S0217595922500051 doi: 10.1142/S0217595922500051
[26]	H. He, Y. Hu, W. W. Liu, Scheduling with deteriorating effect and maintenance activities under parallel processors, Eng. Optim., 53 (2021), 2070–2087. https://doi.org/10.1080/0305215X.2020.1844194 doi: 10.1080/0305215X.2020.1844194
[27]	S. Eilon, On a mechanistic approach to fatigue and rest periods, Int. J. Prod. Res., 3 (1964), 327–332. https://doi.org/10.1080/00207546408943065 doi: 10.1080/00207546408943065
[28]	E. J. Lodree, C. D. Geiger, A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration, Eur. J. Oper. Res., 201 (2010), 644–648. https://doi.org/10.1016/j.ejor.2009.03.027 doi: 10.1016/j.ejor.2009.03.027
[29]	M. Ji, C. J. Hsu, D. L. Yang, Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, J. Comb. Optim., 26 (2013), 437–447. https://doi.org/10.1007/s10878-011-9415-1 doi: 10.1007/s10878-011-9415-1
[30]	G. H. Hardy, J. E. Littlewood, G. Polya, Inequalities, Cambridge University Press, 1988.
[31]	C. C. Wu, J. N. D. Gupta, S. R. Cheng, B. M. T. Lin, S. H. Yip, W. C. Lin, Robust scheduling of a two-stage assembly shop with scenario-dependent processing times, Int. J. Prod. Res., 59 (2021), 5372–5387. https://doi.org/10.1080/00207543.2020.1778208 doi: 10.1080/00207543.2020.1778208
[32]	C. C. Wu, A. Azzouz, J. Y. Chen, J. Xu, W. L. Shen, L. Lu, et al., A two-agent one-machine multitasking scheduling problem solving by exact and metaheuristics, Complex. Intell. Syst., 8 (2022), 199–212. https://doi.org/10.1007/S40747-021-00355-4 doi: 10.1007/S40747-021-00355-4
[33]	C. C. Wu, D. Bai, X. Zhang, S. R. Cheng, W. C. Lin, Z. L. Wu, A robust customer order scheduling problem along with scenario-dependent component processing times and due dates, J. Manuf. Syst., 58 (2021), 291–305. https://doi.org/10.1016/j.jmsy.2020.12.013 doi: 10.1016/j.jmsy.2020.12.013

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)