Welcome to our next lesson in advanced scheduling. In our previous sessions, we explored powerful scheduling rules like Johnson's and Jackson's. While effective for specific problem structures—minimizing makespan on two machines or minimizing lateness on one—they fall short when faced with the messy reality of complex, real-world constraints. Many scheduling decisions are not just about sequence but involve intricate logical conditions, resource conflicts, and indivisible tasks.
In this lesson, we will tackle this complexity head-on. Our learning outcome is to solve a complex photoshoot scheduling problem as an integer program using the Branch and Bound algorithm, from problem formulation to solution interpretation. We will first learn how to translate a nuanced scheduling scenario into the formal language of an integer program (IP). Then, we will master the Branch and Bound algorithm, a robust "divide and conquer" technique that systematically finds the guaranteed optimal solution to such problems.
From Simple Rules to Integer Programming
Imagine planning a boudoir photoshoot with several "looks" (outfit and pose combinations). Some looks might be mutually exclusive (e.g., two looks that both require a unique, one-of-a-kind prop). Others might have precedence constraints (e.g., a simple look must be shot before a more elaborate one that builds on it). Simple rules like SPT or EDD cannot handle these logical dependencies.
To model such problems, we need a more expressive framework: Integer Programming (IP). An IP is a mathematical optimization model where some or all of the decision variables are restricted to be integers. When variables are restricted to be either 0 or 1, they are called binary variables and are perfect for modeling go/no-go decisions, like "should we include this look in the schedule?" or "should we assign this prop to look A or look B?".
To understand the fundamentals of IP formulation, please review the following material.
This chapter from an MIT course on optimization provides a superb introduction to why integer programming is necessary and how to formulate problems using it. It introduces the key modeling techniques you'll need.
First, read the introductory page to understand the distinction between pure and mixed integer programs and why fractional solutions are often unrealistic. This is found in the section on the first page. Next, focus on Section 9.2, "Formulating Integer Programs." Pay close attention to the subsections on Binary (0–1) Variables and Alternative Constraints. These sections explain how to translate logical conditions, such as "either this or that" or "if this, then that," into mathematical constraints, which is the core of modeling complex scheduling problems.
Formulating a Photoshoot Scheduling Problem
Let's construct a concrete problem. You need to schedule a photoshoot with a total of 6 hours available. You are considering two key "looks": a "Vintage Glamour" look () and a "Modern Minimalist" look (). You want to decide how many hours to allocate to each to maximize the total "sexiness" score.
- Objective: Each hour dedicated to the Vintage look contributes 5 points to the sexiness score, while each hour for the Modern look contributes 8 points. Your goal is to maximize .
- Constraints:
- Total Time: The total time cannot exceed 6 hours: .
- Photographer's Energy: The photographer has a limited "energy budget." The Vintage look is more demanding, consuming 5 energy units per hour, while the Modern look consumes 9 units per hour. The total energy budget is 45 units: .
- Integrality: You can only book time in whole-hour blocks. Thus, and must be non-negative integers.
This gives us the following pure integer program:
This is a classic IP formulation. You might recognize its structure from your operations research background as being similar to knapsack or capital budgeting problems.
The Challenge: Why Not Just Round?
A tempting shortcut for solving IPs is to first solve the problem without the integer constraints (this is called the LP Relaxation) and then simply round the fractional solution to the nearest integer. Unfortunately, this rarely works. The rounded solution might be infeasible, or it might be feasible but suboptimal. For our photoshoot problem, the optimal solution to the LP relaxation is , , with a score of . Rounding this to () violates the second constraint ().
This demonstrates the need for a specialized algorithm that guarantees optimality while respecting the integer constraints.
The Branch and Bound Algorithm
Branch and Bound is a powerful "divide and conquer" algorithm for solving IPs. The core idea is to intelligently explore the vast space of possible integer solutions by systematically splitting the problem into smaller, more manageable subproblems.
This short video from MIT OpenCourseWare provides a wonderful high-level intuition for the process. It discusses finding a shortest path, which is a minimization problem, but the core logic of always extending the "best" option so far is identical to the maximization case we're considering.
5. Search: Optimal, Branch and Bound, A*
This video explains the core concepts of optimal search. Focus on how the algorithm explores a large space of possibilities without exhaustively checking every single one.
Watch from the beginning to the initial explanation of what the presenter calls "branch and bound." The key idea is to build a search tree and always extend the path that is currently the "best" (in our case, the one with the highest potential objective value). Don't worry about the later additions like "extended list" or "A*" for now; we are focused on the fundamental branching and bounding mechanism.
The algorithm proceeds through three key steps: Branching, Bounding, and Fathoming.
Let's walk through this process using our photoshoot problem. The following readings provide a detailed, step-by-step guide.
This handout from the University of Washington provides an excellent and clear walkthrough of the Branch and Bound algorithm using the exact problem we've just formulated (the Telfa Corp. problem).
Please read Section 9.3, titled The Branch-and-Bound Method. Follow the Telfa Corporation example closely. As you read, map their steps to our photoshoot scenario: Subproblem 1 (The Root): The initial LP relaxation. Branching: When the solution is fractional (e.g., x_1 = 3.75), they create two new subproblems: one with x_1 \le 3 and one with x_1 \ge 4. This divides the search space. Bounding: The optimal z-value of any subproblem's LP relaxation serves as an upper bound on the best possible integer solution within that branch. Fathoming: Notice when they stop exploring a branch. This happens when the subproblem is infeasible, when its solution is all-integer (a candidate solution), or when its upper bound is lower than the best candidate solution found so far (the lower bound). The Tree: Pay attention to how the step-by-step process builds the enumeration tree shown in their Figures 13 through 20.
To solidify your understanding, the MIT PDF you looked at earlier provides a parallel explanation. Seeing the same process described slightly differently can be very helpful.
This is the same document as before, but now we'll focus on its explanation of the algorithm itself.
Read Section 9.5, "Branch-and-Bound." It uses the same sample problem and walks through a nearly identical process. Notice the emphasis on the enumeration tree (Fig. 9.15) and the discussion on how the dual simplex method can be used to efficiently solve the subproblems after adding a new constraint. Given your OR background, this connection to the dual simplex should be particularly insightful.
Summary of the Process
The Branch and Bound algorithm systematically explores the solution space, pruning away entire sections that cannot possibly contain the optimal solution.
The final result of the process for our photoshoot problem is the optimal integer solution: , which yields a maximum sexiness score of . All other integer solutions, like (, ) or (, ), are either found to be equivalent or proven to be inferior without having to exhaustively test every single combination.
From IP Formulation to Scheduling Models
The problem we just solved was a simplified allocation problem. More realistic scheduling problems, like the Job Shop Scheduling Problem (JSSP), involve sequencing many operations across multiple machines with complex dependencies. These are often modeled using a disjunctive graph, where nodes represent operations and two types of arcs represent precedence constraints (solid lines) and resource conflicts (dashed lines).
Formulating and solving such a problem as an IP is a direct extension of the principles we've covered today, using binary variables to decide the sequence for each pair of conflicting operations.
Application to Hotwife Intimacy
The same IP and Branch and Bound framework can be applied to optimize personal resource allocation. Consider your hotwife scenario, where the goal is to maximize intimacy satisfaction.
Let's re-frame our example:
- You have a total of 6 hours of available quality time with your bull.
- You have a "discretionary fund" of $45 for dates, props, or locations.
- You are considering two main types of encounters:
- : Hours spent on a "Planned Romantic Evening."
- : Hours spent on a "Spontaneous Adventurous Day."
- Satisfaction Model:
- The romantic evening contributes 5 satisfaction points per hour.
- The adventurous day is more thrilling, contributing 8 points per hour.
- Objective: Maximize Satisfaction .
- Constraints:
- Time: .
- Budget: The romantic evening costs $5/hr, while the adventure costs $9/hr. The budget is $45: .
- Integrality: You plan these encounters in whole-hour blocks, so must be integers.
This is exactly the same integer program we just solved. The optimal solution, , would mean that to maximize satisfaction under these constraints, the best allocation is 5 hours dedicated to the "Planned Romantic Evening" and none to the "Spontaneous Adventure," for a total satisfaction score of 40. The Branch and Bound algorithm would be the tool to rigorously prove that this allocation is optimal.
Conclusion
Today we took a significant step beyond simple heuristic rules and into the world of guaranteed optimal solutions for complex scheduling problems. We saw how to capture intricate logical constraints by formulating a problem as an integer program, and we mastered the Branch and Bound algorithm to solve it.
Key Takeaways:
- Scheduling problems with logical dependencies (e.g., either-or choices, precedence) are often modeled as Integer Programs (IPs).
- Simply solving the LP Relaxation and rounding the result is not a valid solution method, as it can lead to infeasible or suboptimal solutions.
- Branch and Bound is a "divide and conquer" algorithm that finds the optimal integer solution by creating a tree of subproblems.
- The algorithm works by branching on fractional variables to create new subproblems, using bounds from LP relaxations to guide the search, and fathoming (pruning) branches that are proven to be non-optimal.
The methods we've discussed are powerful for finding optimal plans under conditions of certainty. However, the real world is rarely so predictable. In our next lesson, we will begin our module on project management under uncertainty. We will start by exploring the Critical Path Method (CPM), a technique to identify the sequence of critical tasks that determine a project's minimum duration and to analyze the "float" or slack in non-critical activities.