Operation Research & Supply Chain (ME-703 (A)) - Unit 5 Short Notes

UNIT 5: OPERATION RESEARCH & SUPPLY CHAIN

1. LINEAR PROGRAMMING (LP)

Formulation of LP Problems

An LP problem seeks to maximize or minimize a linear objective function subject to linear constraints and non-negativity restrictions.

Components:

• Decision Variables: Quantities to be determined (e.g., \(x_1, x_2\)).

• Objective Function: \(Z = c_1x_1 + c_2x_2 + \dots\) (maximize profit or minimize cost).

• Constraints: Resource limits, demand requirements, technological limits (e.g., \(a_{11}x_1 + a_{12}x_2 \le b_1\)).

• Non-negativity: \(x_i \ge 0\) for all \(i\).

Formulation Steps from Word Problems:

1. Define decision variables clearly.

2. Construct objective function (profit/cost).

3. Translate constraints into inequalities/equalities.

4. Add non-negativity restrictions.

[!TIP]

Exam Focus: LP formulation is frequently asked. Ensure variables represent quantities, not costs/profits directly. Check units consistency.

Simplex Method

A systematic procedure to solve LP problems by moving from one basic feasible solution (BFS) to an adjacent one, improving the objective value.

Standard Form Requirements:

• Maximization objective.

• All constraints as equalities (\(\le\) → add slack; \(\ge\) → subtract surplus and add artificial; \(=\) → add artificial).

• All variables \(\ge 0\).

Tableau Format Steps:

1. Initial Tableau: Include slack/surplus/artificial variables. Set up \(C_j\) (coefficients in objective) and \(Z_j = \sum C_B \cdot a_{ij}\).

2. Compute \(C_j - Z_j\) row.

3. Optimality Check:

   • For maximization: if all \(C_j - Z_j \le 0\), current solution is optimal.

   • If any \(C_j - Z_j > 0\), entering variable is the most positive.

4. Pivot Operation: Determine leaving variable via minimum ratio test (only for positive entries in pivot column). Update tableau.

5. Repeat until optimal.

Handling Constraints:

• \(\le\): Add slack variable (e.g., \(x_1 + 2x_2 + s_1 = 10\), \(s_1 \ge 0\)).

• \(\ge\): Subtract surplus variable and add artificial variable (e.g., \(x_1 + 2x_2 - s_1 + a_1 = 10\)).

• \(=\): Add artificial variable.

Big-M Method: Assign large penalty \(M\) to artificial variables in objective (max: \(-M a_i\), min: \(+M a_i\)). Remove artificial variables after they leave basis.

Two-Phase Method:

• Phase I: Minimize sum of artificial variables. If min > 0 → infeasible. If min = 0 → proceed to Phase II.

• Phase II: Solve original objective with feasible basis from Phase I.

Special Cases:

• Multiple Optimal Solutions: If a non-basic variable has \(C_j - Z_j = 0\) at optimum, alternate optimal solutions exist.

• Unbounded Solution: If entering variable column has all \(\le 0\) entries, solution is unbounded.

• Infeasible Solution: If artificial variable remains positive in optimal tableau.

[!TIP]

Common Pitfall: Forgetting to remove artificial variables before optimality check in Big-M. Always ensure \(C_j - Z_j\) computed correctly with \(C_B\) values.

Degeneracy in LP

Definition: A BFS is degenerate if at least one basic variable equals zero. In simplex, this occurs when the minimum ratio test yields a tie (two or more variables qualify to leave basis).

Causes:

• Redundant constraints.

• Linear dependency among constraints.

• Poor initial BFS.

Resolution:

• Perturbation Method: Add tiny \(\epsilon > 0\) to RHS of constraints to break ties.

• Cycling Prevention: Bland’s rule (choose smallest subscript for entering/leaving variable).

[!TIP]

Degeneracy may cause cycling (infinite loop) in simplex. In exams, perturbation is usually accepted.

2. TRANSPORTATION PROBLEMS

Problem Structure

• Balanced: Total supply = Total demand.

• Unbalanced: Introduce dummy row (if supply < demand) or dummy column (if supply > demand) with zero transportation cost.

Initial Basic Feasible Solution (IBFS) Methods

North-West Corner Rule (NWCR):

1. Start at top-left cell (row 1, col 1).

2. Allocate as much as possible: \(x_{11} = \min(\text{supply}_1, \text{demand}_1)\).

3. Adjust supply/demand; move right if demand exhausted, down if supply exhausted.

4. Repeat until all allocations made.

Least Cost Method (LCM):

1. Identify cell with minimum cost.

2. Allocate max possible, adjust supply/demand.

3. Cross out exhausted row/column.

4. Repeat from remaining cells.

Vogel’s Approximation Method (VAM) – High Priority:

1. For each row and column, compute penalty = difference between two smallest costs.

2. Select row/column with highest penalty.

3. In that row/column, allocate to minimum cost cell as much as possible.

4. Adjust supply/demand, recalc penalties for affected rows/columns.

5. Repeat until all allocations made.

VAM usually gives IBFS close to optimal.

Optimality Test

MODI (Modified Distribution) / UV Method:

1. For IBFS with \(m+n-1\) allocations, find \(u_i, v_j\) such that \(u_i + v_j = c_{ij}\) for allocated cells (\(c_{ij}\) = cost). Set \(u_1 = 0\) (or any), solve.

2. Compute improvement index \(\Delta_{ij} = c_{ij} - (u_i + v_j)\) for unallocated cells.

3. Optimality: If all \(\Delta_{ij} \ge 0\), solution is optimal.

4. If any \(\Delta_{ij} < 0\), select most negative \(\Delta_{ij}\) for improvement.

Stepping Stone Method:

1. For unallocated cell, trace a closed loop through allocated cells (horizontal/vertical turns only).

2. Assign \(+\) and \(-\) alternately to corners.

3. Compute opportunity cost = sum of \(-\) costs minus sum of \(+\) costs.

4. If any opportunity cost < 0, solution not optimal. Most negative cell enters basis.

5. Adjust allocations along loop: subtract smallest allocation from \(-\) cells, add to \(+\) cells.

Degeneracy in Transportation

Definition: Number of allocated cells \(< m + n - 1\) in IBFS or during optimality test.

Resolution:

• Epsilon (\(\epsilon\)) Method: Assign tiny \(\epsilon > 0\) to one unallocated cell to make allocations = \(m+n-1\). Proceed with MODI/stepping stone; ignore \(\epsilon\) in final solution.

• Allocate smallest unallocated cell: Manually allocate to a zero-cost unallocated cell (if available) to reach \(m+n-1\) allocations.

Special Cases

• Maximization Problems: Convert to minimization by subtracting each cost from a large constant \(M\) (e.g., \(M = \max(c_{ij}) + 1\)). Solve minimization, then convert optimal value back.

• Penalties for Unfulfilled Demand: Introduce dummy destination with penalty cost for each origin. Supply equals total actual demand + dummy demand.

• Unbalanced with Penalties: Combine dummy row/column with penalty costs.

[!TIP]

VAM is frequently asked. Always check for degeneracy after IBFS. For maximization, remember to subtract from large \(M\), not just negate costs.

3. INVENTORY MANAGEMENT

Economic Order Quantity (EOQ) Model

Assumptions:

• Demand rate \(D\) constant and known.

• Instantaneous replenishment (order arrives all at once).

• No shortages allowed.

• Fixed ordering cost \(S\) per order.

• Constant holding cost \(H\) per unit per year.

• Single item.

Derivation:

Total Annual Cost: \(TC = DS + \frac{Q}{2}H + PD\)

Where \(Q\) = order quantity, \(P\) = unit cost.

Minimize \(TC\): \(\frac{dTC}{dQ} = 0 \Rightarrow Q^* = \sqrt{\frac{2DS}{H}}\).

Key Calculations:

• EOQ: \(Q^* = \sqrt{\frac{2DS}{H}}\)

• Total Annual Cost: \(TC^* = DS + \frac{Q^*}{2}H + PD\)

• Number of Orders per Year: \(N = \frac{D}{Q^*}\)

• Time Between Orders (Cycle Time): \(T = \frac{365}{N}\) days or \(T = \frac{Q^*}{D}\) years.

EOQ Variants

Finite Production Rate (EPQ/Production Model):

• Production rate \(p > D\), consumption during production.

• \(Q^* = \sqrt{\frac{2DS}{H \left(1 - \frac{D}{p}\right)}}\)

Planned Shortages/Backordering:

• Backorder cost \(B\) per unit per year.

• \(Q^* = \sqrt{\frac{2DS}{H} \cdot \frac{H+B}{B}}\)

• Maximum backorder level: \(S^* = Q^* \cdot \frac{H}{H+B}\)

Quantity Discounts

All-Units Discount: Discount applies to entire order if \(Q\) exceeds breakpoint.

• Compute EOQ at each discounted price (use \(H = i \cdot P_{\text{disc}}\) where \(i\) = carrying cost %).

• If EOQ feasible (within discount range), compute \(TC\).

• Else, compute \(TC\) at breakpoint (minimum \(Q\) for discount).

• Choose \(Q\) with minimum \(TC\).

Incremental Discount: Discount applies only to units above breakpoint.

• Compute \(TC\) at each breakpoint and EOQ at lowest price.

• Choose minimum \(TC\).

ABC Analysis

Classification based on annual usage value (\(= \text{annual demand} \times \text{unit cost}\)):

• A-items: ~70% of total value, ~10% of items. Tight control, frequent review.

• B-items: ~20% of value, ~20% of items. Moderate control.

• C-items: ~10% of value, ~70% of items. Loose control, bulk ordering.

Advantages: Prioritizes management attention, optimizes inventory investment, reduces stockouts for critical items.

VED Analysis

Classification based on criticality (especially for spares):

• V (Vital): Essential for operation; stockouts halt production. High cost of stockout.

• E (Essential): Important but not vital; stockouts cause inefficiency.

• D (Desirable): Nice to have; stockouts cause minor inconvenience.

Advantages: Focuses on maintenance spares, ensures availability of critical items, cost-effective control.

[!TIP]

EOQ calculations are very frequent. Ensure consistent units: \(D\) per year, \(S\) per order, \(H\) per unit per year. For monthly data, convert \(D\) to annual or adjust \(H\) accordingly.

4. SUPPLY CHAIN MANAGEMENT (SCM) CONCEPTS

Bull-Whip Effect

Definition: Demand distortion upstream in supply chain: small fluctuations in consumer demand cause larger fluctuations at wholesalers, manufacturers, suppliers.

Causes:

1. Demand Forecasting: Each echelon forecasts based on orders, not actual demand → amplification.

2. Order Batching: Large, infrequent orders to reduce ordering costs → periodic spikes.

3. Price Fluctuations: Forward buying during promotions → irregular orders.

4. Rationing & Gaming: Suppliers allocate based on orders, not needs → customers over-order.

Mitigation Strategies:

• Vendor Managed Inventory (VMI): Supplier manages inventory at customer’s location.

• Electronic Data Interchange (EDI): Share real-time point-of-sale data.

• Everyday Low Pricing (EDLP): Eliminate promotions.

• Reduce Lead Times: Faster response reduces need for safety stock.

• Order Smoothing: Consistent ordering patterns.

Importance: Reduces inventory costs, improves forecast accuracy, enhances coordination.

Logistics in SCM

Inbound Logistics:

• Activities: Procurement, transportation from suppliers, receiving, warehousing of raw materials.

• Importance: Ensures timely availability of inputs, impacts production continuity and cost of goods sold.

Outbound Logistics:

• Activities: Finished goods storage, order processing, distribution, delivery to customers.

• Importance: Directly affects customer service level, delivery speed, and satisfaction. Key competitive differentiator.

Cross-Docking

Definition: Logistics practice where inbound shipments are directly transferred to outbound trucks with minimal or no storage.

Process Flow:

1. Inbound trucks unload at docking bays.

2. Goods sorted and consolidated by destination.

3. Loaded directly onto outbound trucks.

4. Minimal handling and storage time (often < 24 hrs).

Advantages:

• Reduces inventory holding costs.

• Decreases order cycle time.

• Minimizes handling and damage.

• Improves product freshness (perishables).

Disadvantages:

• Requires high coordination and accurate forecasting.

• Inflexible to demand variability.

• High initial investment in docking infrastructure.

Material, Money & Information Flow

• Material Flow: Physical movement of goods from suppliers to customers (upstream/downstream).

• Money Flow: Financial transactions (payments, credit, settlements) opposite to material flow.

• Information Flow: Orders, forecasts, inventory levels, shipment status—bidirectional. Enables coordination.

Integration Importance: Synchronized flows reduce bull-whip, improve visibility, enable quick response.

Role of Inventory in Logistics

• Buffer Against Uncertainty: Against demand variability and supply disruptions.

• Trade-off: Higher inventory → better service level but higher holding costs; lower inventory → cost saving but risk of stockouts.

• Types of Inventory:

  • Cycle Stock: From batch ordering/production.

  • Safety Stock: Buffer against uncertainty.

  • Anticipation Stock: Built for predictable peaks (seasonal demand).

  • Pipeline Stock: In transit between stages.

Outsourcing in SCM

Importance:

• Focus on core competencies.

• Access to specialized expertise and technology.

• Cost reduction (economies of scale, lower labor costs).

• Flexibility to scale operations.

Risks:

• Loss of control over processes.

• Dependency on supplier.

• Quality issues and coordination challenges.

• Intellectual property risks.

SCM Expenditures & Opportunities

Major Cost Areas:

• Procurement (sourcing, purchasing).

• Production (manufacturing, setup).

• Inventory (holding, obsolescence).

• Transportation (shipping, freight).

Opportunity Areas:

• Technology: IoT, AI for demand forecasting, warehouse automation.

• Collaboration: CPFR (Collaborative Planning, Forecasting, Replenishment).

• Sustainability: Green logistics, reverse logistics, carbon footprint reduction.

SCM & E-Business

Linkage:

• E-procurement: Online purchasing, auctions, catalogs.

• E-commerce: Direct-to-consumer sales, online order fulfillment.

• E-fulfillment: Integrated warehousing, picking, shipping for online orders.

Impact:

• Visibility: Real-time tracking of orders/inventory.

• Speed: Faster order processing and delivery.

• Coordination: Seamless integration across supply chain partners via platforms.

MRP to ERP & SCM Integration

Evolution:

• MRP (Material Requirements Planning): Focuses on material planning (explosion of BOM, net requirements).

• MRP II (Manufacturing Resource Planning): Extends MRP to include capacity planning, shop floor control, finance.

• ERP (Enterprise Resource Planning): Integrates all business functions (HR, finance, SCM, CRM) into a single system with real-time data.

How ERP Supports SCM:

• Provides single source of truth for inventory, orders, production.

• Automates processes (order-to-cash, procure-to-pay).

• Enables demand planning and supply chain visibility across the network.

• Facilitates collaboration with suppliers and customers via portals.

[!TIP]

Bull-Whip effect and its mitigation are very high frequency. Cross-docking advantages/disadvantages also common. Be precise: cross-docking ≠ cross-docking with storage.

5. PROJECT MANAGEMENT (PERT/CPM)

Network Diagram Construction

• Activity-on-Arrow (AOA): Arrows represent activities, nodes represent events (milestones). Requires dummy activities (zero duration) to show dependencies when multiple activities share start/end events.

• Activity-on-Node (AON): Nodes represent activities, arrows represent dependencies (precedence). More common, no dummy activities needed.

Network Logic: Precedence relationships (FS, SS, FF, SF). Typically Finish-to-Start (FS): Activity B cannot start until Activity A finishes.

Critical Path Method (CPM)

Assumptions: Deterministic activity times.

Steps:

1. Forward Pass (compute earliest times):

   • \(ES_i = 0\) for start node.

   • \(EF_i = ES_i + t_i\).

   • For successor \(j\): \(ES_j = \max(EF_i)\) over all predecessors \(i\).

2. Backward Pass (compute latest times):

   • \(LF_j = \text{project duration}\) for end node.

   • \(LS_j = LF_j - t_j\).

   • For predecessor \(i\): \(LF_i = \min(LS_j)\) over all successors \(j\).

3. Float/Slack:

   • Total Float: \(TF_i = LS_i - ES_i = LF_i - EF_i\). Time an activity can be delayed without delaying project.

   • Free Float: \(FF_i = \min(ES_j) - EF_i\) (delay without delaying successors).

   • Independent Float: \(IF_i = FF_i - \sum TF\) of successors? Often not required.

4. Critical Path: Path with zero total float. Longest path through network. Determines minimum project duration.

Significance: Any delay on critical path delays project. Non-critical paths have slack.

Program Evaluation and Review Technique (PERT)

Assumptions: Probabilistic activity times (beta distribution approximation).

Three Time Estimates:

• Optimistic (\(O\)): Minimum time if everything goes well.

• Most Likely (\(M\)): Most probable time.

• Pessimistic (\(P\)): Maximum time if major problems.

Expected Time & Variance:

• \(t_e = \frac{O + 4M + P}{6}\)

• \(\sigma^2 = \left(\frac{P - O}{6}\right)^2\)

Project Duration & Variance:

• Expected project duration \(T_e = \sum t_e\) along critical path.

• Project variance \(V = \sum \sigma^2\) along critical path (variances add on critical path).

Project Completion Probability:

Given due date \(D\):

1. Compute \(Z = \frac{D - T_e}{\sqrt{V}}\).

2. Use standard normal table to find \(P(Z \leq z)\) or \(P(Z > z)\).

3. Probability of completion by \(D\) = \(P(Z \leq z)\) if \(D > T_e\); else \(P(Z > |z|)\).

PERT vs. CPM

Applications of PERT/CPM

• Project planning and scheduling.

• Resource allocation and leveling.

• Monitoring progress (earned value management).

• Crashing: Reducing project duration by adding resources at extra cost (CPM).

[!TIP]

Critical path identification is essential. For probability, always use critical path variance. In PERT, if \(D < T_e\), compute \(Z = (T_e - D)/\sqrt{V}\) and find \(P(T_e > D)\).

6. QUEUING THEORY

Basic Concepts

• Arrival Process: Pattern of customer arrivals. Often Poisson with rate \(\lambda\) (customers/unit time).

• Service Time Distribution: Time to serve a customer. Often Exponential with rate \(\mu\) (customers/unit time).

• Queue Discipline: Order of service (FCFS, LCFS, priority, SPT).

• System Capacity: Maximum number of customers allowed in system (finite/infinite).

• Population Size: Number of potential customers (finite/infinite).

Poisson Arrivals & Exponential Service (M/M/1)

Notation: M/M/1 → Markovian (Poisson) arrivals, Exponential service, 1 server.

• Arrival rate \(\lambda\), service rate \(\mu\).

• Utilization factor: \(\rho = \frac{\lambda}{\mu}\).

• Steady-state condition: \(\rho < 1\) (otherwise queue grows infinitely).

Performance Measures (M/M/1)

• Probability of \(n\) customers in system: \(P_n = (1-\rho) \rho^n\)

• Average number in system: \(L = \frac{\rho}{1-\rho}\)

• Average number in queue: \(L_q = \frac{\rho^2}{1-\rho}\)

• Average time in system: \(W = \frac{1}{\mu - \lambda}\)

• Average time in queue: \(W_q = \frac{\lambda}{\mu(\mu - \lambda)}\)

• Probability of waiting (server busy): \(P_w = \rho\)

• Probability of zero customers: \(P_0 = 1 - \rho\)

Probability Calculations

• Exponential Service Time: \(P(\text{service time} > t) = e^{-\mu t}\)

• Poisson Arrivals: \(P(n \text{ arrivals in time } t) = \frac{(\lambda t)^n e^{-\lambda t}}{n!}\)

Queue Disciplines

• FCFS (First-Come-First-Served): Fair, common. Average wait minimized for identical service times.

• LCFS (Last-Come-First-Served): Stack discipline (e.g., emergency). Can lead to starvation.

• Priority Queuing: Customers have priorities; preemptive (interrupt service) or non-preemptive.

• SPT (Shortest Processing Time): Minimizes average waiting time but requires known service times.

[!TIP]

M/M/1 formulas are crucial. Remember \(L = L_q + \rho\), \(W = W_q + 1/\mu\). For exponential, \(P(T > t) = e^{-\mu t}\) is a direct formula.

7. OTHER OPERATION RESEARCH TOPICS

Game Theory

• Pure Strategy: Player chooses a single strategy deterministically.

• Mixed Strategy: Player randomizes over strategies with probabilities.

• Basic Assumptions:

  1. Rational players (maximize own payoff).

  2. Competitive (zero-sum or non-zero-sum).

  3. Known payoffs for all strategy combinations.

  4. Single move (simultaneous or sequential with known actions).

Dominance Rule:

• Row Dominance: If all elements of row \(i\) ≤ corresponding elements of row \(j\), row \(i\) is dominated (in minimization) → delete row \(i\).

• Column Dominance: If all elements of column \(k\) ≥ corresponding elements of column \(l\), column \(k\) is dominated (in maximization) → delete column \(k\).

• Use to reduce payoff matrix before solving (saddle point or mixed strategies).

Heuristic & Meta-Heuristic Algorithms

• Heuristics: Problem-specific, quick, intuitive rules that yield good but not optimal solutions.

  Example: Nearest neighbor for TSP, savings algorithm for VRP.

• Meta-Heuristics: General-purpose frameworks that can be adapted to many problems; explore large solution spaces efficiently.

  Examples: Genetic Algorithms (evolution), Simulated Annealing (cooling process), Tabu Search (memory-based).

• Use When: Exact methods (e.g., branch-and-bound) are too slow or complex for large-scale problems.

Waiting Line (Queue) Disciplines – Detailed

Impact on Performance:

• FCFS: Fair, but may not minimize waiting time if service times vary.

• Priority: Reduces waiting for high-priority customers but may increase for others; risk of starvation.

• SPT: Minimizes average waiting time \(W_q\) but requires knowledge of service times; can cause starvation for long jobs.

• LCFS: Useful for emergency (LIFO stack), but average wait can be high.

Selection Criteria:

• Service Environment: Hospital emergency (priority), call centers (FCFS with priority), manufacturing (SPT for throughput).

• Fairness vs Efficiency: FCFS for fairness; SPT for efficiency.

• Information Availability: SPT requires service time knowledge.

[!TIP]

Game theory dominance is a common reduction technique. For meta-heuristics, know one example (e.g., GA: selection, crossover, mutation). Queue discipline choice depends on context—FCFS is default unless specified.

Final Note: This summary covers all topics from the blueprint with emphasis on high-frequency exam areas. Practice numerical problems for Simplex, Transportation (VAM/MODI), EOQ, PERT probability, and M/M/1 queuing. Always state assumptions and show steps clearly in exams.