| Peer-Reviewed

Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration

Received: 30 April 2014     Accepted: 20 May 2014     Published: 10 June 2014
Views:       Downloads:
Abstract

We consider several single machine scheduling problems in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time. The objectives are to minimize the functions about delivery completion times. For the former three problems, we propose polynomial-time algorithms to solve them. For the last problem, we prove that it is NP-hard when all jobs have release dates.

Published in Applied and Computational Mathematics (Volume 3, Issue 3)
DOI 10.11648/j.acm.20140303.13
Page(s) 85-89
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2014. Published by Science Publishing Group

Keywords

Scheduling, Single Machine, Delivery Time, Deteriorating jobs

References
[1] S.Browne, U.Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, vol.38, no.3, pp.495-498, 1990.
[2] G.Mosheiov, Scheduling jobs under simple linear deteri-oration, Computers Operations Research, vol.21, no.6, pp.653-659, 1994.
[3] B.Alidaee, N.K.Womer, Scheduling with time dependent processing times: Review and extension, Journal of the Operational Research Society, vol.50, no.7, pp.711-720, 1999.
[4] T.C.E.Cheng, Q.Ding, B.M.T.Lin, A concise survey of scheduling with time-dependent processing times, European Jour-nal of Operational Research, vol.152, no.1, pp.1-13, 2004.
[5] R.L.Graham, E.L.Lawler, J.K.Lenstra, A.H.G.Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, vol.5, pp. 287-326, 1979.
[6] S.Gawiejnowicz, Time-Dependent Scheduling, Springer, Berlin, 2008.
[7] E.Lodree, C.Gerger, A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration, European Journal of Operational Research, vol.201, no.2, pp.644–648, 2010.
[8] Y.Cheng, S.Sun, Scheduling linear deteriorating jobs with rejection on a single machine, European Journal of Operational Research, vol.194, no.1, pp.18–27, 2009.
[9] M.Ji, C.J. Hsu, D.L. Yang, Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, Journal of Combinatorial Op-timization, vol.26, no.3, pp.437-447,2013.
[10] X.R.Wang, J.J.Wang, Single-machine scheduling with convex resource dependent processing times and deteriorating jobs, Applied Mathematical Modelling, vol. 37, no. 4, pp. 2388-2393, 2013.
[11] D.Wang, Y. Huo, P.Ji, Single-machine group scheduling with deteriorating jobs and allotted resource, Optimization Letters, vol. 8, no.2.pp.591-605, 2014.
[12] W.C.Lee, C.C.Wu, Y.H.Chung, Scheduling deteriorating jobs on a single machine with release times, Journal Computers and Industrial Engineering, vol. 54, no.3, pp.441-452,2008.
Cite This Article
  • APA Style

    Juan Zou. (2014). Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration. Applied and Computational Mathematics, 3(3), 85-89. https://doi.org/10.11648/j.acm.20140303.13

    Copy | Download

    ACS Style

    Juan Zou. Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration. Appl. Comput. Math. 2014, 3(3), 85-89. doi: 10.11648/j.acm.20140303.13

    Copy | Download

    AMA Style

    Juan Zou. Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration. Appl Comput Math. 2014;3(3):85-89. doi: 10.11648/j.acm.20140303.13

    Copy | Download

  • @article{10.11648/j.acm.20140303.13,
      author = {Juan Zou},
      title = {Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration},
      journal = {Applied and Computational Mathematics},
      volume = {3},
      number = {3},
      pages = {85-89},
      doi = {10.11648/j.acm.20140303.13},
      url = {https://doi.org/10.11648/j.acm.20140303.13},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20140303.13},
      abstract = {We consider several single machine scheduling problems in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time. The objectives are to minimize the functions about delivery completion times. For the former three problems, we propose polynomial-time algorithms to solve them. For the last problem, we prove that it is NP-hard when all jobs have release dates.},
     year = {2014}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration
    AU  - Juan Zou
    Y1  - 2014/06/10
    PY  - 2014
    N1  - https://doi.org/10.11648/j.acm.20140303.13
    DO  - 10.11648/j.acm.20140303.13
    T2  - Applied and Computational Mathematics
    JF  - Applied and Computational Mathematics
    JO  - Applied and Computational Mathematics
    SP  - 85
    EP  - 89
    PB  - Science Publishing Group
    SN  - 2328-5613
    UR  - https://doi.org/10.11648/j.acm.20140303.13
    AB  - We consider several single machine scheduling problems in which the processing time of a job is a simple linear increasing function of its starting time and each job has a delivery time. The objectives are to minimize the functions about delivery completion times. For the former three problems, we propose polynomial-time algorithms to solve them. For the last problem, we prove that it is NP-hard when all jobs have release dates.
    VL  - 3
    IS  - 3
    ER  - 

    Copy | Download

Author Information
  • School of Management, Qufu Normal University, Rizhao, China

  • Sections