reset("10","0","1010","780","Machine Scheduling") B = TextPanel("1","1","1000","700","black","white","red") B.setFontLarge() B.disableRH() //S = TextPanel("5","525","500","160","black","white","red") //B2 = TextPanel ("510","5","475","515","black","white","blue") //B2s = TextPanel ("510","5","475","375","black","white","blue") \macro(Rightarrow,⇒) \macro(red,) \macro(Sum,∑) \macro(sum,∑) \macro(sp, ) \macro(le,≤) \macro(ge,≥) \macro(ne,≠) \macro(times,∏) \macro(cdot,·) \macro(times,×) \macro(infty,∞) \macro(cap,∩) \macro(equiv,≡) \macro(cup,∪) B!

Scheduling with Startup and Holding Costs Machine capacity: 1 unit/day.
Startup cost = S, if machine idle previous day.
Warehouse to hold units. Holding cost= H/night.

Input:
Daily demand for n days: D[1,..n],
Startup cost S,
Holding cost H.
Output:
Production schedule: P[1..n] with P[i] denoting whether machine should produce on day i or not, that minimizes total holding and startup cost.

At the end of the n days, all the units manufactured must have been delivered. If the given demand cannot be met, algorithm should indicate as much. B!
Example:Demands D=[0,0,2,0,0,0,3], Holding cost H=1, Startup cost S=5 B:: One possible production plan:

Day 1 2 3 4 5 6 7

Demand 2 3

Produce? - \red T \red T - \red T \red T \red T

Startup 5 5

Inventory 1 1 2

B- Another: // // // // // // // //
Day 1 2 3 4 5 6 7
Demand 2 3

Produce? - \red T \red T \red T \red T \red T -

Startup 5

Inventory 1 1 2 3

B: Cost(plan 1) = 5+5+1+1+2 = 14
Cost(plan 2) = 5+1+1+2+3 = 12 B!
Brute force algorithm Generate all possible schedules, evaluate costs, pick best. B:: Number of schedules = exponential in n, where n = number of days. B:: Too slow. B!
Dynamic Programming Overview Find a recursive solution:
Cast problem as a search for an object over a certain Search space. Define clearly an objective function which is to be minimized (or maximized).

Design algorithm which partitions search space, searches each partition recursively and finds the best in each partition, and returns the best of the best.
B: Check if bottom-up evaluation will help.

Characterize the recursive calls in the above algorithm. Define a table for storing the results of the calls. Define a procedure for filling table entries using other table entries. Procedure should not be recursive.
B! Recursive Algorithms: To solve n day problem:
..
solve first day somehow.
..
recurse on remaining n-1 days.
..
B:: Recursing on n-1 days:
must include history information e.g. is machine on/off
B! Generalized scheduling problem: B- Input:
\sp Daily demand for n days: D[1..n],
\sp Startup cost S,
\sp Holding cost H.
\sp \red Initial inventory I.
\sp \red Machine status (already on/off) M. B:: Old problem : I=0,M=off. B:
Output:
\sp Production schedule: P[1..n] with P[i] denoting whether machine should produce on day i or not, that minimizes total holding and startup cost.

At the end of the n days, all the units manufactured must have been delivered. B!
Search Space and Objective Function: S : All possible schedules for instance D[1..n],S,H,I,M.
\sp Each schedule is an n bit vector.

Objective Function: "cost" = holding + startup costs.
Minimum cost schedule from S is needed. B::
Partitioning S: S_{p : All schedules in which machine
is producing on day 1.

S_{i : All schedules in which machine is idle on day 1.

B:: Clearly S = S_{p U S_{i

B: How to search S_{p:

B- \red If P has the least cost in S_{p then will parts of P
themselves be least cost solutions to some smaller instance?

B! Searching S_{p:
Let P[1..n] be a least cost schedule in S_{p.

P[1]=true.

P[2..n] is a schedule for the residual instance from day 2.

B:: Original Instance: D[1..n],S,H,I,M

B:: Residual Instance: D[2..n],S,H,I-D[1]+1,true.

B:: Lemma: P[2..n] is optimal for instance
D[2..n],S,H,I-D[1]+1,true.

B:: Proof: Suppose not. Let Q[2..n] be optimal for
D[2..n],S,H,I-D[1], with Cost(Q[2..n]) < Cost(P[2..n]).

B:: Consider R = P[1] | Q[2..n] = valid schedule for original.

B:: Cost(R) < Cost(P). Thus contradiction.

B! Lemma for searching S_{i:
Let I[1..n] be a least cost schedule in S_{i. Then I[2..n] is optimal
for instance D[2..n],S,H,I-D[1],false.

B! Outline of Recursive Algorithm:
optschedule(D[1..n],S,H,I,M){

...

P[1..n] = true | optschedule(D[2..n],S,H,I-D[1]+1,true)

I[1..n] = false | optschedule(D[2..n],S,H,I-D[1],false)

If Cost(P) < Cost(I) return P

else return I

}

B:: Several details need to be filled, but this algorithm will take
time O(2^{n).

B! Key step of Dynamic Programming Characterizing the recursive
calls.

B:: Arguments to optschedule are always (D[j..n],S,H,I,M)

B:: 1 \le j \le n. \sp S,H do not vary. \sp I\le n. \sp M=true/false.

B:: Goal: somehow construct a table T, where:

\sp T[j,I,M] = optschedule(D[j..n],S,H,I,M)

B:: Simplified Goal: somehow construct a table C, where:

\sp C[j,I,M] = cost of optschedule(D[j..n],S,H,I,M)

B! Basic Recurrence for C[j,I,M]:
C[j,I,M] = Cost of Optsched(D[j..n],S,H,I,M)

B:: Optsched(D[j..n],S,H,I,M) = least cost schedule from

\sp true | Optsched(D[j+1..n],S,H,I-D[j]+1,true) \sp and

\sp false | Optsched(D[j+1..n],S,H,I-D[j],false)

B:: C[j,I,M] = min(

\sp (M ? 0 : S) + (I-D[j]+1)H + C[j+1, I-D[j]+1, true],

\sp (I-D[j])H + C[j+1, I-D[j], false]

\sp )

B:: \red What if inventory in residual instance is < 0?
B.H("r1,r2,r3,r4,r5,r6","yellow")

B:: Solution: Define C[j,I,M] = \infty \sp if I < 0

B:: Table
too large? \sp D[j] \le n \Rightarrow I \ge -n

B.U("r1,r2,r3,r4,r5,r6")
B! Base Case: Last day's schedule How to set C[n,I,M] for all I,M.

B:: Key: \red There should be just enough
inventory to satisfy D[n].

B:: I = D[n] \sp \Rightarrow Machine off, \sp C[n,I,M] = 0.

B:: I = D[n]-1 \Rightarrow Machine on, \sp C[n,I,M] = M ? 0 : S

B:: Otherwise C[n,I,M] = \infty

B! How to fill table C, C[j,I,M]:
In decreasing order of j.

B:: Number of entries:

B:: j ranges over 1 to n.

B:: -n \le I

B- \le n

B:: M can be on/off.

B:: Total number = n \cdot (2n+1) \cdot 2 = O(n^{2)

B: Time to fill each = O(1)

B:: Total Time = O(n^{2)

B:: Optimal cost: C[1,0,false]

B! How to find schedule given table C

B- C[1,0,off] = cost of optimal schedule.

B:: = min(

\sp ... + C[2, 1-D[1], on]

\sp ... + C[2, -D[1], off]

\sp )

B:: C[1,0,off] = first term or second

B:: first term \Rightarrow machine on (during day 1)

B:: second term \Rightarrow machine off (during day 1)

B:: In similar manner we can find machine state for each day.

B!
Concluding Remarks:
Generalizing the given problem is important.

Dynamic Programming = recursion + compute every value only
once.

Recursion in search problems = divide and conquer of search space.

\scene(End)}}}}}}}}}}}}}

Day	1	2	3	4	5	6	7
Demand			2				3
Produce?	-	\red T	\red T	-	\red T	\red T	\red T
Startup		5			5
Inventory		1			1	2

Brute force algorithm Generate all possible schedules, evaluate costs, pick best. B:: Number of schedules = exponential in n, where n = number of days. B:: Too slow. B!

Search Space and Objective Function: S : All possible schedules for instance D[1..n],S,H,I,M. \sp Each schedule is an n bit vector. Objective Function: "cost" = holding + startup costs. Minimum cost schedule from S is needed. B::

Concluding Remarks: Generalizing the given problem is important. Dynamic Programming = recursion + compute every value only once. Recursion in search problems = divide and conquer of search space. \scene(End)

Search Space and Objective Function: S : All possible schedules for instance D[1..n],S,H,I,M.
\sp Each schedule is an n bit vector.

Objective Function: "cost" = holding + startup costs.
Minimum cost schedule from S is needed. B::

Concluding Remarks:
Generalizing the given problem is important.
Dynamic Programming = recursion + compute every value only once.
Recursion in search problems = divide and conquer of search space.
\scene(End)