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
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.
Single Machine Scheduling Problems with Delivery Times under Simple Linear Deterioration, Applied and Computational Mathematics.
Vol. 3, No. 3,
2014, pp. 85-89.
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.