Published on

26-Jun-2016View

213Download

1

Transcript

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

1. Introduction

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 [14].

A survey of this topic up to 1990 was given by Nowicki and Zdrzalka [11]. 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

constant.

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: lgtcheng@polyu.edu.hk (T.C.E. Cheng).

0377-2217/$ - see front matter 2003 Elsevier B.V. All rights reserved.doi:10.1016/j.ejor.2003.10.024

proce

sum

situat

times

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

rj

(Xnijai xi

)Xni1

cixi Xni1

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

further research.

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

Unsourc

while

times

amou

is evi

In

consi

W

total

releas

Proof

(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

r0j

(Xnijai xi

)Xni1

cixi Xni1

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

deration.

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 [8]. In our problem the release

follow the same linear model as that in [8], 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

Ac

Further, although an optimal solution is determined by the factors p, x and r, these factors are interrelated

the se

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

i1cixi

i1wv ri

n n"

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

Xni1

cixi Xni1

wv ri: 3i1 i1 i1

m1 m1 m m

where

Fo

If 0

where

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

Xni1

cixi wa1 x1K 0x; r;p r1 i1ai xi

i1cixi

i1wv ri

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

Xni1

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

Xni1

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

Xni1

cixi wa1 x1 2a2 x2 k 1ak1 xk1Xni1ai xi

Xni1

cixi wXm1i1ai

" xi dm

# w

Xm1i2ai

" 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

From

In

Kx;

Fo

More

strain

a lar

solut

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

Xni1

cixi Xni1

wv riXn1

ion is

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

Su

Theor

Be

comp

xi a

Proof

xh ap1

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...