CPE 613, Lecture 16 Study Notes

Problem Formulation in Process Design: Scheduling and Retrofit

  • Multi-level optimization is critical for the chemical industries.

  • Focus areas include scheduling and planning.

  • Key problems that need addressing:
      - Batch planning: determining what to make, how much to produce, and when to produce.
      - Logistics: optimizing shipping amounts and destinations.
      - Business planning: making decisions on plant construction and quantities.

Scheduling and Planning

  • Planning and scheduling are essential components in process systems engineering.

  • Specific problems to resolve:
      - Batch Planning: What to manufacture, quantity to produce, and timing of production.
      - Logistics Planning: Determining shipping volumes and destinations.
      - Business Planning: Deciding on plant locations and the number of plants to establish.

Business and Engineering

  • Operations Research (OR) refers to optimizing supply chains within business contexts.

  • Integration of multiple objectives leads to Enterprise-Wide Optimization, which involves:
      - Minimizing the overall carbon footprint.
      - Capitalizing on business opportunities for expanding the product portfolio.
      - Leveraging economies of scale in manufacturing.

Example: Scheduling and Planning

  • Engineers validate the formulation of scheduling and planning problems.

  • Example Scenario: A petrochemical company operates two refineries.
      - Locations: Los Angeles and Houston.
      - Objective: Ship jet fuel to four tank farms designated for airports in:
        - Denver
        - Kansas City
        - Nashville
        - Pittsburgh

Scheduling Example: Data

  • Production Capacities:
      - Los Angeles Refinery: 150,000 bbl/week
      - Houston Refinery: 200,000 bbl/week

  • Demand at Each Tank Farm:
      - Denver: 100,000 bbl/week
      - Kansas City: 80,000 bbl/week
      - Nashville: 60,000 bbl/week
      - Pittsburgh: 90,000 bbl/week

Scheduling Example: Costs

  • Shipping Costs (per 100,000 bbl):
      - From Los Angeles to:
        - Denver: $4
        - Kansas City: $7
        - Nashville: $9
        - Pittsburgh: $11
      - From Houston to:
        - Denver: $5
        - Kansas City: $4
        - Nashville: $5
        - Pittsburgh: $8

Scheduling: Problem Statement

  • Objective: Determine the number of 100,000 bbl shipments from each refinery to each tank farm, ensuring all demands are met while minimizing total shipping costs.

  • Formulation Requirements:
      - Define all variables involved in optimization.
      - Develop an objective function.
      - Formulate all constraints.

Variable Definitions

  • Variables Defined:
      - Refineries:
        - 1 = Los Angeles, 2 = Houston (denote as extit{i})
      - Tank Farms:
        - 1 = Denver, 2 = Kansas City, 3 = Nashville, 4 = Pittsburgh (denote as extit{j})
      - Let xijx_{ij} represent the number of 100,000 bbl shipments from refinery ii to tank farm jj.
      - Let cijc_{ij} denote the cost to ship one 100,000 bbl shipment from refinery ii to tank farm jj (this value is known).

Objective Function

  • Objective Function: Minimize Total Cost:
      - This is achieved by multiplying shipping cost by the total amount shipped:
        - extMinimize:extTotalCost=extcostimesextamountshippedext{Minimize: } ext{Total Cost} = ext{cost} imes ext{amount shipped}.

Constraints

  • Constraints to Consider:
      - Production Limits:
        - From Los Angeles: x11+x12+x13+x14 ext(fromLA) extmustbe extlessthanorequalto 150x_{11} + x_{12} + x_{13} + x_{14} \, ext{(from LA)} \, ext{must be} \, ext{less than or equal to} \, 150
        - From Houston: x21+x22+x23+x24 ext(fromHouston) extmustbe extlessthanorequalto 200x_{21} + x_{22} + x_{23} + x_{24} \, ext{(from Houston)} \, ext{must be} \, ext{less than or equal to} \, 200
      - Demand Satisfaction:
        - Denver Demand: x11+x21 extmustsatisfy extatleast 100x_{11} + x_{21} \, ext{must satisfy} \, ext{at least} \, 100
        - Kansas City Demand: x12+x22 extmustsatisfy extatleast 80x_{12} + x_{22} \, ext{must satisfy} \, ext{at least} \, 80
        - Nashville Demand: x13+x23 extmustsatisfy extatleast 60x_{13} + x_{23} \, ext{must satisfy} \, ext{at least} \, 60
        - Pittsburgh Demand: x14+x24 extmustsatisfy extatleast 90x_{14} + x_{24} \, ext{must satisfy} \, ext{at least} \, 90
      - Non-Negativity Constraint:
        - All shipments must be non-negative:
          - xijextmustbe 0 extorgreaterforalli=1,2extandj=1,2,3,4x_{ij} ext{ must be} \, 0 \, ext{or greater for all } i=1,2 ext{ and } j=1,2,3,4.

Mathematical Formulation

  • Characterization of the problem:
      - The problem described is categorized as a Linear Program (LP).
      - It is characterized by having a single, globally optimal solution.

Conclusions

  • Optimization theory serves as a method to address large-scale scheduling and planning challenges in the chemical industry.

  • Enterprises capable of implementing broader optimization strategies can achieve efficiencies not feasible for smaller organizations.

  • Even problems with multiple objectives can now be accommodated through optimization techniques.

Question of the Day

  • The task is to insert your mathematical formulation according to the problem framework established in the lecture.

What this lecture is about

This lecture introduces Problem Formulation in Process Design through the lens of scheduling and planning. The core skill being taught is how to take a real-world logistics or planning problem and translate it into a precise mathematical form that can be solved by optimization software. This is one of the most practically valuable skills in chemical engineering because these problems appear constantly in industry — from shipping logistics to production planning to supply chain optimization.

The Three Levels of Planning and Scheduling

The lecture identifies three distinct categories of problems that fall under planning and scheduling. Understanding which category a problem falls into tells you what kind of formulation you need.

Batch planning answers the questions: what to make, how much to make, and when to make it. This is the production scheduling problem — given a set of products you could make and equipment that can make them, how do you allocate your equipment time across products to meet demand targets most efficiently? This connects directly to Lectures 17 and 18 on batch plant design.

Logistics answers the question: how much to ship where. Given that you've made product at various locations, how do you distribute it to customers or distribution points to meet demand at minimum cost? This is exactly what the jet fuel example in this lecture solves.

Business planning answers the strategic questions: where to build plants and how many to build. This is the highest-level decision — should you build a new refinery in the Gulf Coast or the Midwest? Should you build one large plant or two smaller ones? These decisions involve capital investment of hundreds of millions of dollars and affect the company for decades.

All three levels are mathematically related — they're all optimization problems where you have an objective to minimize or maximize, subject to constraints that represent physical and business realities.

Operations Research vs Enterprise-Wide Optimization

The business world calls the optimization of supply chains and logistics Operations Research (OR). This is a well-established mathematical field that predates computers and was developed extensively during World War II for military logistics.

When you add multiple competing objectives simultaneously — not just minimize cost but also minimize carbon footprint, maximize product portfolio diversity, and exploit economies of scale — the problem becomes what engineers now call Enterprise-Wide Optimization (EWO). EWO considers the entire enterprise as a system rather than optimizing individual parts in isolation. The insight driving EWO is that optimizing each part of a supply chain independently often produces a globally suboptimal result — the whole system can be better than the sum of its individually optimized parts.

Engineers are specifically cited in the lecture as the people capable of formulating these problems in a meaningful way. This is because formulating an optimization problem correctly requires understanding the physical constraints — what's actually possible given production capacities, transportation limits, and process chemistry — which is the engineer's domain.

The Jet Fuel Example — Setting Up the Problem

A petrochemical company has two refineries: Los Angeles (Refinery 1) and Houston (Refinery 2). Jet fuel must be shipped to four tank farms that distribute to airports: Denver (Tank Farm 1), Kansas City (Tank Farm 2), Nashville (Tank Farm 3), and Pittsburgh (Tank Farm 4).

Production capacities:

  • Los Angeles: 150,000 barrels per week maximum

  • Houston: 200,000 barrels per week maximum

These are upper limits — the refineries can produce less but not more.

Demand at each tank farm (minimum requirements):

  • Denver: 100,000 bbl/week

  • Kansas City: 80,000 bbl/week

  • Nashville: 60,000 bbl/week

  • Pittsburgh: 90,000 bbl/week

These are lower limits — each tank farm must receive at least this much to supply its airports.

Total demand: 100 + 80 + 60 + 90 = 330,000 bbl/week Total capacity: 150 + 200 = 350,000 bbl/week

The system is feasible — there's enough total capacity to meet total demand. But the question is how to route the shipments to meet all demands at minimum cost.

Shipping costs (dollars per 100,000 bbl shipped):

From LA: Denver $4, Kansas City $7, Nashville $9, Pittsburgh $11 From Houston: Denver $5, Kansas City $4, Nashville $5, Pittsburgh $8

Notice the pattern: LA is cheaper for Denver (it's geographically closer) and Pittsburgh is most expensive from LA because it's furthest away. Houston is cheapest for Kansas City. These cost differences are what create the optimization problem — if costs were equal everywhere there would be nothing to optimize.

Step 1 — Define Your Variables

This is always the first step in any optimization formulation and it must be done precisely. Poorly defined variables lead to formulations that can't be solved or that give nonsensical answers.

Let i index the refineries: i = 1 for LA, i = 2 for Houston. Let j index the tank farms: j = 1 for Denver, j = 2 for Kansas City, j = 3 for Nashville, j = 4 for Pittsburgh.

Define xij as the number of 100,000 bbl shipments from refinery i to tank farm j. This is the decision variable — the thing we're solving for. There are 2 × 4 = 8 decision variables: x11, x12, x13, x14, x21, x22, x23, x24.

Define cij as the cost per 100,000 bbl shipment from refinery i to tank farm j. These are known constants from the cost table — c11 = 4, c12 = 7, c13 = 9, c14 = 11, c21 = 5, c22 = 4, c23 = 5, c24 = 8.

The distinction between decision variables (what we solve for) and parameters (what we know) is fundamental. In any optimization problem you must be completely clear about which quantities are known and which are unknowns.

Step 2 — Write the Objective Function

The objective is to minimize total shipping cost. Total cost is just the sum of (cost per shipment × number of shipments) for every possible refinery-to-tank-farm route.

Mathematically: Minimize TC = sum over all i and j of (cij × xij)

Written out in full: Minimize TC = c11·x11 + c12·x12 + c13·x13 + c14·x14 + c21·x21 + c22·x22 + c23·x23 + c24·x24

Substituting the known costs: Minimize TC = 4x11 + 7x12 + 9x13 + 11x14 + 5x21 + 4x22 + 5x23 + 8x24

This is a linear objective function — each decision variable appears to the first power only, with no products of variables, no squares, no nonlinear terms. This is the defining feature of a linear program.

Using double summation notation compactly: Minimize TC = ΣΣ cij·xij where i goes from 1 to 2 and j goes from 1 to 4.

Step 3 — Write the Constraints

There are three types of constraints in this problem. Every constraint type serves a different physical purpose and uses a different inequality direction.

Type 1 — Production Limit Constraints (≤ inequalities)

You cannot ship more from a refinery than it can produce. For each refinery, the total amount shipped to all four tank farms must be less than or equal to the refinery's production capacity.

For LA (Refinery 1): x11 + x12 + x13 + x14 ≤ 150

This reads: the total shipments from LA to Denver, plus KC, plus Nashville, plus Pittsburgh must not exceed 150 (in units of 100,000 bbl/week).

For Houston (Refinery 2): x21 + x22 + x23 + x24 ≤ 200

There are two production limit constraints — one per refinery.

Type 2 — Demand Satisfaction Constraints (≥ inequalities)

Each tank farm must receive at least its required amount. For each tank farm, the total amount received from all refineries must be greater than or equal to the demand.

For Denver (Tank Farm 1): x11 + x21 ≥ 100

This reads: Denver must receive at least 100 (in 100,000 bbl/week units) from LA plus Houston combined.

For Kansas City (Tank Farm 2): x12 + x22 ≥ 80

For Nashville (Tank Farm 3): x13 + x23 ≥ 60

For Pittsburgh (Tank Farm 4): x14 + x24 ≥ 90

There are four demand satisfaction constraints — one per tank farm.

Notice the structure: production constraints sum across j (all destinations for one refinery), demand constraints sum across i (all sources for one tank farm). This is the classic transportation problem structure.

Type 3 — Non-negativity Constraints (≥ 0)

You cannot ship a negative amount of fuel. This seems obvious but must be stated explicitly in the mathematical formulation because optimization solvers don't automatically know that negative shipments are physically impossible.

xij ≥ 0 for all i = 1, 2 and j = 1, 2, 3, 4

This applies to all eight decision variables.

The Complete Mathematical Formulation

Putting it all together:

Minimize: TC = 4x11 + 7x12 + 9x13 + 11x14 + 5x21 + 4x22 + 5x23 + 8x24

Subject to:

  • x11 + x12 + x13 + x14 ≤ 150 (LA capacity)

  • x21 + x22 + x23 + x24 ≤ 200 (Houston capacity)

  • x11 + x21 ≥ 100 (Denver demand)

  • x12 + x22 ≥ 80 (KC demand)

  • x13 + x23 ≥ 60 (Nashville demand)

  • x14 + x24 ≥ 90 (Pittsburgh demand)

  • xij ≥ 0 for all i, j (non-negativity)

This is the complete LP formulation — 8 decision variables, 1 objective function, 8 constraints (2 production + 4 demand + technically 8 non-negativity but these are usually stated as a group).

Characterizing the Problem — Linear Program vs MILP

This problem is called a Linear Program (LP) because three conditions are all satisfied simultaneously:

First, the objective function is linear — it's a weighted sum of decision variables to the first power with no nonlinear terms.

Second, all constraints are linear — each constraint is a linear combination of decision variables compared to a constant using ≤, ≥, or =.

Third, the decision variables are continuous — xij can take any non-negative real value, not just integers.

The critical mathematical property of a Linear Program is that it has a single globally optimal solution. This means there are no local optima to get trapped in — any optimization algorithm that finds an optimum for an LP has found the best possible solution. This is a tremendously important practical advantage. You can solve it with confidence that you've found the true best answer.

What if the variables had to be integers? If you required xij to be whole numbers only — whole 100,000 barrel shipments, no fractional shipments — the problem becomes a Mixed Integer Linear Program (MILP). This is far harder to solve because the feasible region is no longer a continuous convex set. MILPs can have local optima and require branch-and-bound or similar methods, as discussed in Lecture 18.

What if the objective or constraints were nonlinear? For example, if shipping cost depended on shipment size in a nonlinear way (economies of scale producing a quadratic cost function), the problem would become a Nonlinear Program (NLP) or Mixed Integer Nonlinear Program (MINLP). These are even harder to solve and may not have a single global optimum.

The Conclusions — Exam-Ready Statements

Optimization theory provides a method to solve large-scale scheduling and planning problems in the chemical industries. Problems that would be intractably complex to solve by intuition or trial and error can be formulated mathematically and solved to global optimality.

Working at enterprise scale allows for efficiencies not possible for smaller concerns. A company with two refineries and four tank farms can find the mathematically optimal shipping strategy that no human scheduler could find reliably by hand, and can do so for any set of costs and demands.

Even multiobjective problems — minimize cost AND minimize carbon footprint AND maximize service reliability — can now be considered using modern optimization frameworks, though they require more sophisticated formulation.

How to Answer Any LP Formulation Question on an Exam

The lecture teaches a four-step process that you should follow in exactly this order:

Step 1: Define all variables — what are you deciding, and what indices do you need? Name every decision variable explicitly with its units.

Step 2: Write the objective function — what are you minimizing or maximizing? Express it as a mathematical function of your decision variables.

Step 3: Write all constraints — production limits, demand requirements, logical constraints, non-negativity. For each constraint identify which direction the inequality points and why.

Step 4: Characterize the problem — is it an LP, MILP, NLP, or MINLP? What does that tell you about the solution properties?

If you follow these four steps in order for any optimization problem on your exam, you will get full credit for the formulation even if you can't solve it numerically.

Likely Exam Questions:

"What are the three categories of scheduling and planning problems?" — Batch planning (what, how much, when to make), logistics (how much to ship where), business planning (where to build plants, how many).

"What is Operations Research and how does it differ from Enterprise-Wide Optimization?" — OR optimizes supply chains with a single objective. EWO includes multiple competing objectives simultaneously across the entire enterprise.

"Write the LP formulation for the jet fuel shipping problem." — Full answer: define xij, write objective as double sum of cij·xij, write capacity constraints as row sums ≤ capacity, write demand constraints as column sums ≥ demand, write non-negativity.

"What makes a problem a Linear Program?" — Linear objective function, linear constraints, continuous decision variables. Key property: single globally optimal solution.

"What is the difference between a Linear Program and a MILP?" — LP has continuous variables. MILP requires some or all variables to be integers. MILP is far harder to solve and may not have a unique global optimum.

"Why must non-negativity constraints be explicitly stated?" — Mathematical optimization solvers do not automatically assume variables are non-negative. Without this constraint, a solver could set some xij to negative values to artificially reduce cost, which is physically meaningless.

"How many decision variables are in the jet fuel LP and what are they?" — 8 decision variables: x11, x12, x13, x14, x21, x22, x23, x24 representing the number of 100,000 bbl shipments from each refinery to each tank farm.

"What type of constraint ensures a refinery doesn't overproduce?" — A production limit constraint using a ≤ inequality, summing all shipments from that refinery across all destinations.

"What type of constraint ensures each tank farm receives enough fuel?" — A demand satisfaction constraint using a ≥ inequality, summing all shipments into that tank farm from all refineries.

"Who is uniquely qualified to formulate these optimization problems and why?" — Engineers, because formulating the problem correctly requires understanding the physical constraints and realities of the process — production capacities, transportation limits, process chemistry — which is the engineer's domain.