Advanced Search
Article Contents
Article Contents

Scheduling with step-deteriorating jobs to minimize the makespan

  • * Corresponding author: Email: miaocuixia@126.com

    * Corresponding author: Email: miaocuixia@126.com 
Abstract Full Text(HTML) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 90B35, 90C27.


    \begin{equation} \\ \end{equation}
  • 加载中
  • [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.
  • 加载中

Article Metrics

HTML views(2327) PDF downloads(255) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint