Optim Lett (2012) 6:87–98 DOI 10.1007/s11590-010-0253-3 ORIGINAL PAPER

Single-machine scheduling with nonlinear deterioration Ji-Bo Wang · Ming-Zheng Wang

Received: 13 April 2010 / Accepted: 15 October 2010 / Published online: 28 October 2010 © Springer-Verlag 2010

Abstract In this paper, we consider the single-machine scheduling problems with nonlinear deterioration. By the nonlinear deterioration effect, we mean that the processing times of jobs are nonlinear functions of their starting times. We show that even with the introduction of nonlinear deterioration to job processing times, single machine makespan minimization problem remains polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to job normal processing times. A heuristic algorithm utilizing the V-shaped property is proposed, and computational experiments show that it performs effectively and efficiently in obtaining near-optimal solutions. Keywords Scheduling · Single machine · Deteriorating jobs · Makespan · Total completion time 1 Introduction In many branches of industry and logistics, there arise problems of ordering jobs on machines (Pardalos and Resende [20], Setamaa-Karkkainen et al. [21], Lee and Yu [14], Hadda [11], and Gawiejnowicz [6]). Scheduling jobs with variable processing times has received increasing attention. In problems of this kind, the processing times of jobs are variable, contrary to traditional scheduling problems, where they are

J.-B. Wang School of Science, Shenyang Aerospace University, Shenyang 110136, China e-mail: [email protected] M.-Z. Wang (B) School of Management Science and Engineering, Dalian University of Technology, Dalian 116024, China e-mail: [email protected]

123

88

J.-B. Wang, M.-Z. Wang

fixed. Hence, there is a growing interest in the literature to study scheduling problems involving deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. Job deterioration appears, e.g., in scheduling maintenance jobs, steel production, national defense, emergency medicine or cleaning assignments, where any delay in processing a job is penalized by incurring additional time for accomplishing the job. Extensive surveys of different scheduling models and problems involving jobs with deterioration effect can be found in Alidaee and Womer [2], and Cheng et al. [3]. More recent papers that have considered scheduling problems with deteriorating jobs include Gawiejnowicz [7], Gawiejnowicz et al. [8], Leung et al. [15], Wang et al. [24], Wang and Xia [25], Wu et al. [27,28], Wu and Lee [26], Oron [19], Lee et al. [12,13], Tang and Liu [22], Zhu et al. [31], and Zhao and Tang [29]. We refer the reader to review Gawiejnowicz [6] for more details on scheduling problems with time-dependent processing times. According to the notion mentioned above, many scheduling problems with linear, piecewise linear or nonlinear time-dependent processing times are studied in the literature. There are many interesting efficient ordering policies provided for some scheduling problems with linear or piecewise linear processing times. However, there are less efficient rules available for those with nonlinear processing times. Only a few heuristic algorithms were proposed. For example, Gupta and Gupta [10] studied the single-machine makespan scheduling problem with nonlinear processing times. In this study, the complexity of the problem was conjectured to be NP-hard. Thus, Gupta and Gupta [10] proposed two heuristic algorithms to solve the problem. Further, Alidaee [1] proposed a more efficient heuristic algorithm to solve this problem when the polynomial function is differentiable. Kuo and Yang [18] considered some single-machine scheduling problems with nonlinear start-time dependent processing time. The objectives are to minimize the makespan and to minimize the sum of the kth powers of completion times. They proved that several cases are polynomially solvable under some restrictions of the parameters. Voutsinas and Pappis [23] introduced a new type of model where the job value deteriorates exponentially over time. Cheng et al. [4] studied scheduling problems for a set of non-preemptive jobs on single- or multi-machines without idle times where the processing time of a job is a piecewise non-increasing function of its starting time. Cheng et al. [5] studied a new scheduling model in which deteriorating jobs and learning effect are both considered simultaneously. In many realistic situations, the deterioration function of the job might nonlinear over time. For example, in steel production, more precisely, the temperature of the hot ingot on the blooming mill might drop at a slower pace as the surface cools down. In this paper, we propose a general deterioration model where the job deterioration function is a nonlinear function of its starting times. This model is adopted from Kononov and Gawiejnowicz [17] and Zhao et al. [30]. Kononov and Gawiejnowicz [17] considered the makespan minimization problem. They showed that under linear deterioration the two-machine flow shop problem is strongly NP-hard, and the two-machine open shop problem is ordinary NP-hard. They also showed that in the three-machine flow shop with simple linear deterioration (i.e., the job’s processing time is a simple linear function of its starting time), there does not exist a polynomial-time approximation algorithm with a worst-case ratio bounded by a constant. Finally, they proved

123

Single-machine scheduling with nonlinear deterioration

89

that the three-machine open shop problem with simple linear deterioration is ordinary NP-hard. Zhao et al. [30] considered the scheduling problems under linear deterioration. It is assumed that the deterioration function is a linear function. Optimal algorithms are presented respectively for single machine scheduling problems of minimizing the makespan, weighted sum of completion times, maximum lateness and maximum cost. For two-machine flow shop scheduling problem to minimize the makespan, they also proved that the optimal schedule can be obtained by Johnson’s rule. Specifically, we consider two single machine scheduling problems with nonlinear processing times. The objectives are to minimize the makespan and the total completion time of all jobs, respectively. The paper is organized as follows: In Sect. 2, we formulate the model. In Sect. 3, we consider the makespan minimization problem. In Sect. 4, we consider the total completion time minimization problem. In Sect. 5, we propose a heuristic algorithm utilized the V-shaped property for the total completion time minimization problem, and followed by a computational experiment. The last section is the summary and future research. 2 Problem formulation 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. In this paper we consider a single machine scheduling with an nonlinear processing times which is adopted from Kononov and Gawiejnowicz [17] and Zhao et al. [30]. Specially, 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. Obviously, if c = 1 the model (1) is the model of Kononov and Gawiejnowicz [17] and Zhao et al. [30]. For a given schedule π = [J1 , J2 , . . . , Jn ], C j = C j (π ) represents  the compleC j , represent tion time of job J j . Let Cmax = max{C j | j = 1, 2, . . . , n} and the makespan and the total completion time of a given permutation, respectively. In the remaining part of the paper, all the problems considered will be denoted using the three-field notation schema α|β|γ introduced by Graham et al. [9]. 3 Makespan minimization problem In this section we will consider the single-machine scheduling makespan minimization problem with nonlinear deterioration effect. First, we give some lemmas, they are useful for the following theorems. Lemma 1 (1 − (1 + x)c ) + cx(1 + x)c−1 ≥ 0 if c ≥ 1 and x ≥ 0.

123

90

J.-B. Wang, M.-Z. Wang

Proof Let h(x) = (1 − (1 + x)c ) + cx(1 + x)c−1 . By taking the first derivative of h(x) with respect to x, we have h  (x) = c(c − 1)x(1 + x)c−2 ≥ 0 for c ≥ 1 and x ≥ 0. Hence, h(x) is increasing on c ≥ 1 and x ≥ 0, and we have h(x) ≥ h(0) = 0.   Lemma 2 λ(1 − (1 + x)c ) − (1 − (1 + λx)c ) ≥ 0 if λ ≥ 1, c ≥ 1 and x ≥ 0. Proof Let f (λ) = λ(1 − (1 + x)c ) − (1 − (1 + λx)c ). Then we have f  (λ) = (1 − (1 + x)c ) + cx(1 + λx)c−1 and f  (λ) = c(c − 1)x 2 (1 + λx)c−2 ≥ 0. Hence, f  (λ) is increasing on λ ≥ 1, c ≥ 1 and x ≥ 0 for f  (λ) ≥ 0. In addition, from Lemma 1, we have f  (1) = (1 − (1 + x)c ) + cx(1 + x)c−1 ≥ 0. Therefore, f  (λ) ≥ f  (1) ≥ 0 for λ ≥ 1, c ≥ 1 and x ≥ 0. Hence, f (λ) is increasing on λ ≥ 1, c ≥ 1 and x ≥ 0. Also, f (λ) ≥ f (1) = 0 for λ ≥ 1, c ≥ 1 and x ≥ 0.   Lemma 3 λ(1 − (1 + x)c ) − (1 − (1 + λx)c ) ≤ 0 if λ ≥ 1, 0 ≤ c ≤ 1 and x ≥ 0. Proof Similarly to the proof of Lemma 2.

 

Theorem 1 For the problem 1| p Aj (t) = p j (a + bt)c |Cmax , (i) (ii)

if c ≥ 1, then an optimal schedule can be obtained by sequencing the jobs in non-decreasing order of p j (the SPT rule); if 0 ≤ c ≤ 1, then an optimal schedule can be obtained by sequencing the jobs in non-increasing order of p j (the LPT rule).

Proof Let π and π  be two job schedules where the difference between π and π  is a pairwise interchange of two adjacent jobs J j and Jk , that is, π = [S1 , J j , Jk , S2 ], π  = [S1 , Jk , J j , S2 ], where S1 and S2 are partial sequences. In addition, let t denote the completion time of the last job in S1 . To show π dominates π  (i.e., Cmax (π ) ≤ Cmax (π  )), it suffices to show that Ck (π ) ≤ C j (π  ). Under π , the completion times of jobs J j and Jk are C j (π ) = t + p j (a + bt)c and Ck (π ) = t + p j (a + bt)c + pk (a + b(t + p j (a + bt)c ))c .

123

(2)

Single-machine scheduling with nonlinear deterioration

91

Under π  , the completion times of jobs Jk and J j are Ck (π  ) = t + pk (a + bt)c and C j (π  ) = t + pk (a + bt)c + p j (a + b(t + pk (a + bt)c ))c .

(3)

Based on Eqs. (2) and (3), we have C j (π  ) − Ck (π ) = ( pk − p j )(a + bt)c + p j (a + bt + bpk (a + bt)c )c − pk (a + bt + bp j (a + bt)c )c .

(4)

(i) Suppose p j ≤ pk . By substituting x = bp j (a + bt)c−1 and λ = pk / p j , into Eq. (4), we have C j (π  ) − Ck (π ) = λ(1 − (1 + x)c ) − (1 − (1 + λx)c ). (a + bt)c p j From Lemma 2, we have C j (π  ) − Ck (π ) ≥ 0. This completes the proof of (i). (ii) From the case (i) and Lemma 3, the result can be easily obtained.   Corollary 1 For the problem 1| p Aj (t) = p j (a + bt)c |Cmax , if c = 0 or c = 1, then an optimal schedule can be obtained by sequencing the jobs in any order. 4 Total completion time minimization problem In this section we will consider the single-machine scheduling total completion time minimization problem with nonlinear deterioration effect.  Theorem 2 If c ≥ 1, then the problem 1| p Aj (t) = p j (a + bt)c | C j can be solved optimally by sequencing jobs in non-decreasing order of p j (the SPT rule). Proof It is similar to the proof of Theorem 1 except that: Suppose p j ≤ pk . Ck (π  ) + C j (π  ) − C j (π ) − Ck (π ) = ( pk − p j )(a + bt)c + ( pk − p j )(a + bt)c + p j (a + bt + bpk (a + bt)c )c − pk (a + bt + bp j (a + bt)c )c .

(5)

The term ( pk − p j )(a + bt)c in Eq. (5) is non-negative since pk − p j ≥ 0 and (a + bt)c > 0. It is also noted from Eq. (4) that the sum of the rest terms of Eq. (5) is also non-negative. Thus, we have Ck (π  ) + C j (π  ) ≥ C j (π ) + Ck (π ). This completes the proof.

 

123

92

J.-B. Wang, M.-Z. Wang

Based on Theorems 1 and 2, for the problems 1| p Aj (t) = p j (a + bt)c , c ≥ 0|Cmax  and 1| p Aj (t) = p j (a + bt)c , c ≥ 1| C j , the optimal schedules can be obtained in O(n log n) steps by a simple sorting  algorithm. However, if 0 < c < 1, then the problem 1| p Aj (t) = p j (a + bt)c | C j cannot be solved optimally by sequencing jobs in non-decreasing order of p j (SPT rule) or by sequencing jobs in non-increasing order of p j (LPT rule), the example is as follows: Example 1 n = 3, p1 = 20, p2 = 21, p3 = 22, a = 1, b = 1. When the deterio, J , J ], C j (S P T ) = 490.6725. ration index c = 0.5. The SPT sequence is [J 1 2 3  , J2 , J1 ], C j (L P T ) = 489.8772. Obviously, the optimal The LPT sequence is [J3 sequence is [J2 , J1 , J3 ], C j (O P T ) = 487.3680. From Example 1, if 0 < c < 1, we know that the classical SPT rule or LPT rule cannot give an optimal solution for the total completion time minimization problem. It remains an open problem. Now, we prove that the problem 1| p Aj (t) = p j (a+bt)c , 0 <  c < 1| C j has an important property, i.e., the optimal schedule is V-shaped with respect to the job normal processing times (see Example 1). Before the proof, we first present the definition of the V-shaped policy. Definition A schedule is V-shaped with respect to job normal processing times if jobs are arranged in descending order if they are placed before the job with the smallest p j but in ascending order if placed after it. Obviously, the SPT schedule and the LPT schedule are special cases of V-shaped property, respectively.  Theorem 3 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. Proof Consider a schedule π with three consecutive jobs, Ji , J j and Jk , i.e., π = [S1 , Ji , J j , Jk , S2 ] such that p j > pi and p j > pk . We show that an interchange between Ji and J j or between J j and Jk reduces the value of total completion time. Let π1 be the schedule obtained from π by interchanging Ji and J j , i.e., π1 = [S1 , J j , Ji , Jk , S2 ]. Similarly, let π2 be the schedule obtained from π by interchanging J j and Jk , i.e., π2 = [S1 , Ji , Jk , J j , S2 ]. Furthermore, let t denote the completion time of the last job in S1 . Then, the contribution of the three jobs to the total completion time is (π ) = 3t + 3 pi (a + bt)c + 2 p j (a + b(t + pi (a + bt)c ))c + pk (a + b(t + pi (a + bt)c + p j (a + b(t + pi (a + bt)c ))c ))c = 3t + 3 pi (a + bt)c + 2 p j (a + bt + bpi (a + bt)c )c + pk (a + bt + bpi (a + bt)c + bp j (a + bt + bpi (a + bt)c )c )c .

123

(6)

Single-machine scheduling with nonlinear deterioration

93

Similar expressions are easily obtained for π1 and π2 : (π1 ) = 3t + 3 p j (a + bt)c + 2 pi (a + bt + bp j (a + bt)c )c + pk (a + bt + bp j (a + bt)c + bpi (a + bt + bp j (a + bt)c )c )c .

(7)

(π2 ) = 3t + 3 pi (a + bt) + 2 pk (a + bt + bpi (a + bt) ) + p j (a + bt + bpi (a + bt)c + bpk (a + bt + bpi (a + bt)c )c )c .

(8)

c

c c

It follows that (π ) − (π1 ) = 3( pi − p j )(a + bt)c + 2 p j (a + bt + bpi (a + bt)c )c −2 pi (a + bt + bp j (a + bt)c )c + pk [(a + bt + bpi (a + bt)c +bp j (a + bt + bpi (a + bt)c )c )c − (a + bt + bp j (a + bt)c +bpi (a + bt + bp j (a + bt)c )c )c ]. (9) (π ) − (π2 ) = 2( p j − pk )(a + bt + bpi (a + bt)c )c + pk (a + bt + bpi (a + bt)c +bp j (a + bt + bpi (a + bt)c )c )c − p j (a + bt + bpi (a + bt)c +bpk (a + bt + bpi (a + bt)c )c )c .

(10)

Let λ = p j / pi , x = bpi (a + bt)c−1 , then from (9), we have (π ) − (π1 ) = 3 − 3λ + 2λ(1 + x)a − 2(1 + λx)a + pk [(a + bt + bpi (a + bt)c (a + bt)c pi +bp j (a + bt + bpi (a + bt)c )c )c − (a + bt + bp j (a + bt)c +bpi (a + bt + bp j (a + bt)c )c )c ]. (11) Let μ = p j / pk , θ = bpk (a + bt + bpi (a + bt)c )c−1 , then from (10), we have (π ) − (π2 ) = 2μ − 2 + (1 + μθ )a − μ(1 + θ )a . pk (a + bt + bpi (a + bt)c )c

(12)

From Theorem 1, we have pk [(a + bt + bpi (a + bt)c + bp j (a + bt + bpi (a + bt)c )c )c − (a + bt + bp j (a + bt)c + bpi (a + bt + bp j (a + bt)c )c )c ] ≥ 0. Now let (π ) − (π1 ) be negative, from (11), we have 3 − 3λ + 2λ(1 + x)a − 2(1 + λx)a < 0 ⇒ 2 − 2λ + λ(1 + x)a − (1 + λx)a + [1 − λ + λ(1 + x)a − (1 + λx)a ] < 0 ⇒ 2 − 2λ + λ(1 + x)a − (1 + λx)a < 0 (from Lemma 3) ⇒ 2μ − 2 + (1 + μθ )a − μ(1 + θ )a > 0. Hence, we have (π ) − (π2 ) > 0.

123

94

J.-B. Wang, M.-Z. Wang

Now let (π ) − (π2 ) be negative, from (12) and Lemma 3, we have 2μ − 2 + (1 + μθ )a − μ(1 + θ )a < 0 ⇒ 2μ − 2 + (1 + μθ )a − μ(1 + θ )a + [μ − 1 + (1 + μθ )a − μ(1 + θ )a ] + pk [(a + bt + bp j (a + bt)c + bpi (a + bt + bp j (a + bt)c )c )c −(a + bt + bpi (a + bt)c + bp j (a + bt + bpi (a + bt)c )c )c ] < 0 ⇒ 3μ − 3 + 2(1 + μθ )a − 2μ(1 + θ )a + pk [(a + bt + bp j (a + bt)c + bpi (a + bt + bp j (a + bt)c )c )c −(a + bt + bpi (a + bt)c + bp j (a + bt + bpi (a + bt)c )c )c ] < 0 ⇒ 3 − 3λ + 2λ(1 + x)a − 2(1 + λx)a + pk [(a + bt + bpi (a + bt)c + bp j (a + bt + bpi (a + bt)c )c )c −(a + bt + bp j (a + bt)c + bpi (a + bt + bp j (a + bt)c )c )c ] > 0. Hence, we have (π ) − (π2 ) > 0. We conclude that an optimal schedule exists which is V-shaped with respect to the job normal processing times.   We can easily prove that Theorem 3 remains valid when the performance measure is extended to any linear combination of makespan and total completion time.  Corollary 2 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.

5 The heuristic algorithm for 1| p Aj (t) = p j (a + bt)c , 0 < c < 1|



Cj

For the classical completion time variance minimization problem, Kanet [16] made use of the V-shaped property and presented a heuristic algorithm to solve it. From Example 1, if 0 < c < 1, we know that the classical SPT rule or LPT rule cannot give an optimal solution for the total completion time minimization problem. In spite of many efforts, the complexity of this problem remains open. In this section, we propose  a heuristic algorithm to solve the problem 1| p Aj (t) = p j (a + bt)c , 0 < c < 1| C j . The procedure in Phase I is adopted from Kanet [16] idea to obtain a near optimal solution. To further improve the quality of the solution, a pair-wise interchanging movement to exchange jobs from two edges of the V-shape is conducted in the second phase of the algorithm. However, if the derived sequence is not a V-shape after the exchange movement, then the calculation of the total completion time is skipped to reduce the computational effort. In summary, the procedure of the heuristic algorithm is stated as follows:

123

Single-machine scheduling with nonlinear deterioration

95

Algorithm 1 Phase I Step 1 Choose the job J j with the smallest normal processing time p j in J and label it as job Jk . Step 2 Remove the largest normal processing time job from J and label it job Ji , and create a partial schedule S with only job Jk . Step 3 Insert job Ji to the immediate left of job Jk and create a partial schedule S  . Insert job Ji to the immediate right of job Jk and create a partial schedule S  . From S  and S  , choose the schedule with a smaller total completion time as the new schedule S. Delete job Ji from J . Step 4 If J is not empty, go to step 2. Otherwise, stop.

Phase II Step 1 Let S0 be the initial schedule obtained from Phase I, and v is the position of the job with the smallest pk . Step 2 Set i = 1. Step 3 If i < v, go to Step 4. Otherwise, stop. Step 4 Set j = v + 1. Step 5 If j <= n, go to Step 6. Otherwise, go to Step 8. Step 6 Create a new sequence S1 by interchanging jobs in positions i and j. If S1 is not V-shaped, go to Step 7. Otherwise, replace S0 by S1 if the value of the total completion time of S1 is smaller than that of S0 . Step 7 Set j = j + 1, go to Step 5. Step 8 Set i = i + 1, go to Step 3. To test the performance of Algorithm 1, a computational experiment was conducted. The Algorithm 1 was coded in VC++ 6.0 and the computational experiments were run on a Pentium 4 personal computer with a RAM size of 1 G. The test problems was generated as follows. For each job J j , the job normal processing time p j were generated from a uniform distribution over the integers between 1 and 100. For each Algorithm 1, 6 different job sizes (n=10, 12, 14, 16, 18, 20, 22, 24, 26, 28 and 30), a = b = 1 and five different deterioration rates (c = 0.05, 0.25, 0.45, 0.65, and 0.85) were used. As a consequence, 18 experimental conditions were examined and 50 replications were randomly generated for each condition. A total of 2,750 problems were tested. In order to test the performance of Algorithm 1 relative to the optimal solutions where the optimal solution is obtained by enumerative algorithm (the existence of an optimal V-shaped schedule reduces the number of candidates for the optimal schedule to O(n 2 )). We did not try to optimize the running time of the enumerative algorithm, since our main goal was to evaluate the performance of the heuristics by comparing the heuristic solutions with the optimal solutions. For Algorithm 1, the average CPU time (ms), average and maximum error percentage were recorded. The percentage error

123

123

0.0000

0.0000

0.3200

1.6000

1.5000

1.6000

1.7100

1.7600

1.8200

1.8500

1.9200

12

14

16

18

20

22

24

26

28

30

0.0096

0.0097

0.0098

0.0093

0.0091

0.0086

0.0084

0.0044

0.0034

0.0032

0.0006

0.0292

0.0291

0.0286

0.0265

0.0236

0.0201

0.0196

0.0192

0.0189

0.0261

0.0132

0.0510

0.0410

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

CPU time

max

CPU time

mean

c = 0.25

c = 0.05

10

n

Table 1 The error percentages of Algorithm 1

0.0094

0.0096

0.0095

0.0096

0.0093

0.0091

0.0081

0.0039

0.0065

0.0054

0.0049

mean

0.0399

0.0387

0.0397

0.0392

0.0379

0.0368

0.0339

0.0097

0.0293

0.0359

0.0362

max

0.0780

0.0210

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

CPU time

c = 0.45

0.0080

0.0075

0.0079

0.0071

0.0069

0.0075

0.0064

0.0027

0.0038

0.0065

0.0056

mean

0.0311

0.0299

0.0298

0.0289

0.0284

0.0223

0.0204

0.0149

0.0226

0.0279

0.0160

max

0.3400

0.2300

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

0.0000

CPU time

c = 0.65

0.0151

0.0154

0.0143

0.0132

0.0123

0.0105

0.0095

0.0092

0.0156

0.0096

0.0018

mean

0.0461

0.0453

0.0426

0.0407

0.0397

0.0376

0.0367

0.0201

0.0848

0.0621

0.0216

max

0.3200

0.4100

0.2200

0.0000

0.0000

0.0000

0.0000

0.0000

0.3200

0.3000

0.0000

CPU time

c = 0.85

0.0165

0.0152

0.0125

0.0112

0.0191

0.0168

0.0151

0.0184

0.0182

0.0136

0.0161

mean

0.0661

0.0491

0.0442

0.0621

0.0702

0.0897

0.0486

0.0553

0.0878

0.0773

0.0451

max

96 J.-B. Wang, M.-Z. Wang

Single-machine scheduling with nonlinear deterioration

97

of the solution produced by the heuristic algorithm is calculated as (Heur-Opt)/Opt, where Heur is the total completion time of the solution generated by Algorithm 1 and Opt is the total completion time of the optimal schedule. From Table 1, we see that for all cases the average error percentages of Algorithm 1 are always less than 2%, and the average CPU time used to solve the biggest testing problem would not be more than 1.92 ms. Moreover, it can be observed that, for cases c = 0.05, 0.25, 0.45 and 0.65, the proposed Algorithm 1 give better results, and for case c = 0.85, the proposed Algorithm 1 give worse results. This suggests that the performance of Algorithm 1 is effective and efficient. 6 Summary and future research In this paper we have studied a new type of scheduling problems with nonlinear deterioration. We showed that the makespan minimization problem and the total completion time minimization problem for c ≥ 1 can be optimally solved. However the optimal job sequence of the total completion time minimization problem is still unknown if 0 < c < 1, but we proved that the optimal sequence has a V-shaped property with respect to the normal processing times. It is clearly worthwhile for future research to investigate this open problem, consider the nonlinear deterioration effect in the context of other scheduling problems, for example, flow shop scheduling problem, study the other objective functions, or propose more sophisticated and efficient heuristics. Acknowledgments We are grateful to an anonymous referee for his/her helpful comments on an earlier version of this paper. This research was supported by the National Natural Science Foundation of China (Grant No. 11001181 and 71031002).

References 1. Alidaee, B.: A heuristic solution procedure to minimize makespan on a single machine with non-linear cost functions. J. Oper. Res. Soc. 41, 1065–1068 (1990) 2. Alidaee, B., Womer, N.K.: Scheduling with time dependent processing processing times: review and extensions. J. Oper. Res. Soc. 50, 711–720 (1999) 3. Cheng, T.C.E., Ding, Q., Lin, B.M.T.: A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152, 1–13 (2004) 4. Cheng, T.C.E., Ding, Q., Kovalyov, M.Y., Bachman, A., Janiak, A.: Scheduling jobs with piecewise linear decreasing processing times. Naval Res. Logist. 50(6), 531–554 (2003) 5. Cheng, T.C.E., Wu, C.C., Lee, W.C.: Some scheduling problems with deteriorating jobs and learning effects. Comput. Ind. Eng. 54, 972–982 (2008) 6. Gawiejnowicz, S.: Time-dependent scheduling. Springer, Berlin (2008) 7. Gawiejnowicz, S.: Scheduling deteriorating jobs subject to job or machine availability constraints. Eur. J. Oper. Res. 180, 472–478 (2007) 8. Gawiejnowicz, S., Kurc, W., Pankowska, L.: Pareto and scalar bicriterion optimization in scheduling deteriorating jobs. Comput. Oper. Res. 33, 746–767 (2006) 9. Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979) 10. Gupta, J.N.D., Gupta, S.K.: Single facility scheduling with nonlinear processing times. Comput. Ind. Eng. 14, 387–393  (1998) 11. Hadda, H.: A 43 -approximation algorithm for a special case of the two machine flow shop problem with several availability constraints. Optim. Lett. 3, 583–592 (2009)

123

98

J.-B. Wang, M.-Z. Wang

12. Lee, W.-C., Wu, C.-C., Chung, Y.-H., Liu, H.-C.: Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates. Comput. Oper. Res. 36, 2111–2121 (2009) 13. Lee, W.-C., Wu, C.-C., Wen, C.-C., Chung, Y.-H.: A two-machine flowshop makespan scheduling problem with deteriorating jobs. Comput. Ind. Eng. 54, 737–749 (2008) 14. Lee, C.-Y., Yu, G.: Parallel-machine scheduling under potential disruption. Optim. Lett. 2, 27–37 (2008) 15. Leung, J.Y.T., Ng, C.T., Cheng, T.C.E.: Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times. Eur. J. Oper. Res. 187, 1090–1099 (2008) 16. Kanet, J.J.: Minimizing variation of flow time in single machine systems. Manage. Sci. 27(12), 1453–1459 (1981) 17. Kononov, A., Gawiejnowicz, S.: NP-hard cases in scheduling deteriorating jobs on dedicated machines. J. Oper. Res. Soc. 52, 708–717 (2001) 18. Kuo, W.-H., Yang, D.-L.: Single-machine scheduling problems with start-time dependent processing time. Comput. Math. Appl. 53, 1658–1664 (2007) 19. Oron, D.: Single machine scheduling with simple linear deterioration to miminize total absolute deviation of completion times. Comput. Oper. Res. 5, 2071–2078 (2008) 20. Pardalos, P.M., Resende, M.G.C.: Handbook of Applied Optimization. Oxford University Press, Oxford (2002) 21. Setamaa-Karkkainen, A., Miettinen, K., Vuori, J.: Heuristic for a new multiobjective scheduling problem. Optim. Lett. 1, 213–225 (2007) 22. Tang, L., Liu, P.: Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration. Appl. Math. Model. 33, 1187–1199 (2009) 23. Voutsinas, T.G., Pappis, C.P.: Scheduling jobs with values exponentially deteriorating over time. Int. J. Prod. Econ. 79, 163–169 (2002) 24. Wang, J.-B., Ng, C.T., Cheng, T.C.E., Liu, L.L.: Minimizing total completion time in a two-machine flow shop with deteriorating jobs. Appl. Math. Comput. 180, 185–193 (2006) 25. Wang, J.-B., Xia, Z.-Q.: Flow shop scheduling with deteriorating jobs under dominating machines. Omega 34, 327–336 (2006) 26. Wu, C.-C., Lee, W.-C.: Single-machine group-scheduling problems with deteriorating setup times and job-processing times. Int. J. Prod. Econ. 115, 128–133 (2008) 27. Wu, C.-C., Lee, W.-C., Shiau, Y.-R.: Minimizing the total weighted completion time on a single machine under linear deterioration. Int. J. Adv. Manuf. Technol. 33, 1237–1243 (2007) 28. Wu, C.-C., Shiau, Y.-R., Lee, W.-C.: Single-machine group scheduling problems with deterioration consideration. Comput. Oper. Res. 35, 1652–1659 (2008) 29. Zhao, C.-L., Tang, H.-Y.: A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints. Optim. Lett. (2010). doi:10.1007/s11590-010-0202-1 30. Zhao, C.-L., Zhang, Q.-L., Tang, H.-Y.: Scheduling problems under linear deterioration. Acta Autom. Sin. 29, 531–535 (2003) 31. Zhu, V.C.Y., Sun, L., Sun, L., Li, X.: Single machine scheduling time-dependent jobs with resourcedependent ready times. Comput. Ind. Eng. 58, 84–87 (2010)

123