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. CuiZ. 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. ChengQ. 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. GopalakrishnanS. 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. HsuC. 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. LiC. 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. YuY. 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. YangC. 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. YangH. 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. ZhaoY. Q. YinT. 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. CuiZ. 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. ChengQ. 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. GopalakrishnanS. 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. HsuC. 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. LiC. 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. YuY. 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. YangC. 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. YangH. 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. ZhaoY. Q. YinT. 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]

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 - A, 2021  doi: 10.3934/dcds.2021035

[2]

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

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (155)
  • HTML views (366)
  • Cited by (1)

[Back to Top]