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]

Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & 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 & 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 & 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 & 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 & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219

[6]

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 & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[7]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019005

[8]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[9]

Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131

[10]

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 & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[11]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[12]

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 & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[13]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

[14]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[15]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[16]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[17]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[18]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018148

[19]

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 & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[20]

Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (24)
  • HTML views (241)
  • Cited by (0)

[Back to Top]