算法高級(jí)教程3.2theschedulingproblem

This

is

the

how

we

intend

to

tackle

the

job

shop

schedulingproblem.Read

the

slideOverview1What

are

we

talking

about

?The

Problem,

Its

context,

Applications,

importaManagement

ScienceOperation

ResearchApplicationsAssembly

linesMulti-processor

/

Multi-server

schedulingPacket

SchedulingOk,

the

problem.%Read

slide,

stress

on

the

highlighted

termsJSSP,

here

on

I’ll

use

this

acronymMakespan,

we’ll

see

what

this

is

in

a

momentWe’ll

understand

why

approximationThe

problemWe

have

a

set

of

n

jobs

J1,

..Jn

and

m

machines.M1,

...,Mm.

Each

job

Jj

must

be

processedwithout

interruption

for

a

time

pj>

0

on

one

ofthe

m

machines,

each

of

which

can

process

atmost

one

job

at

a

time.A

Schedule

is

an

assignment

of

operations

totime

slots

on

the

machines2Makespan

(C*Max)

It

is

the

maximumcompletion

time

of

the

Activities*Means

optimalCMax

=

maxi,j

C*j

is

its

optimal

valueRead

slideThis

is

an

illustration

of

a

scheduleA

job

1

has

4

operationsJob2

has2

operations

andjob

3

has

3

operationsThe

operations

cannot

overlap.The

operations

of

a

job

have

a

fixed

orderFor

example3The

JSSP

belongs

to

a

broader

class

of

problems

called

the

General

shop

schedulingproblemRead

the

slideThe

General

Shop

Scheduling

Problem4You

are

given

a

set

of

operations

OAll

operations

o

in

O

have

a

processing

time

po

Objective

is

to

find

a

schedule

that

meet

specifiedcriteriaO

is

partitionedinto

subsets

M

=

{M1,...,

Mm}

(machines)and

into

subsets

J

=

{J1,...,

Jn}

(jobs).We

need

to

introduce

the

notation

fromshop

scheduling

problembecausewe

will

use

this

often

to

succinctly

describe

shop

schedulingproblems

that

weAre

aboutto

explainα:

Machine

Environment

:

o

(dedicated)

,

I

(Identical

parallel)

,

Q

(Uniform

Parallel)

,

R

(Unrelated

Parallel)

,PMPM,

QMPM,

G

(General

Shop),

X

(Mixed

Shop)

,

O

(Open

Shop)

,

J

(Job

Shop)

,

F

(Flow

Shop),β:

Job

Characteristics

:(preemption,

non-preemption),

(precedence/tree/series/parallel),

(release

dates),

(processing

times),

(deadlines),(batching)γ:

Optimality

Criteria

:

(Lateness,

Earliness,

Tardiness,

Absolute

deviation,

Squared

Deviation,

Unit

Penalty),

maximumlateness,

regular

activeThe

α|β|γ

Notation5α:

Machine

Environment

I

(Identical

parallel)

,

G

(General

Shop)

,

O

(Open

Sho(Job

Shop)

,

F

(Flow

Shop),

1(Single

machine),…β:

Job

Characteristics

(preemption,

non-preemption),(precedence/tree/series/parallel),

(release

dates/du(processing

times),

(deadlines),

(number

of

operationeach

job)γ:

Optimality

Criteria(

CMax

MinimumMakespan

),

(

LMax

Minimim

Max-Lateness

) (Wmin

Weighted

Completion

Time)So

this

is

the

notation

for

the

JSSP,

this

readsJob

shop

withnmachines,

no

pre-emptionoptimizing

the

MakespanAnd

this

specifies

that

we

are

tackling

aspecific

kind

of

the

shop

scheduling

problemso

to

say

it

againRead

slideFor

example:

JSSP

(

Jn||CMax

)6n

jobsm

“identical”

“capacity

1”

machines

A

job

is

give

by

a

“set

of

operations”

to

beperformed

in

a

given

order

Goal:

Find

a

schedule

that

minimizes

theMakespanRead

slideHow

hard

is

this

problem7

The

classic

MT10

problem

proposed

in

1963wassolveafter

25

years

JSSP

is

not

only

NP

hard

but

also

know

to

be

the

worsmember

of

its

class

An

n×m

size

JSSP

has

an

upper

bound

of

(n!)m.

Thus

a20×10

problem

can

have

at

most

7.2651×10183

possibsolutions.

It

has

been

proved

that

if

a

solution

exists

for

theshop

with

an

approximation

ratio

better

than

5/4

thP=NPIdentical

parallel

problem8The

problemWe

have

a

set

of

n

jobs

J1,

..Jn

and

m

machines

M1,

...,Mm.

Each

job

Jj

must

be

processed

wit

interruption

for

a

time

tj

>

0

on

one

of

the

m

machines,

each

of

which

can

process

at

most

job

at

a

time.This

problem

is

strong

NP-hard.List

scheduling

(LS)Whenever

a

machine

becomes

available

the

next

job

onthe

list

is

assigned

to

begin

processing

on

that

macM1M2J1

J4J2

J3J5J6Cmax9List:

J1,

J2

,J3

,J4

,

J5

,

J6ListScheduling()105while

the

list

is

not

empty

dotake

the

next

job

j

from

the

head

of

the

listdelete

j

from

the

list

find

the

machine

m

with

the

least

amount

of

workassigned

to

it

so

farassign

j

to

m6

return

the

schedule

so

obtainedFor

exampleExample:

(t1,

t2,

.

.

.

,

tn)

=

(10,

8,

7,

5,

3,

1)List

scheduling

can

obtain

makespan

18The

optimal

schedule

is

1711

Lemma

3.2.1

LS

operates

in

O(nlogm)

time

in

theworst

case.Proof:

Finding

the

machine

with

the

least

amount

owork

assigned

to

it

can

be

done

by

maintaining

a

headata

structure

with

the

total

amounts

of

work

assigto

each

machine

so

far.

Finding

the

machine

with

thleast

amount

of

work

so

far

can

be

done

in

constanttime,

since

it

is

at

the

top

of

the

heap.

It

must

bedeleted

from

the

heap,

and

the

processing

time

of

tnew

task

must

be

added

to

the

total

work

assigned

tothe

machine

so

far

and

the

new

total

must

be

inserteback

into

the

heap.

These

actions

cost

O(1),

O(1)

aO(logm)

respectively.1213Theorem

3.2.1

List

scheduling

achieves

a

performanratio

2?1/m.Proof:

Let

T

=

∑ti,

i=1,2…,n,

the

sum

of

all

procestimes

to

be

accommodated.

We

know

that

the

totalprocessing

time

available

in

an

optimal

schedule

onMoreovermachines

is

m

·

OPT(I).

So,

OPT(I)≥T/m.OPT(I)≥tk

for

every

k.

Let

A(I)

be

the

makespan

of

the

schedule

produced

byLS.

By

definition

there

must

be

a

job

k,

with

processtime

tk,

that

ends

at

the

makespan

time.

No

machine

cend

its

operation

before

A(I)

?tk,

because

then

jobwould

have

been

scheduled

on

that

machine,

thusreducing

the

makespan.MiMmkA(I)T-tk≥m(A(I)?tk),So,

A(I)

≤T/m+tk

(m-1)/m≤

OPT(I)

+(1-1/m)

OPT(I)

=(2-1/m)OPT(I)M1A(I)

?tk14So

all

machines

are

busy

from

time0

through

A(I)

?tk.

Consequently,The

LPT

rule15

List

scheduling

can

do

badly

if

long

jobs

at

the

endthe

list

spoil

an

even

division

of

processing

timesWe

now

assume

that

the

jobs

are

all

given

ahead

of

ti.e.

the

LPT

rule

works

only

in

the

off-line

situatConsider

the

“Largest

Processing

Time

first”

orrule

that

works

as

follows.LPT(I)16sort

the

jobs

in

order

of

decreasing

processing

time≥

.

.

.

≥

tnexecute

list

scheduling

on

the

sorted

listreturn

the

schedule

so

obtained.

Theorem

3.2.2

The

LPT

rule

achieves

a

performanceratio

4/3-1/(3m).Proof:

We

will

construct

a

proof

by

contradiction.Assume

that

4/3

?

1/(3m)

is

not

a

valid

bound

on

theperformance

ratio.

Let

I

be

an

instance

with

thesmallest

number

of

jobs

such

that

the

LPT

schedulefor

I

has

a

makespan

>

(4/3-1/(3m))

OPT(I)

,Wedistinguish

two

cases:17Case

1:

tn≤OPT(I)

/3

.

Consider

a

job

j

that

finishesthe

makespan

A(I)

and

suppose

j≠n.18Consider

the

instance

I

"

equal

to

I

without

job

n.

TI

"

is

a

smaller

instance

than

I

for

which

the

LPT

rulcomputes

a

makespan>(4/3

?1/(3m))

OPT(I)

,

becausethe

completion

time

of

the

LPT

schedule

for

I

"

is

alequal

to

A(I)

and

A(I)

>

(4/3

?1/(3m))

OPT(I)

>(4/31/(3m))

OPT(I

").

This

contradicts

the

choice

of

I.can

assume

that

j

=

n.

Then

by

an

argument

which

issimilar

to

the

proof

of

Theorem

3.2.1

we

have:A(I)

≤T/m+tn

(m-1)/m19≤

OPT(I)

+(1-1/m)

OPT(I)

/3=(4/3-1/(3m))

OPT(I)Which

completes

the

proof

for

case

1.Case

2:

tn>

OPT(I)

/3.

Consider

the

optimum

schedulwith

makespan

OPT.

There

can

clearly

be

no

more

than2

jobs

per

machine.

Normalize

the

optimum

scheduleas

follows:if

a

machine

has

two

jobs

place

the

longest

first,sort

the

machines

so

that

the

first

jobs

are

indescending

order

of

processing

time.

If

n≤m,

then

normalize

further

and

spread

the

jobseach

machine

can

be

assumed

to

have

at

most

one

job.One

easily

sees

that

the

LPT

rule

gives

a

scheduleequivalent

to

this,

thus

with

makespan

A(I)<

(

4/3?1/(3m))OPT(I)

,

contradiction

the

assumption.

If

n>m.

This

means

that

some

machines

must

have

2jobs

assigned

to

them.

Without

loss

of

generality

wmay

assume

that

every

machine

has

two

jobs

assignedto

it

(e.g.

by

adding

dummy

jobs

with

processing

tim0).20

We

will

again

normalize

the

optimum

schedule

furthe

Let

the

first,

thus

longest

job

of

machine

m

be

the

j

with

processing

time

tk.

Note

that

this

job

is

the

sh

of

the

jobs

in

first

place

on

any

machine.Suppose

there

is

another

machine

h

with

first

job

tisecond

job

tj

,

such

that

tj

>

tk.21

We

can

interchange

jobs

j

and

k

and

keep

an

optimal

schedule!

For,

tk<tj

so

ti+tk≤OPT(I)

onmachine

h.

Onmachine

m

we

have

jobs

tj

and

tl.Necessarily

tj

+

tl≤OPT(I),

because

ti+tj≤OPT(I)and

tl

≤

tk

<

tj

≤

ti.iMhklMmj22

By

iterating

exchanges

of

this

kind,

itfollows

that

there

is

an

optimumsolution

in

which

the

m

biggest

jobs

areall

in

first

positions

on

the

machines,

allremaining

(smaller)

jobs

are

in

secondpositions,

and

moreover

all

theseremaining

jobs

appear

from

machine

mdown

to

machine

1

in

order

ofdecreasing

size.23

One

easily

sees

that

the

LPT

rule

gives

a

scheduleequivalent

to

this,

thus

with

makespan

A(I)

<(4/3?1/(3m))OPT(I)

.

This

contradicts

the

assumption.So

we

have

concluded

the

proof

for

Case

2

also.24Approximation

scheme

for

identicalmachines25

Several

other

polynomial-time

scheduling

policiesfor

which

the

performance

ratio

can

be

bounded

by

a‘small’

constant.

In

fact,

for

every

fixed

m

and

e0

there

is

a

polynomial

time

algorithm

that

computeapproximately

optimal

schedule

with

a

performance

rof

1+ε.

In

order

to

show

this,

we

design

a

rule

that

trades‘computation

time

for

quality’.

Let

c

be

an

arbitrbut

fixed

integer

constant

≥1.LPTc()26sort

the

jobs

in

order

of

decreasing

processing times:

t1≥

t2

.

.

.

≥

tnassign

the

first

c

jobs

according

to

an

optimal schedule

and

continue

schedulingexecute

list

scheduling

on

the

remaining

part

of

the sorted

listreturn

the

schedule

so

obtained.

An

optimal

schedule

for

jobs

1,

.

.

.

,

cmay

be

determined

by

enumerating

allpossibilities,

thus

in

O(nc)

time.

For

anyfixed

constant

c,

the

LPTc

rule

ispolynomial-time

computable.27

Lemma

3.2.2

The

LPTc

rule

achieves

aperformance

ratio

≤1+(m-1)/(c+1).

Proof:

Say

the

optimal

schedule

of

the

firstc

jobs

has

makespan

B.

Let

the

overallmakespan

resulting

after

placing

theremaining

n?c

jobs

be

A.

If

A

=

B,

thenobviously

A

=

OPT(I)

and

we

are

done.Thus

assume

that

A

>

B.28

Let

tk

be

the

last

job

to

finish,

necessarilyA

and

necessarily

also

k

>

c

(because

the

firjobs

are

all

finished

by

time

B).

At

the

momejob

k

was

assigned,

no

machine

could

have

hisload

end

before

time

A

?

tk

otherwise

job

kwould

have

been

assigned

to

this

machineandend

earlier.

Thus

all

machines

are

at

least

fbusy

up

to

time

A

?

tk,

with

jobs

1,

.

.

.

,

k

?Thus:29A

?

tk≤(t1+...+

tk-1)/m=(t1+...+

tk)/m

?

tk

/mOPT(I)

?

tk

/m30andhenceA

?

OPT(I)

≤(1

?

1/m)

tk≤(1

?

1/m)tc+1.On

the

other

hand,

observe

thatOPT(I)

≥(

t1+...+

tc+1)/m

≥((c+1)/m)tc+1Thus