# 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 & 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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [5] B. Dickman and Y. Wilamowsky, Multiple common due dates, Naval Research Logistics, 48 (2001), 293-298.  doi: 10.1002/nav.9.  Google Scholar [6] S. Gawiejnowicz, Time-dependent Scheduling, Springer, Berlin, 2008.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [14] D. Nyman and J. Levitt, Maintenance Planning, Scheduling and Coordination, 2$^{nd}$ edition, Industrial Press, New York, 2010. Google Scholar [15] D. Palmer, Maintenance Planning and Scheduling Handbook, 2$^{nd}$ edition, McGraw Hill, New York, 1999. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar

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. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [5] B. Dickman and Y. Wilamowsky, Multiple common due dates, Naval Research Logistics, 48 (2001), 293-298.  doi: 10.1002/nav.9.  Google Scholar [6] S. Gawiejnowicz, Time-dependent Scheduling, Springer, Berlin, 2008.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [14] D. Nyman and J. Levitt, Maintenance Planning, Scheduling and Coordination, 2$^{nd}$ edition, Industrial Press, New York, 2010. Google Scholar [15] D. Palmer, Maintenance Planning and Scheduling Handbook, 2$^{nd}$ edition, McGraw Hill, New York, 1999. Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.   Google Scholar [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.  Google Scholar [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.  Google Scholar
 [1] Shan-Shan Lin. Due-window assignment scheduling with learning and deterioration effects. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021081 [2] Gheorghe Craciun, Jiaxin Jin, Polly Y. Yu. Single-target networks. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021065 [3] Ana Rita Nogueira, João Gama, Carlos Abreu Ferreira. Causal discovery in machine learning: Theories and applications. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021008 [4] Shi'an Wang, N. U. Ahmed. Optimal control and stabilization of building maintenance units based on minimum principle. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1713-1727. doi: 10.3934/jimo.2020041 [5] Hao Li, Honglin Chen, Matt Haberland, Andrea L. Bertozzi, P. Jeffrey Brantingham. PDEs on graphs for semi-supervised learning applied to first-person activity recognition in body-worn video. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021039 [6] Yuncherl Choi, Taeyoung Ha, Jongmin Han, Sewoong Kim, Doo Seok Lee. Turing instability and dynamic phase transition for the Brusselator model with multiple critical eigenvalues. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021035 [7] Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046 [8] Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022 [9] Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061 [10] Kai Cai, Guangyue Han. An optimization approach to the Langberg-Médard multiple unicast conjecture. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021001 [11] Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127 [12] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044 [13] Bouthaina Abdelhedi, Hatem Zaag. Single point blow-up and final profile for a perturbed nonlinear heat equation with a gradient and a non-local term. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021032 [14] Sishu Shankar Muni, Robert I. McLachlan, David J. W. Simpson. Homoclinic tangencies with infinitely many asymptotically stable single-round periodic solutions. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3629-3650. doi: 10.3934/dcds.2021010 [15] Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054

2019 Impact Factor: 1.366