Operations Research (AD-504 (C)) Unit 4 Notes

How unit 4 is examined

This unit covers job sequencing (Johnson's rule for flow shops, then job shops) and dynamic programming with its use on LPP and its applications; no topic was asked in the supplied papers, so learn the definitions, Johnson's rule with one worked example, and Bellman's recursion first.

Sequencing problem: Introduction to sequencing problem

Not asked since 2022

Definition. The sequencing problem is to find the order in which n jobs should be processed on m machines so that a chosen measure of effectiveness, usually the total elapsed time, is optimised.

Key points.

Each job has a known processing time on each machine, and the order in which a job must visit the machines is called its technological order.
Standard assumptions are that a machine handles only one job at a time, a job is on only one machine at a time, processing times do not depend on the sequence, and once started a job is not interrupted.
The usual objective is to minimise total elapsed time (makespan), which is the time from the start of the first job to the finish of the last job; idle time of machines is the companion measure.
Other objectives are minimum total idle time, minimum mean flow time and minimum lateness against due dates.
With n jobs on m machines there are $(n!)^m$ possible sequences, so a systematic rule is needed instead of trial and error.

Pitfall: Do not confuse sequencing (order of jobs on machines) with assignment (which job goes to which machine); in sequencing every job visits every machine.

Flow shop problem: Processing n jobs through 2, 3 and m machines

Definition. In a flow shop every one of the n jobs passes through the machines in the same order, and Johnson's rule gives the sequence with the minimum total elapsed time.

Steps (n jobs, 2 machines A then B).

Step 1: List the processing time of each job on A and on B.
Step 2: Find the smallest time in the whole table.
Step 3: If it lies on A, put that job first; if it lies on B, put it last.
Step 4: Delete that job and repeat on the remaining jobs; break ties arbitrarily.
Step 5: Read the elapsed time from the in-out table of the final sequence.

Example. Five jobs, times (A, B): J1 (5, 2), J2 (1, 6), J3 (9, 7), J4 (3, 8), J5 (10, 4).

Smallest is 1 (J2 on A) so J2 first; next 2 (J1 on B) so J1 last; next 3 (J4 on A) so J4 second; next 4 (J5 on B) so J5 fourth; J3 remains in the middle.

Optimal sequence: J2, J4, J3, J5, J1.

Job	A in	A out	B in	B out
J2	0	1	1	7
J4	1	4	7	15
J3	4	13	15	22
J5	13	23	23	27
J1	23	28	28	30

Total elapsed time = 30 hours (units), checked against all 120 permutations; idle time of A is 30 - 28 = 2 and of B is 1 + 1 + 1 = 3 (B waits at the start, and for J5 and J1).

Key points.

For 3 machines A, B, C, Johnson's rule applies only if $\min A_i \ge \max B_i$ or $\min C_i \ge \max B_i$, that is, the middle machine is never the bottleneck.
When the condition holds, form two fictitious machines $G_i = A_i + B_i$ and $H_i = B_i + C_i$ and apply the 2-machine rule to G and H.
For m machines the same test is extended: the smallest time on the first machine or the last machine must be at least the largest time on every middle machine.
Then $G_i$ is the sum of the times on the first m-1 machines and $H_i$ is the sum on the last m-1 machines.
The sequence found from G and H is used on the real machines, and the elapsed time is calculated from the in-out table of the real three or m machines, not from G and H.
If the condition fails, Johnson's rule does not guarantee the optimum and other methods such as branch and bound are needed.

Answer frame. Open with the definition of a flow shop and the aim of minimum elapsed time; state the assumptions in one line; write Johnson's steps; solve the given data by listing the sequence stepwise; draw the in-out table; close with the total elapsed time and idle times in bold.

Pitfall: For 3 machines, check the condition first and show it; skipping it loses marks even when the arithmetic is right.

General n/m job-shop problem

Definition. In a job shop each job has its own routing through the machines, so there is no common machine order as in a flow shop.

Key points.

In a flow shop all jobs follow the same order of machines, while in a job shop every job may visit machines in a different order and may skip some machines.
The number of feasible schedules grows enormously with n and m, so an exact solution exists only for small cases such as 2 jobs on m machines, which is solved graphically.
In practice priority dispatching rules are used, such as shortest processing time (SPT), earliest due date (EDD), first come first served (FCFS) and longest processing time (LPT).
Schedules are shown on a Gantt chart, and larger problems use integer programming, branch and bound or heuristics.
The usual objectives are minimum makespan, minimum mean flow time and minimum tardiness.

Basis	Flow shop	Job shop
Machine order	Same for all jobs	Different for each job
Layout	Product line	Process layout
Method	Johnson's rule	Dispatching rules, heuristics
Volume	High, standard	Low, varied

Introduction to Dynamic Programming

Definition. Dynamic programming is a method that solves a multistage decision problem by breaking it into sub-problems, one per stage, and solving them one after another so that the whole problem is optimised.

Key points.

It rests on Bellman's principle of optimality: whatever the initial state and first decision, the remaining decisions must form an optimal policy for the state that results from that first decision.
Each stage has a state variable (the condition of the system entering the stage), a decision variable and a return (profit or cost) function.
The stage transformation $s' = t(s, x)$ links the state of one stage to the next.
The recursive equation is $f_n(s)=\max_x\{r_n(s,x)+f_{n-1}(s')\}$ (use min for costs), with $f_0=0$.
The problem is solved backward, from the last stage to the first, or forward; the answer is the value of $f$ at the initial state.
There is no single formula for all problems, so the state, stage and recursion must be defined afresh for each problem.

Example (shortest route). Nodes S, A, B, C, D, T with arc lengths S-A 4, S-B 2, A-C 5, A-D 3, B-C 1, B-D 6, C-T 3, D-T 2. Working backward with $f(\text{node})=\min\{d+f(\text{next})\}$: $f(C)=3$, $f(D)=2$, $f(A)=\min(5+3,\,3+2)=5$, $f(B)=\min(1+3,\,6+2)=4$, $f(S)=\min(4+5,\,2+4)=6$.

Shortest route: S - B - C - T, length 6.

Answer frame. Open with the definition and Bellman's principle; list the stage, state, decision and return; write the recursion; illustrate with the backward calculation; close by stating the optimal policy.

Dynamic Programming Approach for solving Linear Programming Problem

Definition. An LPP with n variables is treated as an n-stage dynamic programming problem in which each stage chooses the value of one variable and the resource still unused is the state.

Key points.

To maximise $z=\sum c_j x_j$ subject to $\sum a_{ij}x_j\le b_i$, stage $j$ decides $x_j$ and the state is the amount of each resource left.
The recursion is $f_j(b)=\max_{x_j}\{c_jx_j+f_{j-1}(b-a_jx_j)\}$ with $f_0(b)=0$.
For every state value $b$ the best $x_j$ and $f_j(b)$ are tabulated, and the answer is $f_n(b)$ at the full resource.
The number of state variables equals the number of constraints, so the tables grow rapidly (the curse of dimensionality) and the method suits only problems with one or two constraints.
For larger problems the simplex method is preferred, though DP handles non-linear and integer cases that simplex cannot.

Example. Maximise $z=3x_1+5x_2$ subject to $2x_1+3x_2\le 10$, integers. Stage 1 gives $f_1(b)=3\lfloor b/2\rfloor$. Stage 2 gives $f_2(10)=\max_{x_2}\{5x_2+f_1(10-3x_2)\}$: $x_2=0$ gives 15, $x_2=1$ gives $5+f_1(7)=14$, $x_2=2$ gives $10+f_1(4)=16$, $x_2=3$ gives $15+f_1(1)=15$.

Optimum: $x_1=2$, $x_2=2$, $z=16$.

Answer frame. Open by saying the LPP is converted to an n-stage problem; define stage, state and decision; write the recursion; fill the stage tables; close with the optimal values and $z$.

Applications of Dynamic programming

Definition. Dynamic programming applies wherever a decision is made in stages and each decision affects the state of the next stage.

Key points.

Shortest route and network path problems are solved stage by stage from the destination back to the source.
Resource allocation problems, such as sharing capital, machines or manpower among several activities, are the classic cargo-loading or knapsack form.
Multi-period inventory and production planning use the stage as the period and the state as the stock in hand.
Equipment replacement decisions choose in each year whether to keep or replace a machine so that total cost over the horizon is minimum.
It is also used in capital budgeting, scheduling and sequencing problems, and in linear programming with non-linear or integer restrictions.

Last-minute revision

Sequencing: order n jobs on m machines to minimise total elapsed time.
Number of possible sequences of n jobs on m machines is $(n!)^m$.
Johnson's rule: smallest time on A goes first, smallest on B goes last, repeat on the rest.
3-machine condition: $\min A\ge\max B$ or $\min C\ge\max B$; then $G=A+B$, $H=B+C$.
Worked flow shop: times (5,2), (1,6), (9,7), (3,8), (10,4) give J2-J4-J3-J5-J1 with elapsed time 30.
Flow shop has one common machine order; job shop has job-specific routing.
Job-shop rules: SPT, EDD, FCFS, LPT, shown on a Gantt chart.
Bellman's principle: the remaining decisions of an optimal policy are optimal for the resulting state.
DP recursion: $f_n(s)=\max_x\{r_n(s,x)+f_{n-1}(s')\}$, with $f_0=0$.
DP for LPP: stage is a variable, state is the remaining resource; $\max 3x_1+5x_2$, $2x_1+3x_2\le10$ gives 16.
DP applications: shortest route, resource allocation, inventory, replacement.

Memory hooks

Johnson: small on A goes to the front, small on B goes to the back.
Flow shop is a river (one direction); job shop is a city (many routes).
Bellman: the rest of the trip must still be the best trip.
Stage, State, Decision, Return: "SSDR".
Johnson for 3 machines: check the middle machine is never the boss, then merge into G and H.

Coverage checklist

Sequencing problem: Introduction to sequencing problem (no past questions)
Flow shop problem: Processing n jobs through 2, 3 and m machines (no past questions)
General n/m job-shop problem (no past questions)
Introduction to Dynamic Programming (no past questions)
Dynamic Programming Approach for solving Linear Programming Problem (no past questions)
Applications of Dynamic programming (no past questions)

Account

Operations Research (AD-504 (C)) - Unit 4 Short Notes

How unit 4 is examined

Sequencing problem: Introduction to sequencing problem

Flow shop problem: Processing n jobs through 2, 3 and m machines

General n/m job-shop problem

Introduction to Dynamic Programming

Dynamic Programming Approach for solving Linear Programming Problem

Applications of Dynamic programming

Last-minute revision

Memory hooks

Coverage checklist