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

Xiaoli Lu, Pengzhan Huang, Yinnian He. Fully discrete finite element approximation of the 2D/3D unsteady incompressible magnetohydrodynamic-Voigt regularization flows. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 815-845. doi: 10.3934/dcdsb.2020143
[2]

Michiyuki Watanabe. Inverse $N$-body scattering with the time-dependent hartree-fock approximation. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021002
[3]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[4]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020174
[5]

Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001
[6]

Xin Guo, Lexin Li, Qiang Wu. Modeling interactive components by coordinate kernel polynomial models. Mathematical Foundations of Computing, 2020, 3 (4) : 263-277. doi: 10.3934/mfc.2020010
[7]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[8]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[9]

Jan Bouwe van den Berg, Elena Queirolo. A general framework for validated continuation of periodic orbits in systems of polynomial ODEs. Journal of Computational Dynamics, 2021, 8 (1) : 59-97. doi: 10.3934/jcd.2021004
[10]

Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389
[11]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[12]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[13]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[14]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[15]

Bilal Al Taki, Khawla Msheik, Jacques Sainte-Marie. On the rigid-lid approximation of shallow water Bingham. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 875-905. doi: 10.3934/dcdsb.2020146
[16]

P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178
[17]

Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048
[18]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[19]

François Dubois. Third order equivalent equation of lattice Boltzmann scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 221-248. doi: 10.3934/dcds.2009.23.221
[20]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (112)
  • HTML views (1167)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences