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 |
Scheduling, Single Machine, Delivery Time, Deteriorating jobs
| [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. |
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
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
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
Share This Article
Twitter
Linked In
Facebook
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}
}
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 -
Email: