J. Appl. Math. & Computing Vol. 25(2007), No. 1 - 2, pp. 305 - 314

Website: http://jamc.net

SINGLE-MACHINE SCHEDULING PROBLEMS WITH AN AGING EFFECT CHUAN-LI ZHAO∗ AND HENG-YONG TANG

Abstract. This paper considers single machine scheduling problems where the processing time of a job increases as a function of its position in the sequence. In this model, the later a given job is scheduled in the sequence, the longer its processing time. It is shown that the optimal schedule may be very different from that of the classical version of the problem. We introduce polynomial solutions for the makespan minimization problem, the sum of completion times minimization problem and the sum of earliness penalties minimization problem. For two resource constrained problems, based on the analysis of the problems, the optimal resource allocation methods are presented, respectively. AMS Mathematics Subject Classification : 90B35. Key words and phrases : Scheduling, single machine, aging, resource constrained.

1. Introduction In the classical scheduling problems it is assumed that the processing times of jobs are constant [13]. However, there are many situations where the processing times of the job may be dependent on their positions in the sequence. This phenomenon is called learning effect or aging effect. In a learning environment, the later a given job is scheduled in the sequence, the shorter its processing time; while in an aging environment, the later a given job is scheduled in the sequence, the longer its processing time. The learning effect on scheduling problem was first introduced by Biskup [2]. He solved two single machine scheduling problems. Mosheiov [8,9] continued to study Biskup’s model, and presented polynomial solutions for single machine makespan minimization problem, two for multi-criteria single machine problems and the flow time minimization problem on parallel identical machines. Mosheiov Received March 21, 2006. Revised March 7, 2007. ∗ Corresponding author. c 2007 Korean Society for Computational & Applied Mathematics.

305

306

Chuan-li Zhao and Heng-yong Tang

and Sidney [10,11] extended Biskup’s work to the case of the job-dependent learning curves, they introduced polynomial time solutions for several single machine scheduling problems. Lee et al. [6] proposed some solutions for a bi-criterion single-machine scheduling problem with learning effect. Bachman and Janiak [1] studied the single machine scheduling problems, where job processing times are defined by general functions dependent on their positions in the sequence. Wang [12] studied Flow shop scheduling jobs with position-dependent processing times. Contrast to the learning effect, to the best of our knowledge, apart from the paper of Mosheiov [9], the scheduling problem with the aging effects has not been investigated. In the last section of his paper, after introducing a polynomial time solution for the problem of minimizing sum of completion times on parallel identical machines with a learning effect, Mosheiov shows that the approach used to solve the case of learning effect remains valid for the case of aging effect. In this paper, we consider several single-machine scheduling problems with an aging effect. First we study some regular objectives. We show that the minimum makespan problem is solved by the longest processing time first (LP T ) policy. The problem to minimize sum of completion times can be solved as an assignment problem although neither LP T schedule nor SP T schedule is optimal. Two other regular objectives, minimizing maximum lateness and minimizing the number of tardy jobs, appear to be more complicated, the O(n log n) solutions of classical version do not hold for the problem with an aging effect. We then consider the problem to minimize sum of earliness penalties subject to no tardy jobs. We show that the LP T schedule is also optimal for this problem, while the SP T schedule is not optimal to minimize sum of completion times. This result implies that the scheduling problem with an aging effect have some interesting features. Finally, we study two resource constrained problems. The first one is to minimize the total resource consumption with makespan constraints, while the second is to minimize the makespan with total resource consumption constraints. The classical versions of two problems were introduced by Cheng and Janiak [3] and Janiak [4]. We show that both problems can be solved by similar approach of classical versions. 2. Regular objectives There are n jobs J1 , J2 , . . . , Jn , to be processed on a single machine. Job Jj has a normal processing time pj (without loss of generality we assume that p1 ≥ p2 ≥ . . . ≥ pn ). The normal processing time of a job is incurred if the job is scheduled first in a sequence. The processing times of the following jobs are longer than their normal processing times. Let pjr be the actual processing time of job Jj if it is scheduled in position r in a sequence. Then pjr = pj ra , j, r = 1, . . . , n.

(1)

where a > 0 is a constant aging index. For convenience, we denote single machine

Single-machine scheduling problems with an aging effect

307

scheduling with an aging effect as 1|AE|F . 2.1. Minimum makespan For the classical makespan minimization problem, the makespan value is sequence-independent. This solution does not hold for 1|AE|Cmax . Theorem 1. For problem 1|AE|Cmax , an optimal schedule can be obtained by LP T rule. Proof. Consider an optimal schedule π, suppose which is not LP T schedule. In schedule π, there must be at least two adjacent jobs, say job Jj followed by job Jk , such that pj < pk . Assume job Jj is scheduled in the position r and its starting time is t0 . Perform a adjacent pair-wise interchange on job Jj and Jk . 0 Call the new schedule π , Let Cj denote the completion time of job Jj under 0 0 schedule π, and Cj denote the completion time of job Jj under schedule π . Hence Cj = t0 + pj ra , Ck = t0 + pj ra + pk (r + 1)a ; 0

Ck = t0 + pk ra , 0

Cj = t0 + pk ra + pj (r + 1)a . So 0

Ck − Cj = (pk − pj )[(r + 1)a − ra ]. 0

Since pj < pk , a > 0, then Ck > Cj . The completion times of the jobs processed before jobs Jj and Jk is not affected by the interchange, the completion times of the jobs processed after jobs Jj and Jk is become earlier. Hence the 0 value of objective under π is strictly less than under π. This contradicts the optimality of π and proves the theorem.  2.2. Minimum sum of completion times P 1|| Cj is known to be solved by the shortest processing time first (SP T ) policy.PThe examples below shows that neither SP T nor LP T is optimal for 1|AE| Cj . Example 1. = 1.25. SP T schedule: P n = 3, p1 = 4, p2 = 3 and p3 = 2, a P [J3 , J2 , J1 ], Cj = 35.98. LP T schedule: [J , J , J ], Cj = 34.10. Optimal 1 2 3 P schedule:[J1 , J3 , J2 ], Cj = 33.30. P The problem 1|AE| Cj can be solved as an assignment problem(following Biskup[2]). 2.3. Minimum maximum lateness If dj denotes due-date of job Jj , and Lj = Cj − dj is its lateness, j = 1, . . . , n. then classical problem 1||Lmax is known to be solved by the earliest due-date

308

Chuan-li Zhao and Heng-yong Tang

first (EDD) policy. In the following example, we show that this policy is not optimal for 1|AE|Lmax . Example 2. n = 2, p1 = 1, p2 = 10, d1 = 0, d2 = 1. a = 1.25. EDD schedule: [J1 , J2 ], Lmax = 23.7. Optimal schedule: [J2 , J1 ], Lmax = 12.37. 2.4. Minimum number of tardy jobs Let Uj =P1 if Cj > dj and Uj = 0 otherwise, j = 1, . . . , n. The classical problem 1|| Uj is known to be solved by Moore’s Algorithm [7]. As a special case, it is known (Jackson [5]) that if a schedule with no tardy jobs exists, then the EDD sequence will contain no tardy jobs. P The example below shows that Jackson’s Lemma does not hold for 1|AE| Uj . Therefore, Moore’s Algorithm P is not optimal for the 1|AE| Uj . Example 3. n =P2, p1 = 1, p2 = 10, d1 = 14, d2 = P 15. a = 1.25. EDD schedule: [J1 , J2 ], Uj = 1. Optimal schedule: [J2 , J1 ], Uj = 0. 3. Minimum sum of earliness penalties If d denotes the common due date of jobs, and Ej = d − Cj is its earliness, the n X objective is to minimize g(Ej ), where g(x) is a strictly increasing function. j=1 P The problem is denoted as 1|AE| g(Ej ). A schedule is feasible if and only if there is no tardy job in the schedule. For the optimal schedule, it is obvious that (i) The last job completion time is d, (ii) There is no idle time between the jobs, the idle time can only exist before the first job. From Theorem 1, we have the following solution. P Theorem 2. For problem 1|AE| g(Ej ), an optimal schedule can be obtained n X by LP T rule,the first job starting time is d − pj j a . j=1

Proof. Consider an optimal schedule π, suppose there are two adjacent jobs Jj and Jk , job Jj followed by job Jk , such that pj < pk , job Jk is scheduled in the position r + 1 and its completion time is C0 . Perform a adjacent pair-wise 0 interchange on job Jj and Jk get a new schedule π , then we have: Ck = C0 , Cj = C0 − pk (r + 1)a , Ek = d − C0 , Ej = d − C0 + pk (r + 1)a ; 0

0

Cj = C0 , Ck = C0 − pj (r + 1)a , 0

0

Ej = d − C0 , Ek = d − C0 + pj (r + 1)a . 0

0

0

Since pj < pk , a > 0, then Ek < Ej ,g(Ej ) + g(Ek ) < g(Ek ) + g(Ej ). From Theorem 1, The completion times of the jobs processed after jobs Jj and Jk

Single-machine scheduling problems with an aging effect

309

is not affected by the interchange, the completion times of the jobs processed before jobs Jj and Jk is become larger and earliness become smaller. Hence the 0 value of objective under π is strictly less than under π. This contradicts the optimality of π and proves the theorem.  When g(x) = x,

n X j=1

g(Ej ) = nd−

n X

Cj . Since nd is a constant, then the sum

j=1

of completion times maximization problem can be solved by LP T rule, although the sum of completion times minimization problem can not be solved by SP T rule. It is implies that the problem with an aging effect has a few interesting features. 4. Resource constrained problems In this section we assume that the release time of Jj is:rj = f (uj ), α ≤ uj ≤ β, j = 1, 2, . . . , n. where uj is the amount of resources allocated to Jj , with 0 ≤ α ≤ uj ≤ β, α and β are known technological constraints and f : R+ → R+ (R+ is the set of nonnegative real numbers) is a strictly decreasing function with f (β) ≥ 0. Let π denote any schedule of jobs J1 , J2 , . . . , Jn and the job J[j] in position ˜ we denote the set of all resource j of π. We denote all schedules by Π. By U allocations u = [u1 , u2 , . . . , un ] satisfying the resource constraint (i.e., α ≤ uj ≤ n X β, j = 1, 2, . . . , n, uj ≤ U , U is the global amount of continuously divisible j=1

non-renewable resource, U ≥ nα) We consider the problem to minimize the total resource consumption with makespan constraints and the problem to minimize makespan with the resource consumption constraints. Two P problems denoted as 1|AE, rj = f (uj ), Cmax ≤ P C| uj and 1|AE, rj = f (uj ), uj ≤ U |Cmax , respectively. For the two problems, the analysis is similar to that of Cheng and Janiak [3,4] of classical versions. 4.1. Minimum resource consumption ˜ , for each job J[j] , j = Given a schedule π and a resource allocation u ∈ U 1, 2, . . . , n, the completion time C[j] (π, u) may be calculated recursively as C[1] (π, u) = f (u[1] ) + p[1] n o C[j] (π, u) = max f (u[j] ), C[j−1] (π, u) + p[j] j a , j = 2, . . . , n. Thus the completion time of Jj may also be taken as ( ) j X a p[r] r C[j] (π, u) = max f (u[i] ) + 1≤i≤j

and the makespan

r=i

310

Chuan-li Zhao and Heng-yong Tang

Cmax (π, u) = max

n

C[j] (π, u) 1≤j≤n (

= max

f (u[j] ) +

1≤j≤n

o n X

p[r] r

a

)

.

r=j

˜ , denote the total resource consumption by Also, for π ∈ Π and u ∈ U n X U (π, u) = u[j] . j=1

˜ which Let C is a given makespan, the problem is to find π ∗ ∈ Π and u∗ ∈ U ∗ ∗ minimizes the total resource consumption and Cmax (π , u ) ≤ C. Since releasing jobs sooner consumes more resources, jobs should be released as late as possible. From theorem 1,2, the jobs should be released in nonincreasing order of processing times and we need only consider the optimal resource allocation for LPT schedule, i.e., π = [J1 , J2 , . . . , Jn ]. It is obviously that there are feasible schedules if and only if n X C ≥ f (β) + pj j a j=1

and if C ≥ f (α) +

n X

pj j a , then u∗j = α, j = 1, 2, . . . , n., so we assume that

j=1

f (β) +

n X

pj j a ≤ C < f (α) +

j=1

n X

pj j a .

j=1

For π = [J1 , J2 , . . . , Jn ], we denote a resource allocation with which the resource consumption is minimized, subject to a given makespan C by u∗ , i,e.,  U (π, u∗ ) = min U (π, u) . ˜ u∈U

∗

subject to Cmax (π, u ) ≤ C. After the resource allocation u∗ is determined, the first job J1 needs to be n n X X pj j a , the second job J2 no later than C − pj j a , released no later than C − j=1

j=2

the third one J3 no later than C −

n X

pj j a , etc.

j=3

Hence, the resource allocation u∗ which minimizes the total resource consumption, subject to Cmax (π, u∗ ) ≤ C, is determined as follows: n X pj j a ≥ f (α), then (i) if C −   j=2 n X u∗1 = f −1 C − pj j a , u∗j = α, j = 2, . . . , n. j=1

Single-machine scheduling problems with an aging effect

(ii) if C −

n X

311

pj j a < f (α), let k−1 be the maximum natural number satisfying

j=2

C−

n X

pj j a < f (α).

j=k

Let d = f (α) −

C−

n X

!

pj j a , then

j=k

u∗j

=f

−1

C−

n X

pr r

a

r=j

u∗k

=f

−1

C−

n X

pr r

a

! !

=f

−1

f (α) − d −

k−1 X

pr r

a

!

, j = 1, . . . , k − 1;

r=j

= f −1 (f (α) − d),

r=k

u∗j = α, j = k + 1, . . . , n.

(2)

P Theorem 3. For the problem 1|AE, rj = f (uj ), Cmax ≤ C| uj , π ∗ ∈ Π and u∗ ∈ U is obtained by sequencing jobs in non-increasing order of processing times and allocating the resource according to (2). If we are able to calculate f , and f −1 in O(g(n)) time, then find π ∗ and u∗ needs time O(max{g(n), nlogn}). 4.2. Minimum makespan P From theorem 1-3, for problem 1|AE, rj = f (uj ), uj ≤ U |Cmax , we also need only consider the LP T schedule. For π = [J1 , J2 , . . . , Jn ], if uj = α, j = 1, 2, . . . , n, then Cmax (π, α) = f (α) +

n X

pj j a .

j=1

At this condition, r1 = r2 = . . . = rn = f (α), the makespan be constrained by r1 = f (α). If we increase the amount of resource allocated to J1 then release time r1 will be smaller and makespan be smaller too. When the C1 (π, .) = r2 = f (α), the makespan be constrained by r2 = f (α). In order to get smaller makespan, we should increase the amount of resources allocated to both J1 and J2 . When the C2 (π, .) = r3 = f (α), the makespan be constrained by r3 = f (α). In order to get smaller makespan, we should increase the amount of resources allocated to J1 ,J2 and J3 , etc. By this way, we assume that the maximal amount of resource allocated to the n X max , if u = β, then makespan is C (π, β) = f (β) + pj j a it job J1 is umax max 1 1 j=1

implies that total amount of resource can not restraints the makespan. Now we < β. consider the case at which umax 1

312

Chuan-li Zhao and Heng-yong Tang

Assume the amount of resource allocated to the job Jj is u∗j , then there must be a natural number k such that Cj (π, u∗ ) ≤ f (α), j = 1, . . . , k − 1, Cj (π, u∗ ) > f (α), j = k, . . . , n. uj = a, j = k + 1, . . . , n. Let d = f (α) − Ck−1 (π, u∗ ). Then r1∗

= f (α) − d −

k−1 X

pj j a ,

j=1

r2∗ = f (α) − d −

k−1 X

pj j a ,

j=2

... ,... , rk∗ = f (α) − d. Hence, for LPT schedule π, the resource allocation u∗ minimizing makespan is as follows. Let umax = min{U − (n − 1)α, β}. 1 (i) if f (umax ) ≥ f (α), then 1 u∗1 = U − (n − 1)α, u∗j = α, j = 2, . . . , n. (ii) if f (umax ) < f (α), then 1 u∗j

=f

−1

f (α) − d −

k−1 X

pr r

a

(3)

!

, j = 1, . . . , k − 1,

r=j

u∗k = f −1 (f (α) − d), u∗j = α, j = k + 1, . . . , n,

(4)

where k is the maximal natural number satisfying the following inequalities: ! k−1 k−1 X X f −1 f (α) − pr ra + (n − (k − 1))α ≤ U. (5) j=1

r=j

d calculated from k−1 X j=1

f −1 f (α) − d −

k−1 X

pr ra

!

+ f −1 (f (α) − d) + (n − k)α = U.

(6)

r=j

P Theorem 4. For the problem 1|AE, rj = f (uj ), uj ≤ U |Cmax , π ∗ and u∗ is obtained by sequencing jobs in non-increasing order of processing times and allocating the resource according to (3) and (4).

Single-machine scheduling problems with an aging effect

313

If we are able to calculate f , f −1 and d in O(g(n)) time, then find π ∗ and u∗ needs time O(max{g(n), nlogn}). Remark. The solutions of Theorem 3,4 are not valid for the case of learning effect since LPT schedule is not optimal for the makespan minimization with learning effect. 5. Conclusions In this paper we consider a single machine scheduling problem with an aging effect. We introduce polynomial solutions for the makespan minimization problem, the sum of completion times minimization problem, the sum of earliness penalties minimization problem. We present the optimal resource allocation methods for two resource constrained problems. For single-machine problem with a learning effect, Biskup[2] and Mosheiov[8] considered three Multi-criteria problems:(i) Minimal deviation from a common due date, (ii)A due date assignment problem, (iii) Simultaneous minimization of total completion time and n X variation of completion times. The objectives are F = (αEj + βTj + θCj ), j=1

F =

n X j=1

(αd + βEj + γTj ), and F = δ

n X

Cj + (1 − δ)

j=1

n X n X

|Ci − Cj |, respec-

i=1 j=i

tively. They shown that three problems all can be formulated as assignment problems, and have polynomial solutions. Since the actual processing time of a job is solely a function of its normal processing time and position, the approach used to solve the case of learning effect remains valid for the case of aging effect. Hence, above three Multi-criteria problems can be formulated as assignment problems and solved in the case of aging effect. Moreover, the sum of completion times minimization problem is a special case of the problem to minimize deviation from a common due date, so it is solvable. Further study includes the investigation of the multi-machine and job-shop problems with an aging effect. Acknowledgements The authors would like to thank the anonymous referees and the editors for their good comments to make this paper more readable. This work was supported by National Natural Science Foundation of China(NNSFC) 10471096 and Science and Research Project Foundation of Liaoning Province Education Department(05L417).

References 1. A. Bachman and A. Janiak, Scheduling jobs with position-dependent processing times, J. Oper. Res. Soc. 55 (2004), 257-264.

314

Chuan-li Zhao and Heng-yong Tang

2. D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res. 115 (1999), 173-178. 3. T. C. E. Cheng and A. Janiak, Resource optimal control in some single machine scheduling problem, IEEE Trans. Automat. Contr. 39 (1994), 1243-1246. 4. A. Janiak, Time-optimal control in a single machine problem with resource constraints, Automatica 22 (1986), 745-747. 5. J. R. Jackson, Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, University of California, Los Angeles 1955. 6. W-C. Lee, C-C. Wu and H-J. Sung, A bi-criterion single-machine scheduling problem with learning considerations, Acta. Inform. 40 (2004), 303-315. 7. J. M. Moore, An n job one machine sequencing algorithm for minimizing the number of late jobs, Manage. Sci. 15 (1968), 102-109. 8. G. Mosheiov, Scheduling problems with a learning effect, Eur. J. Oper. Res. 132 (2001), 687-693. 9. G.Mosheiov, Parallel machine scheduling with a learning effect, J. Oper. Res. Soc. 52 (2001), 1165-1169. 10. G. Mosheiov and B. Sidney, Scheduling with general job-dependent learning curves, Eur. J. Oper. Res. 147 (2003), 665-670. 11. G. Mosheiov and B. Sidney, Note on scheduling with general learning curves to minimize the number of tardy jobs, J. Oper. Res. Soc. 56 (2005), 110-112. 12. J-B. Wang, Flow shop scheduling jobs with position-dependent processing times, J. Appl. Math. & Computing 18 (2005), 383-391. 13. J-B. Wang, No-wait or no-idle permutation flowshop scheduling with dominating machines, J. Appl. Math. & Computing 17 (2005), 419-432. Chuan-li Zhao is a professor at the School of Mathematics and System Science, Shenyang Normal University. He received his Ph. D from the Northeastern University. His research interests focus on scheduling and combinatorial optimization. School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, P. R. China e-mail: [email protected], [email protected] Heng-yong Tang is a professor at the School of Mathematics and System Science, Shenyang Normal University. His research interests focus on stochastic programing and combinatorial optimization. School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, P. R. China e-mail: [email protected]