Article Contents
Article Contents

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

• * Corresponding author
• 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.

Mathematics Subject Classification: Primary: 90B35; Secondary: 90C26.

 Citation:

•  [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.