Optim Lett (2012) 6:825–826 DOI 10.1007/s11590-011-0295-1 SHORT COMMUNICATION

A note on single-machine scheduling with nonlinear deterioration Xiao-Yuan Wang · Dan Wang · Na Yin

Received: 6 November 2010 / Accepted: 8 February 2011 / Published online: 18 February 2011 © Springer-Verlag 2011

Abstract Some results in a recent paper (Wang and Wang in Optim Lett doi:10. 1007/s11590-010-0253-3) are incorrect because job processing times are variable due to nonlinear deterioration. In this note, we show by a counter-example that the results are incorrect. Keywords

Scheduling · Single machine · Deteriorating jobs

1 Introduction The recent paper “Single-machine scheduling with nonlinear deterioration” (Wang and Wang [1]) addresses the single-machine scheduling problems with nonlinear deterioration. The authors showed that even with the introduction of nonlinear deterioration to job processing times, single machine makespan minimization problem remains polynomially solvable. They also showed that an optimal schedule of the total completion time minimization problem is V-shaped with respect to job normal processing times. In this note we will give a counter-example to show the incorrectness of V-shape policy in Wang and Wang [1]. We shall follow the notations and terminologies given in Wang and Wang [1]. There are given a single machine and a set J = {J1 , J2 , . . . , Jn } of n independent and non-preemptive jobs. All jobs are available for processing at time 0. The machine can handle one job at a time and preemption is not allowed. Let p Aj (t) be the actual processing time of job J j if it is started at time t in a sequence. As in Wang and Wang

X.-Y. Wang (B) · D. Wang · N. Yin School of Science, Shenyang Aerospace University, Shenyang 110136, China e-mail: [email protected]

123

826

X.-Y. Wang et al.

[1], we consider a general nonlinear processing times model as follows: p Aj (t) = p j (a + bt)c ,

(1)

where p j is the normal (basic) processing time of job J j , a ≥ 0, b ≥ 0 and c ≥ 0 is the deterioration index.  For a given schedule π = [J1 , J2 , . . . , Jn ], Let C j = C j (π ), Cmax and C j be the completion time of job J j , the makespan and the total completion time of a given permutation, respectively. 2 A counter-example Wang and Wang [1] gave the following result. Theorem 1 (Theorem 3, Wang and Wang [1]). For the problem 1| p Aj (t) = p j (a +  bt)c , 0 < c < 1| C j , an optimal schedule exists which is V-shaped with respect to the job normal processing times. Corollary 1 (Corollary 2, Wang and Wang [1]). For the problem 1| p Aj (t) = p j (a +  bt)c , 0 < c < 1|αCmax + β C j , where α ≥ 0, β ≥ 0, an optimal schedule exists which is V-shaped with respect to the job normal processing times. The following example shows that Theorem 1 and Corollary 1 are incorrect. Counter-example 1 n = 5, p1 = 1, p2 = 63, p3 = 66, p4 = 75, p5 = 97. When the a = b = 1 and c = 0.45. By  the enumerative algorithm, we know that the optimal C j (O P T ) = 6631.554678.Obviously, the optisequence is [J5 , J1 , J3 , J2 , J4 ], mal schedule of problem 1| p Aj (t) = p j (a + bt)c , 0 < c < 1| C j is not V-shaped with respect to the job normal processing times.  Note that the problem 1| p Aj (t) = p j (a + bt)c , 0 < c < 1| C j is a special case  of the problem 1| p Aj (t) = p j (a + bt)c , 0 < c < 1|αCmax + β C j . Therefore, Corollary 2 in Wang and Wang [1] is also not correct. Acknowledgments This research was supported by the National Natural Science Foundation of China under grant number 11001181.

Reference 1. Wang, J.-B., Wang, M.-Z.: Single-machine scheduling with nonlinear deterioration. Optim. Lett. doi:10. 1007/s11590-010-0253-3

123