American Institute of Mathematical Sciences

Advanced
October  2019, 15(4): 1955-1964. doi: 10.3934/jimo.2018131

Scheduling with step-deteriorating jobs to minimize the makespan

Cuixia Miao 1,2,, and  Yuzhong Zhang 3,

1. 

School of Mathematical Sciences, Qufu Normal University, Qufu 273165, China
2. 

School of Business Administration, University of New Brunswick, Fredericton, NB E3B 5A3, Canada
3. 

School of Management, Qufu Normal University, Rizhao 276826, China

* Corresponding author: Email: miaocuixia@126.com

Received  March 2018 Revised  April 2018 Published  October 2019 Early access  August 2018

In this paper, we consider the scheduling with step-deteriorating jobs. The objective is to minimize the makespan. We first propose a property of any optimal schedule after analyzing the NP-hardness for the parallel-machine scheduling with a common deteriorating date, and then present a fully polynomial time approximation scheme for the case where the number of machines $m$ is a constant and jobs have anti-agreeable parameters. Furthermore, we show that the single-machine scheduling is NP-hard in the strong sense if jobs have distinct release dates and distinct deteriorating dates.

Keywords: Scheduling, step-deteriorating, anti-agreeable, NP-hard, fully polynomial time approximation scheme.
Mathematics Subject Classification: Primary: 90B35, 90C27.
Citation: 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
References:
[1]

T. C. E. Cheng and Q. Ding, Single machine scheduling with step-deteriorating processing times, European Journal of Operational Research, 134 (2001), 623-630.  doi: 10.1016/S0377-2217(00)00284-8.  Google Scholar

[2]

L. R. Eduardo and V. Stefan, Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs, European Journal of Operational Research, 255 (2016), 21-33.  doi: 10.1016/j.ejor.2016.04.010.  Google Scholar

[3]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.  Google Scholar

[4]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[5]

P. Guo, W. M. Cheng and Y. Wang, A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs, Journal of Industrial and Magagement Optimization, 10 (2014), 1071-1090.  doi: 10.3934/jimo.2014.10.1071.  Google Scholar

[6]

P. Guo, W. M. Cheng and Y. Wang, Parallel machine scheduling with step-deteriorating jobs and setup times by a hybrid discrete cuckoo search algorithm, Engineering Optimization, 47 (2015), 1564-1585.  doi: 10.1080/0305215X.2014.982634.  Google Scholar

[7]

A. A. K. Jeng and B. M. T. Lin, Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs, Computers and Operations Research, 32 (2005), 521-536.   Google Scholar

[8]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3 (1998), 287-297.   Google Scholar

[9]

G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine, Computer and Industrial Engineering, 28 (1995), 869-879.  doi: 10.1016/0360-8352(95)00006-M.  Google Scholar

[10]

B. Mor and G. Mosheiov, Batch scheduling with step-deteriorating processing times to minimize flowtime, Naval Research Logistics, 59 (2012), 587-600.  doi: 10.1002/nav.21508.  Google Scholar

[11]

P. S. Sundararaghavan and A. S. Kunnathur, Single machine scheduling with start time dependent processing times: Some solvable cases, European Journal of Operational Research, 78 (1994), 394-403.  doi: 10.1016/0377-2217(94)90048-5.  Google Scholar

show all references

References:
[1]

T. C. E. Cheng and Q. Ding, Single machine scheduling with step-deteriorating processing times, European Journal of Operational Research, 134 (2001), 623-630.  doi: 10.1016/S0377-2217(00)00284-8.  Google Scholar

[2]

L. R. Eduardo and V. Stefan, Modeling the Parallel Machine Scheduling Problem with Step Deteriorating Jobs, European Journal of Operational Research, 255 (2016), 21-33.  doi: 10.1016/j.ejor.2016.04.010.  Google Scholar

[3]

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979.  Google Scholar

[4]

R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.  Google Scholar

[5]

P. Guo, W. M. Cheng and Y. Wang, A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs, Journal of Industrial and Magagement Optimization, 10 (2014), 1071-1090.  doi: 10.3934/jimo.2014.10.1071.  Google Scholar

[6]

P. Guo, W. M. Cheng and Y. Wang, Parallel machine scheduling with step-deteriorating jobs and setup times by a hybrid discrete cuckoo search algorithm, Engineering Optimization, 47 (2015), 1564-1585.  doi: 10.1080/0305215X.2014.982634.  Google Scholar

[7]

A. A. K. Jeng and B. M. T. Lin, Minimizing the total completion time in single-machine scheduling with step-deteriorating jobs, Computers and Operations Research, 32 (2005), 521-536.   Google Scholar

[8]

M. Y. Kovalyov and W. Kubiak, A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3 (1998), 287-297.   Google Scholar

[9]

G. Mosheiov, Scheduling jobs with step-deterioration: Minimizing makespan on a single and multi-machine, Computer and Industrial Engineering, 28 (1995), 869-879.  doi: 10.1016/0360-8352(95)00006-M.  Google Scholar

[10]

B. Mor and G. Mosheiov, Batch scheduling with step-deteriorating processing times to minimize flowtime, Naval Research Logistics, 59 (2012), 587-600.  doi: 10.1002/nav.21508.  Google Scholar

[11]

P. S. Sundararaghavan and A. S. Kunnathur, Single machine scheduling with start time dependent processing times: Some solvable cases, European Journal of Operational Research, 78 (1994), 394-403.  doi: 10.1016/0377-2217(94)90048-5.  Google Scholar

[1]

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
[2]

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
[3]

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
[4]

Bin Dan, Huali Gao, Yang Zhang, Ru Liu, Songxuan Ma. Integrated order acceptance and scheduling decision making in product service supply chain with hard time windows constraints. Journal of Industrial & Management Optimization, 2018, 14 (1) : 165-182. doi: 10.3934/jimo.2017041
[5]

Horst Osberger. Long-time behavior of a fully discrete Lagrangian scheme for a family of fourth order equations. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 405-434. doi: 10.3934/dcds.2017017
[6]

Guoliang Xue, Weiyi Zhang, Tie Wang, Krishnaiyan Thulasiraman. On the partial path protection scheme for WDM optical networks and polynomial time computability of primary and secondary paths. Journal of Industrial & Management Optimization, 2007, 3 (4) : 625-643. doi: 10.3934/jimo.2007.3.625
[7]

Maurizio Grasselli, Nicolas Lecoq, Morgan Pierre. A long-time stable fully discrete approximation of the Cahn-Hilliard equation with inertial term. Conference Publications, 2011, 2011 (Special) : 543-552. doi: 10.3934/proc.2011.2011.543
[8]

Igor E. Pritsker and Richard S. Varga. Weighted polynomial approximation in the complex plane. Electronic Research Announcements, 1997, 3: 38-44.

[9]

Yu A. Kutoyants. On approximation of BSDE and multi-step MLE-processes. Probability, Uncertainty and Quantitative Risk, 2016, 1 (0) : 4-. doi: 10.1186/s41546-016-0005-0
[10]

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
[11]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499
[12]

Peter E. Kloeden, Björn Schmalfuss. Lyapunov functions and attractors under variable time-step discretization. Discrete & Continuous Dynamical Systems, 1996, 2 (2) : 163-172. doi: 10.3934/dcds.1996.2.163
[13]

Christoph Bandt, Helena PeÑa. Polynomial approximation of self-similar measures and the spectrum of the transfer operator. Discrete & Continuous Dynamical Systems, 2017, 37 (9) : 4611-4623. doi: 10.3934/dcds.2017198
[14]

Azmy S. Ackleh, Kazufumi Ito. An approximation scheme for a nonlinear size-dependent population model. Conference Publications, 1998, 1998 (Special) : 1-6. doi: 10.3934/proc.1998.1998.1
[15]

Michele Coti Zelati. Remarks on the approximation of the Navier-Stokes equations via the implicit Euler scheme. Communications on Pure & Applied Analysis, 2013, 12 (6) : 2829-2838. doi: 10.3934/cpaa.2013.12.2829
[16]

Azmy S. Ackleh, Mark L. Delcambre, Karyn L. Sutton, Don G. Ennis. A structured model for the spread of Mycobacterium marinum: Foundations for a numerical approximation scheme. Mathematical Biosciences & Engineering, 2014, 11 (4) : 679-721. doi: 10.3934/mbe.2014.11.679
[17]

Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021
[18]

Blaine Keetch, Yves van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6091-6139. doi: 10.3934/dcdsb.2019132
[19]

Santanu Sarkar, Subhamoy Maitra. Further results on implicit factoring in polynomial time. Advances in Mathematics of Communications, 2009, 3 (2) : 205-217. doi: 10.3934/amc.2009.3.205
[20]

Chuang Peng. Minimum degrees of polynomial models on time series. Conference Publications, 2005, 2005 (Special) : 720-729. doi: 10.3934/proc.2005.2005.720

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (169)
  • HTML views (1260)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences