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

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

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

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

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

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

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

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

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

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

Igor E. Pritsker and Richard S. Varga. Weighted polynomial approximation in the complex plane. Electronic Research Announcements, 1997, 3: 38-44.

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Chuang Peng. Minimum degrees of polynomial models on time series. Conference Publications, 2005, 2005 (Special) : 720-729. doi: 10.3934/proc.2005.2005.720

[19]

Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial & Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867

[20]

Lihui Zhang, Xin Zou, Jianxun Qi. A trade-off between time and cost in scheduling repetitive construction projects. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1423-1434. doi: 10.3934/jimo.2015.11.1423

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (15)
  • HTML views (211)
  • Cited by (0)

Other articles
by authors

[Back to Top]