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:
[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. GrahamE. L. LawlerJ. 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. GuoW. 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. GuoW. 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. GrahamE. L. LawlerJ. 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. GuoW. 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. GuoW. 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]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044

[2]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029

[3]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[4]

Jérôme Ducoat, Frédérique Oggier. On skew polynomial codes and lattices from quotients of cyclic division algebras. Advances in Mathematics of Communications, 2016, 10 (1) : 79-94. doi: 10.3934/amc.2016.10.79

[5]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[6]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[7]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[8]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409

[9]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009

[10]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075

[11]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[12]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493

[13]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189

[14]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258

[15]

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

[16]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (118)
  • HTML views (1168)
  • Cited by (0)

Other articles
by authors

[Back to Top]