# American Institute of Mathematical Sciences

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

## Scheduling with step-deteriorating jobs to minimize the makespan

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

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:

show all references

##### References:
 [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 - A, 2017, 37 (1) : 405-434. doi: 10.3934/dcds.2017017 [6] 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 [7] 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 [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 - A, 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 - A, 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

2019 Impact Factor: 1.366