Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration
Applied and Computational Mathematics
Volume 3, Issue 3, June 2014, Pages: 85-89
Received: Apr. 30, 2014; Accepted: May 20, 2014; Published: Jun. 10, 2014
Views 3177      Downloads 150
Juan Zou, School of Management, Qufu Normal University, Rizhao, China; School of Mathematical Sciences, Qufu Normal University, Qufu, China
Article Tools
Follow on us
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.
Scheduling, Single Machine, Delivery Time, Deteriorating jobs
To cite this article
Juan Zou, Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration, Applied and Computational Mathematics. Vol. 3, No. 3, 2014, pp. 85-89. doi: 10.11648/j.acm.20140303.13
S.Browne, U.Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, vol.38, no.3, pp.495-498, 1990.
G.Mosheiov, Scheduling jobs under simple linear deteri-oration, Computers Operations Research, vol.21, no.6, pp.653-659, 1994.
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.
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.
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.
S.Gawiejnowicz, Time-Dependent Scheduling, Springer, Berlin, 2008.
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.
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.
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.
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.
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.
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.
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
Tel: (001)347-983-5186