in which both release times and processing times are resource dependent. Such a scheduling problemcommonly arises in the chemical processing industry. Before chemical compounds (jobs) are ready for*Abstract
We consider the single machine scheduling problem with resource dependent release times and processing times, in
which both the release times and processing times are strictly linear decreasing functions of the amount of resources
consumed. The objective is to minimize the makespan plus the total resource consumption costs. We propose a heuristic
algorithm for the general problem by utilizing some derived optimal properties and analyze its performance bound. For
some special cases, we propose another heuristic algorithm that achieves a tighter performance bound.
2003 Elsevier B.V. All rights reserved.
Keywords: Scheduling; Resource dependent release times; Resource dependent processing times; Heuristics; Performance bound
The scheduling problem with resource dependent processing times has received much research attention
in recent years. Studies in this area were initiated by Vickson [15,16] and Van Wassenhove and Baker .
A survey of this topic up to 1990 was given by Nowicki and Zdrzalka . During the last decade, somenew results on these problems have appeared in the literature. They can be found in [13,5,9,12,13,17,18].
The scheduling models cited above all assume that each job is available at the beginning or its release time is
The scheduling problem with resource dependent release times has also received considerable attention
of the scheduling research community in recent years. Some research results can be found in [4,68,10]. In
these scheduling models, the jobs are each assumed to have a xed processing time.
However, to the best of our knowledge, there seem to exist no papers studying the scheduling problemDiscrete Optimization
Single machine scheduling with resource dependentrelease times and processing times
Xiuli Wang a, T.C.E. Cheng b,*
a Department of Automation, Shanghai Jiaotong University, Shanghai, PR Chinab Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
Received 29 November 2002; accepted 27 October 2003
Available online 24 December 2003
European Journal of Operational Research 162 (2005) 727739
www.elsevier.com/locate/dswCorresponding author. Tel.: +852-27665216; fax: +852-23645245.
E-mail address: firstname.lastname@example.org (T.C.E. Cheng).
0377-2217/$ - see front matter 2003 Elsevier B.V. All rights reserved.doi:10.1016/j.ejor.2003.10.024
small that it can be neglected in the objective function. Let x x1; x2; . . . ; xn denote a processing timecompression vector and r r1; r2; . . . ; rn a release time vector. Also, let X denote the set of all feasible x
728 X. Wang, T.C.E. Cheng / European Journal of Operational Research 162 (2005) 727739and R the set of all feasible r.For any job Ji, since the amount of resources consumed for its release time reduction ui, ui wv ri, is
a decreasing function of the release time ri, i 1; 2; . . . ; n, we assume that all jobs start as early as possibleafter they are released. For given p, x and r, assuming the job permutation p J1; . . . ; Jn, the objectivefunction, or total cost, Kx; r; p is dened as
Kx; r; p max16 j6 n
wv ri; 1
where ci, i 1; 2; . . . ; n, is the cost per unit processing time reduction. To simplify notation, we assume thatboth ci, 0 < ci < 1, and w, 0 < w < 1, are appropriately scaled so that their units are compatible with thatof the makespan. It is clear that max16 j6 n frj
Pnij ai xig is the makespan,
Pni1 cixi is the total
processing time compressing cost, andPn
i1 wv ri is the total release time compressing cost. Thus, theoptimal objective Kx; r; p is
This paper is organized as follows. In Section 2, we formulate the problem under study. In Section 3, we
derive some properties of an optimal solution. In Section 4, we present a heuristic algorithm for the general
problem and analyze its performance bound. In Section 5, we present a heuristic algorithm for some special
cases that yields a tighter performance bound. Section 6 concludes with a summary and suggestions for
2. Problem formulation
In this section the single machine scheduling problem is considered under the assumption that both
release times and processing times are strictly linear decreasing functions of the amount of resources
consumed. Formally, the problem can be formulated as follows.
We consider the problem of scheduling a set J fJ1; . . . ; Jng of n jobs on a single machine. Let p denotea permutation of the jobs in set J and P the set of all such permutations. All jobs are initially available attime v, but each job may be made available at an earlier time point by consuming extra resources (e.g. fuel)that will incur additional costs. Associated with each job Ji is a processing time pi and a release time ri,i 1; 2; . . . ; n, where both pi and ri depend on the amount of resources consumed. Specically, pi ai xi,where ai is the normal processing time and xi the amount of processing time compression, 06 xi6 ai;ri v ui=w, where ui is the cost of the resource consumed to advance the availability of Ji to ri and w thecost per unit reduction of release time, 06 ui6wv. For the convenience of theoretically analyzing thestudied problem, it should be noted that the case pi 0 means that the actual processing time of job Ji is soof resource consumption and the makespan, i.e., the total elapsed time to complete all jobs. Such a
ion can be modeled as our scheduling problem with resource dependent release times and processing
on a single machine.not take place. This preheating process consumes resources such as fuel and so a chemical compound is
ready earlier for processing if more fuel is consumed to preheat it. On the other hand, the processing time of
a chemical compound varies according to the speed of its chemical reaction, which is directly related to the
amount of catalysts consumed. Hence, both the job release times and processing times are variable and
depend on the amount of resources consumed. The objective of the scheduling problem is to minimize thessing, they have to be preheated to reach a temperature threshold below which chemical reactions willK x; r; p minx2X ;r2R;p2P
Kx; r; p: 2
(0 0), we can construct aolution x; r0;p with an objective function Kx; r0; p such that Kx; r0; p < Kx; r; p.vP rm am xm Dt, we set r0 r01; r02; . . . ; r0n r1 Dt; . . . ; rm Dt; rm1; . . . ; rn. Then Kx; r0;p is
Kx; r0;p max16 j6 n
wv r0i( )Lemma 1. In an optimal schedule, there exists no idle time between the rst and the last processed jobs.oblem analysis
this section we establish some properties of an optimal solution to the scheduling problem under
e rst note that if there exists idle time between the rst job and the last job in a permutation p, thecost can be reduced by eliminating the idle time through changing the actual processing times and
e times of some jobs. So we have the following lemma.3. Prder the constraint of a common deadline, the single machine scheduling problem to minimize re-e consumption, in which the job release times follow a linear model, ri v ui=w, i 1; 2; . . . ; n,the processing times are constant, is NP-hard in the ordinary sense . In our problem the release
follow the same linear model as that in , but the processing times are also linearly dependent on the
nt of resources the jobs have consumed. So the problem studied here is more dicult to deal with, and
dently NP-hard. Thus, we will focus on developing heuristic algorithms for the problem under study.X. Wang, T.C.E. Cheng / European Journal of Operational Research 162 (2005) 727739 729arizing the above discussion, the conclusion holds. h
Further, although an optimal solution is determined by the factors p, x and r, these factors are interrelated
directly aected by the integer k.
X X X
730 X. Wang, T.C.E. Cheng / European Journal of Operational Research 162 (2005) 727739 ai xi cixi wv wv a1 x1 w v ai xiK1x; r; p i1ai xi
m1#For given permutation p and x x1; x2; . . . ; xn, in view of the optimal properties of Lemmas 1 and 2, wecan determine r r1; r2; . . . ; rn using the following algorithm.
Algorithm A1Step 1. If p1 pk1 > v holds, then set r1 0; otherwise, set
r1 v p1 pk1:Step 2. If r1 0, then determine the integer m, m < k, such that p1 pm16 v < p1 pm holds.
Set r2 p1; r3 p1 p2; . . . ; rm p1 pm1; rm1 v; . . . ; rn v. Otherwise, set r2 r1p1; r3 r1 p1 p2; . . . ; rk1 r1 p1 pk2; rk r1 p1 pk1 v; rk1 v; . . . ;rn v.
According to Algorithm A1, for the case where p1 pk1 > v, the objective function K1x; r; pis
Xn Xn Xnquel that, to minimize the objective function, the optimal determination of the release time vector isin the process of searching for an optimal solution. So it is necessary to analyze the relations among these
factors in an optimal solution. In the following, we derive some optimal properties to determine the release
times for given p and x. We also develop some optimal properties to sequence jobs and determine theprocessing time compressions simultaneously.
In an optimal solution, let p denote its permutation and x its processing time compression vector. Wehave
Lemma 2. For p and x in an optimal solution, ri, i 2; . . . ; n, should satisfy the following conditions:
(i) If r1 Pi1
j1 aj xj 6 v, then ri r1 Pi1
j1 aj xj ;(ii) If r1
Pi1j1 aj xj > v, then ri v.
Proof. (i) If ri < r1 Pi1
j1 aj xj , we set Dri r1 Pi1
j1 aj xj ri, and r r1; . . . ; ri1; riDri; ri1; . . . ; rn. From (3), we have
Kx;r; p Kx; r; p wv ri Dri wv ri wDri < 0:If ri > r1
Pi1j1 aj xj , it contradicts Lemma 1.
(ii) The conclusion holds trivially. h
We assume that the constant w is such that 1k < w6 1k1, where k is an integer and k P 2. We will notice incording to Lemma 1, the objective function Kx; r; p can be re-written as
Kx; r; p r1 Xni1ai xi
wv ri: 3i1 i1 i1
m1 m1 m m
Dti K2x; r; p: 7
p1 pk16 v, and if we set v p1 pk1 < r16 v, then r1 may be denoted as p1 pk1 Dt1 Dtk1, where 0 < Dtk16 pk1, 06Dti6 pi, i 1; 2; . . . ; k 2. Ande that if Dti < pi i 2; 3; . . . ; k 1, then Dth 0 for h 1; 2; . . . ; i 1. According to Lemmas 1 2a2 x2 k 1ak1 xk1 kDtXn Xn p1 pk1 Dt, where 0 < Dt < v p1 pk1. According to Lemmas 1 and 2,1 p1; . . . ; rk1 r1 p1 pk2; rk v Dt; rk1 v; . . . ; rn v. Then the objective func-0x; r; p is
K 0x; r;p r1 Xni1ai xi
cixi wa1 x1K 0x; r;p r1 i1ai xi
K1x; r; p 1 wDt1 1 2wDt2 1 m 1wDtm1 1 mwd 0m PK1x; r; p: 6
If p1 pk16 v, and if we set 0 < r1 < v p1 pk1, then r1 may be denoted asp1 pk1 > v, and if we set 0 < r16 v, then r1 may be denoted as r1 Dt1 Dtm1 dm,06Dti6 pi, i 1; 2; . . . ;m 1, 0 < d 0m6 dm. And assume that if d 0m < dm, then Dtm1 0, and ifpi i 2; 3; . . . ;m 1, then Dth 0 for h 1; 2; . . . ; i 1. According to Lemmas 1 and 2,1 p1 Dt1; r3 r1 p1 p2 Dt1 Dt2; . . . ; rm r1 p1 pm1 Dt1 Dtm1; rm1 ; rn v. Then the objective function K 0x; r; p is
n n n vXnikai xi
cixi wa1 x1 2a2 x2 k 1ak1 xk1: 5
In Step 1 of Algorithm A1, we select the value of r1 based on the following consideration.Xni1ai xi
cixi mwdm wa1 x1
2a2 x2 m 1am1 xm1; 4dm v
Pm1i1 ai xi and 06 dm < am xm.
r the case where p1 pk16 v, the objective function K2x; r; p is
K2x; r; p r1 Xni1ai xi
cixi wa1 x1 2a2 x2 k 1ak1 xk1Xni1ai xi
" xi dm
" xi dm
wa x d wd
X. Wang, T.C.E. Cheng / European Journal of Operational Research 162 (2005) 727739 7312, r2 r1 p1 Dt1; r3 r1 p1 p2 Dt1 Dt2; . . . ; rk1 r1 p1 pk2 Dt1 ; rk v; . . . ; rn v. Then the objective function K 0x; r; p is
v a x wa x 2a x k 1a x
732 X. Wang, T.C.E. Cheng / European Journal of Operational Research 162 (2005) 727739s:t: xi6 ai; i 1; 2; . . . ; n;x1 x2 xk1 a1 ak1 v r1;xi P 0; i 1; 2; . . . ; n:
r problem P1, to minimize K1x; p, it is obvious from (4) that if iPm, Ji must be fully compressed.over, since the coecient of xi, i 1; 2; . . . ;m 1, in (4) is 1 ci iw, and under the con-t that x1 xn a1 am1 v dm, a job Ji whose processing time compression xi hasger negative coecient must be fully compressed to minimize K x; p. Specically, the optimalx1 x2 xm1 a1 am1 v dm;xi P 0; i 1; 2; . . . ; n:
Similarly, to minimize the objective function K2x; p, we can treat the processing time compressions xi,i 1; 2; . . . ; n, as decision variables and formulate the problem as a linear programming problem P2:(P2)
min K2x; pmin K1x; ps:t: xi6 ai; i 1; 2; . . . ; n;From the above discussion, we may focus our attention on analyzing the relation between a permutation
p and a processing time compression vector x in order to search for an optimal schedule. In fact, the twofactors p and x are interrelated in an optimal solution. Next, we develop an optimal property to determine xunder a given p.
For a given p J1; J2 . . . ; Jn, say, to minimize the objective function K1x; p, we can treat the pro-cessing time compressions xi, i 1; 2; . . . ; n, as decision variables and formulate the problem as a linearprogramming problem P1:
(P1)view of Theorem 1, we will denote K1x; r; p, K2x; r; p and Kx; r; p by K1x; p, K2x; p andp, respectively. Thus, the optimal objective value Kx; p is given byKx; p min
x2X ;p2PfK1x; p;K2x; pg:x; p with r determined by Algorithm A1. According to Lemmas 1 and 2 and the above discussion, we havethe following result.
Theorem 1. In an optimal solution, r r1; r2; . . . ; rn should be determined by Algorithm A1.iki i 1 1 2 2 k1 k1
1 wDt1 1 2wDt2 1 k 1wDtk1 K2x; r; p 1 wDt1 1 2wDt2 1 k 1wDtk1 PK2x; r;p: 8
(6)(8), it is evident that the search for an optimal solution can be restricted to the space of the setK 0x; r; p r1 Xni1ai xi
x1 it ind 1 1 2
~as if Ji 2 B3;where
B1 \ B2 1 2 3 1 2 k1 i 2 j 1 i s j
X. Wang, T.C.E. Cheng / European Journal of Operational Research 162 (2005) 727739 733i.
. In a solution x; r; p with objective function (4) or (5), assume that ch < w, i.e., Jh 2 N0. If we set, for the case p p > v, denote the objective function as K 0 x; r; p, and for the caseinto k subsets:
Nl fJi j lw6 ci < l 1w; Ji 2 Jg;where l 0; 1; . . . ; k 1. For a given problem, some of these subsets may be empty. From (4) and (5), wecan easily obtain the following result.
Theorem 3. In an optimal solution, a job Ji belonging t...