-
Previous Article
Optimal dividend policy with liability constraint under a hidden Markov regime-switching model
- JIMO Home
- This Issue
-
Next Article
Optimal investment and consumption in the market with jump risk and capital gains tax
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 |
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.
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. |
[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. |
[3] |
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
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. |
[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. |
[3] |
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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
Other articles
by authors
[Back to Top]