Single-Machine Scheduling with Deteriorating Processing Times and Release Dates ∗

In this paper, we consider a single-machine scheduling problem where jobs have release dates and deteriorating processing times. Formally, a set of n jobs N = {1, 2, . . . , n} is to be processed on a single machine without preemption. Let N = {1 , 2 , . . . , n } be the job set obtained from N by defining job i using the i−th largest elements in {b1 , b2 , . . . , bn } and the i−th smallest element in {r1 , r2 , . . . , rn }. Lemma 1 The optimal total completion time of the derived set N is no greater than that of job set N . Proof: Let S ∗ be an optimal schedule for 1/pi = a + bi (si − ri )/ Ci . Our proof consists of two phases. In phase one, we derive from S ∗ a schedule in which the jobs are sequenced in non-increasing order of penalty rates. Based upon this derived schedule, phase two deduces another schedule where the jobs are arranged in non-decreasing order of release dates. The derived schedule has a total completion time no greater than schedule S ∗ . Consider two consecutive jobs i and j such that i is the immediate predecessor job j and bi < bj . Denote the starting time of job i by t0 . Then, we have Ci = t0 + (a + bi (t0 − ri )), and Cj = t0 + (a + bi (t0 − ri )) + (a + bj (t0 + a + bi (t0 − ri )) − rj ). After the interchange of bi and bj without altering any other parameters, we have the following two completion times: Ci = t0 + (a + bj (t0 − ri )) , and Cj = t0 + (a + bj (t0 − ri )) + (a + bi (t0 + a + bj (t0 − ri ) − rj )). Considering Cj − Cj = (bi − bj )t0 − (bj − bi )ri + a(bi − bj ) = (bi − bj )(t0 + a − ri ) < 0, we know that the starting times of any jobs following jobs i and j will not be increased. We next consider the sum of completion times of jobs i and j:

1

= = = >

Ci + Cj − Ci − Cj 2(t0 + (a + bi (t0 − ri ))) + (a + bj (a + bi (t0 − ri )))− 2(t0 + (a + bj (t0 − ri ))) + (a + bi (a + bj (t0 − ri ))) 2(bi − bj )(t0 − ri ) + a(bi − bj ) (bi − bj )(2t0 − 2ri + a) 0.

Combining the above inequality with previous discussions, we readily that interchanging two bi and bj will not increase the total completion time. Continuing the above process, we can come up with a schedule, denoted as S , whose total completion time is no greater that Z(S). In phase two, we similarly locate two consecutive jobs i and j with ri ≥ rj . We interchange the release dates of i and j and keep all other parameters unchanged. The completion times of jobs i and j become Ci = t0 + (a + bi (t0 − rj )), and Cj = t0 + (a + bi (t0 − rj )) + (a + bj (t0 + a + bi (t0 − rj ) − ri )). 2

2

3-Partition: Given an integer M and a set A of 3m positive integers {x1 , x2 , . . . , x3m }, M/4 < xi < M/2, 1 ≤ i ≤ 3m, such that 3m xi = nM , does there exist a partition i=1 A1 , A2 , . . . , An of the set A such that |Al | = 3 and xi ∈Al xi = M, 1 ≤ l ≤ m?

3