American Institute of Mathematical Sciences

April  2017, 13(2): 713-720. doi: 10.3934/jimo.2016042

Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs

 1 Institute of Systems Engineering, Dalian University of Technology, Dalian, Liaoning, 116023, China 2 School of Mathematics and System Science, Shenyang Normal University, Shenyang, Liaoning, 110034, China

* Corresponding author

Received  October 2013 Revised  June 2016 Published  July 2016

In this paper, we consider the multiple common due-dates assignment and machine scheduling with linear deteriorating jobs and optimal maintenance activity. The linear deteriorating jobs means job processing times are an increasing function of their starting times. The maintenance activity requires a fixed time interval. During the time interval, the machine is turned off and no job is processed. Once completing the maintenance, the machine will revert to its initial condition. The objective is to schedule the jobs, the due dates and the maintenance activity, so as to minimize the total cost including earliness, tardiness, and the due dates. We provide some properties of optimal sequence and introduce an efficient $O({n^{\rm{2}}}\log n)$ algorithm to solve the problem.

Citation: Chunlai Liu, Yanpeng Fan, Chuanli Zhao, Jianjun Wang. Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs. Journal of Industrial and Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042
References:
 [1] M. A. Bajestani, Integrating Maintenance Planning and Production Scheduling, Making Operational Decisions with a Strategic Perspective, Ph. D thesis, University of Toronto in Toronto, 2014. [2] W. W. Cui, Z. Q. Lu and E. Pan, Integrated production scheduling and maintenance policy for robustness in a single machine, Computers and Operations Research, 47 (2014), 81-91.  doi: 10.1016/j.cor.2014.02.006. [3] T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152 (2004), 1-13.  doi: 10.1016/S0377-2217(02)00909-8. [4] S. Chand and D. Chhajed, A single machine model for determination of optimal due dates and sequence, Operations Research, 40 (1992), 596-602.  doi: 10.1287/opre.40.3.596. [5] B. Dickman and Y. Wilamowsky, Multiple common due dates, Naval Research Logistics, 48 (2001), 293-298.  doi: 10.1002/nav.9. [6] S. Gawiejnowicz, Time-dependent Scheduling, Springer, Berlin, 2008. [7] M. Gopalakrishnan, S. L. Ahire and D. M. Miller, Maximizing the effectiveness of a preventive maintenance system: an adaptive modeling approach, Management Science, 43 (1997), 827-840.  doi: 10.1287/mnsc.43.6.827. [8] C. J. Hsu, C. J. Yang and D. L. Yang, Due-date assignment and optional maintenance activity scheduling with linear deteriorating jobs, Journal of Marine Science and Technology, 19 (2011), 97-100. [9] M. A. Kubzin and V. A. Strusevich, Two-machine flow shop no-wait scheduling with machine maintenance, 4OR: A Quarterly Journal of Operations research, 3 (2005), 303-313.  doi: 10.1007/s10288-005-0070-1. [10] W. H. Kuo and D. L. Yang, A note on due-date assignment and single-machine scheduling with deteriorating jobs, Journal of the Operational Research Society, 59 (2008), 857-859.  doi: 10.1057/palgrave.jors.2602396. [11] I. Kacem and E. Levner, An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs, Journal of Industrial and Management Optimization, 12 (2016), 811-817.  doi: 10.3934/jimo.2016.12.811. [12] S. S. Li, C. T. Ng and J. J. Yuan, Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine, International Journal of Production Economics, 131 (2011), 747-751.  doi: 10.1016/j.ijpe.2011.02.029. [13] G. Mosheiov, Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21 (1994), 653-659.  doi: 10.1016/0305-0548(94)90080-9. [14] D. Nyman and J. Levitt, Maintenance Planning, Scheduling and Coordination, 2$^{nd}$ edition, Industrial Press, New York, 2010. [15] D. Palmer, Maintenance Planning and Scheduling Handbook, 2$^{nd}$ edition, McGraw Hill, New York, 1999. [16] K. Rustogi and 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. [17] K. Rustogi and 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. [18] J. B. Wang and M. Z. Wang, Single machine multiple common due dates scheduling with learning effects, Computers and Mathematics with Applications, 60 (2010), 2998-3002.  doi: 10.1016/j.camwa.2010.09.061. [19] X. Y. Yu, Y. L. Zhang and G. Steiner, Single-machine scheduling with periodic maintenance to minimize makespan revisited, Journal of Scheduling, 17 (2014), 263-270.  doi: 10.1007/s10951-013-0350-0. [20] S. J. Yang, C. J. Hsu and D. L. Yang, Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration, International Journal of Information and Management Sciences, 21 (2010), 177-195. [21] S. J. Yang, H. T. Lee and J. Y. Guo, Multiple common due dates assignment and scheduling problems with resource allocation and general position-dependent deterioration effect, The International Journal Advanced Manufacturing Technology, 67 (2013), 181-188.  doi: 10.1007/s00170-013-4763-x. [22] C. L. Zhao, Y. Q. Yin, T. C. E. Cheng and C. C. Wu, Single-machine scheduling and due date assignment with rejection and position-dependent processing times, Journal of Industrial and Management Optimization, 10 (2014), 691-700.  doi: 10.3934/jimo.2014.10.691.

show all references

References:
 [1] M. A. Bajestani, Integrating Maintenance Planning and Production Scheduling, Making Operational Decisions with a Strategic Perspective, Ph. D thesis, University of Toronto in Toronto, 2014. [2] W. W. Cui, Z. Q. Lu and E. Pan, Integrated production scheduling and maintenance policy for robustness in a single machine, Computers and Operations Research, 47 (2014), 81-91.  doi: 10.1016/j.cor.2014.02.006. [3] T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152 (2004), 1-13.  doi: 10.1016/S0377-2217(02)00909-8. [4] S. Chand and D. Chhajed, A single machine model for determination of optimal due dates and sequence, Operations Research, 40 (1992), 596-602.  doi: 10.1287/opre.40.3.596. [5] B. Dickman and Y. Wilamowsky, Multiple common due dates, Naval Research Logistics, 48 (2001), 293-298.  doi: 10.1002/nav.9. [6] S. Gawiejnowicz, Time-dependent Scheduling, Springer, Berlin, 2008. [7] M. Gopalakrishnan, S. L. Ahire and D. M. Miller, Maximizing the effectiveness of a preventive maintenance system: an adaptive modeling approach, Management Science, 43 (1997), 827-840.  doi: 10.1287/mnsc.43.6.827. [8] C. J. Hsu, C. J. Yang and D. L. Yang, Due-date assignment and optional maintenance activity scheduling with linear deteriorating jobs, Journal of Marine Science and Technology, 19 (2011), 97-100. [9] M. A. Kubzin and V. A. Strusevich, Two-machine flow shop no-wait scheduling with machine maintenance, 4OR: A Quarterly Journal of Operations research, 3 (2005), 303-313.  doi: 10.1007/s10288-005-0070-1. [10] W. H. Kuo and D. L. Yang, A note on due-date assignment and single-machine scheduling with deteriorating jobs, Journal of the Operational Research Society, 59 (2008), 857-859.  doi: 10.1057/palgrave.jors.2602396. [11] I. Kacem and E. Levner, An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs, Journal of Industrial and Management Optimization, 12 (2016), 811-817.  doi: 10.3934/jimo.2016.12.811. [12] S. S. Li, C. T. Ng and J. J. Yuan, Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine, International Journal of Production Economics, 131 (2011), 747-751.  doi: 10.1016/j.ijpe.2011.02.029. [13] G. Mosheiov, Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21 (1994), 653-659.  doi: 10.1016/0305-0548(94)90080-9. [14] D. Nyman and J. Levitt, Maintenance Planning, Scheduling and Coordination, 2$^{nd}$ edition, Industrial Press, New York, 2010. [15] D. Palmer, Maintenance Planning and Scheduling Handbook, 2$^{nd}$ edition, McGraw Hill, New York, 1999. [16] K. Rustogi and 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. [17] K. Rustogi and 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. [18] J. B. Wang and M. Z. Wang, Single machine multiple common due dates scheduling with learning effects, Computers and Mathematics with Applications, 60 (2010), 2998-3002.  doi: 10.1016/j.camwa.2010.09.061. [19] X. Y. Yu, Y. L. Zhang and G. Steiner, Single-machine scheduling with periodic maintenance to minimize makespan revisited, Journal of Scheduling, 17 (2014), 263-270.  doi: 10.1007/s10951-013-0350-0. [20] S. J. Yang, C. J. Hsu and D. L. Yang, Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration, International Journal of Information and Management Sciences, 21 (2010), 177-195. [21] S. J. Yang, H. T. Lee and J. Y. Guo, Multiple common due dates assignment and scheduling problems with resource allocation and general position-dependent deterioration effect, The International Journal Advanced Manufacturing Technology, 67 (2013), 181-188.  doi: 10.1007/s00170-013-4763-x. [22] C. L. Zhao, Y. Q. Yin, T. C. E. Cheng and C. C. Wu, Single-machine scheduling and due date assignment with rejection and position-dependent processing times, Journal of Industrial and Management Optimization, 10 (2014), 691-700.  doi: 10.3934/jimo.2014.10.691.
 [1] 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 [2] Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071 [3] Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial and Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033 [4] Imed Kacem, Eugene Levner. An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial and Management Optimization, 2016, 12 (3) : 811-817. doi: 10.3934/jimo.2016.12.811 [5] Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial and Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219 [6] Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71 [7] Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005 [8] Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691 [9] Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131 [10] Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021192 [11] Ji-Bo Wang, Dan-Yang Lv, Shi-Yun Wang, Chong Jiang. Resource allocation scheduling with deteriorating jobs and position-dependent workloads. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022011 [12] Chaoming Hu, Xiaofei Qian, Shaojun Lu, Xinbao Liu, Panos M Pardalos. Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021142 [13] 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 [14] Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825 [15] Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040 [16] 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 [17] Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial and Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757 [18] 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 [19] Hanyu Gu, Hue Chi Lam, Yakov Zinder. Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center. Journal of Industrial and Management Optimization, 2022, 18 (2) : 747-772. doi: 10.3934/jimo.2020177 [20] Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

2021 Impact Factor: 1.411