-
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.
|
| [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.
|
| [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.
|
| [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.
|
| [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] |
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 and 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 and 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 and 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 and 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 and 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 and 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] |
Ji-Bo Wang, Dan-Yang Lv, Shi-Yun Wang, Chong Jiang. Resource allocation scheduling with deteriorating jobs and position-dependent workloads. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022011 |
| [9] |
Igor E. Pritsker and Richard S. Varga. Weighted polynomial approximation in the complex plane. Electronic Research Announcements, 1997, 3: 38-44. |
| [10] |
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 |
| [11] |
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 and Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042 |
| [12] |
Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial and Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 |
| [13] |
Peter E. Kloeden, Björn Schmalfuss. Lyapunov functions and attractors under variable time-step discretization. Discrete and Continuous Dynamical Systems, 1996, 2 (2) : 163-172. doi: 10.3934/dcds.1996.2.163 |
| [14] |
Christoph Bandt, Helena PeÑa. Polynomial approximation of self-similar measures and the spectrum of the transfer operator. Discrete and Continuous Dynamical Systems, 2017, 37 (9) : 4611-4623. doi: 10.3934/dcds.2017198 |
| [15] |
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 |
| [16] |
Michele Coti Zelati. Remarks on the approximation of the Navier-Stokes equations via the implicit Euler scheme. Communications on Pure and Applied Analysis, 2013, 12 (6) : 2829-2838. doi: 10.3934/cpaa.2013.12.2829 |
| [17] |
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 |
| [18] |
Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021 |
| [19] |
Blaine Keetch, Yves van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete and Continuous Dynamical Systems - B, 2019, 24 (11) : 6091-6139. doi: 10.3934/dcdsb.2019132 |
| [20] |
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 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]