Solution of a bilevel optimistic scheduling problem on parallel machines

This paper addresses a strong NP-hard bilevel optimistic scheduling problem on uniform parallel machines, where a leader minimizes weighted tardy jobs and a follower minimizes total completion time, by establishing its complexity via reduction from Numerical 3-Dimensional Matching and proposing exact solution methods including a dynamic programming algorithm, a MIP formulation, and a branch-and-bound approach with column generation that effectively solve instances up to 80 jobs and 4 machines.

The Gist

Imagine a factory floor in the "Factory of the Future" (Industry 4.0). This isn't just a place with machines; it's a smart ecosystem where a central Boss (the Leader) and several Autonomous Robots (the Followers) work together, but they have very different goals.

This paper is about solving a complex scheduling puzzle that happens between these two parties. Here is the story of the problem and how the authors solved it.

The Characters and the Conflict

The Boss (The Leader):
The Boss is in charge of the big picture. Their main worry is reputation. They want to make sure as many orders as possible are delivered on time. If an order is late, it costs money and hurts the company's image. The Boss's goal: Minimize the number of late deliveries.

The Robots (The Followers):
The Boss picks a list of orders to run, but then hands them over to a team of robots. These robots are very efficient, but they are obsessed with speed. They don't care about deadlines; they just want to finish all the work as quickly as possible to save energy and time. Their goal: Minimize the total time it takes to finish everything.

The Twist (The "Optimistic" Rule):
Here is where it gets tricky. Sometimes, there isn't just one way for the robots to finish the work quickly. There might be ten different schedules that all take the exact same amount of time.

• The Optimistic Scenario: The Boss gets to hope for the best. If the robots have a choice between ten fast schedules, they will pick the one that happens to result in the fewest late deliveries for the Boss. The Boss is betting on the robots being "nice."

The Problem: A Game of Tetris with Moving Walls

Imagine you are playing Tetris.

1. The Boss decides which blocks (jobs) to put on the board.
2. The Robots then have to stack those blocks as fast as possible.
3. The Boss wants to pick blocks that, when stacked by the robots, result in the fewest blocks falling off the edge (being late).

The catch? The factory has two types of machines:

• Super-Speed Machines: They work twice as fast.
• Standard Machines: They work at normal speed.

The Boss has to decide: Which jobs go on the Super-Speed machines and which go on the Standard ones? And which jobs should we even accept?

This is incredibly hard because the Boss has to predict exactly how the Robots will rearrange the blocks to be fastest, and then figure out which of those "fastest" arrangements is the "nicest" for the Boss.

Why is this so hard? (The Complexity)

The authors proved that this problem is NP-hard in the strong sense.

The Analogy:
Imagine trying to find the perfect combination of keys to open a lock.

• If you have 10 keys, you can try them all quickly.
• If you have 80 keys, the number of combinations is so huge that even the fastest supercomputer in the world would take longer than the age of the universe to check them all one by one.

The authors showed that no matter how clever you are, you can't just use a simple formula to solve this. It's a "brute force" nightmare where you have to explore millions of possibilities.

The Solution: How They Cracked the Code

Since they couldn't solve it with a simple formula, they built a sophisticated "search engine" to find the answer. They used three main tools:

1. The "Block" Strategy (Structural Insight)
The authors realized that the Robots' "fastest" schedules aren't random. They follow a pattern, like bricks in a wall.

• The Analogy: Imagine the Robots always build their schedule in "blocks" of jobs. Within a specific block, the order of jobs doesn't change the total time, but it does change if they are late.
• The Win: Instead of looking at every single job individually, they looked at these "blocks." This reduced the chaos significantly.

2. The "Smart Guessing" Engine (Branch-and-Bound)
They built a computer algorithm that acts like a detective.

• It starts with a big question: "What if we pick these specific jobs?"
• It branches out into smaller questions: "If we pick Job A, what happens to Job B?"
• Pruning: If the detective sees a path that leads to a terrible result (too many late jobs), it immediately cuts that branch off and stops looking there. This saves massive amounts of time.

3. The "Lower Bound" Calculator (Column Generation)
To know when to stop searching, the algorithm needs a "best-case scenario" estimate.

• The Analogy: Imagine you are trying to pack a suitcase. You want to know if it's possible to fit everything. Instead of packing it perfectly first, you quickly throw the biggest items in to see if they might fit. If they don't even fit in the "quick throw" version, you know for sure the perfect version won't work either.
• This "quick throw" calculation (Column Generation) tells the algorithm: "You can stop looking down this path; it's impossible to do better than this."

The Results: How Far Did They Get?

The authors tested their method on a computer.

• Small Problems: They solved problems with up to 80 jobs and 4 machines perfectly.
• The Limit: They found that once you go beyond 80 jobs, the problem becomes too heavy for even their super-smart algorithm. It's like trying to solve a Sudoku puzzle with 1,000 squares instead of 81; the math just gets too heavy.

The Takeaway

This paper is a victory for optimization. It shows that even in a complex world where a Boss and Robots have different goals, we can still find the perfect schedule using:

1. Understanding the hidden patterns (Blocks).
2. Smart guessing (Branch-and-Bound).
3. Quick estimates to rule out bad ideas (Column Generation).

While they can't solve every size of problem yet, they have built a powerful tool that helps factories in the "Industry 4.0" era make better decisions, ensuring that the Boss gets their on-time deliveries while the Robots stay happy and fast.

Technical Summary

Here is a detailed technical summary of the paper "Solution of a bilevel optimistic scheduling problem on parallel machines" by Schau et al.

1. Problem Definition

The paper addresses a bilevel optimization problem within the context of uniform parallel machine scheduling. The scenario involves two hierarchical agents: a Leader and a Follower.

• Context: The setting models Industry 4.0 environments with autonomous cyber-physical systems (CPS). The system (Leader) dispatches orders to CPS units (Followers). The machines operate at two distinct speeds: high speed ($V_1$) and low speed ($V_0$), potentially due to maintenance status or machine health.
• The Leader's Decision: The Leader selects a subset of $n$ jobs from a total pool of $N$ jobs and assigns them to the Followers. The Leader's objective is to minimize the weighted number of tardy jobs ($\sum w_j U_j^L$).
• The Follower's Decision: Once the subset of jobs is selected, the Follower schedules them on the $m$ uniform machines. The Follower's primary objective is to minimize the total completion time ($\sum C_j^F$).
• Optimistic Bilevel Setting: The problem assumes an optimistic stance. If the Follower has multiple schedules that achieve the optimal total completion time, the Follower chooses the one that is most favorable to the Leader (i.e., minimizes the weighted number of tardy jobs).
• Formal Notation: The problem is denoted as $Q|V_i \in \{V_0, V_1\}, OPT-n | \sum C_j^F, \sum w_j U_j^L$.

2. Methodology and Theoretical Foundations

2.1 Structural Properties (Block Structure)

The authors analyze the Follower's sub-problem ($Q|V_i \in \{V_0, V_1\} | \sum C_j$).

• Block Structure: They prove that optimal schedules for minimizing total completion time on uniform machines with two speeds exhibit a specific block structure. Jobs are grouped into blocks based on machine speeds and positions. Within these blocks, jobs can be permuted without affecting the total completion time, provided the processing times follow specific ordering rules (Longest Processing Time - LPT).
• Implication: This structure reduces the search space for the Follower's optimal solutions, allowing the Leader to focus on which permutation within these blocks minimizes the tardiness penalty.

2.2 Complexity Analysis

The paper establishes rigorous complexity results:

• Strong NP-Hardness: The authors prove that the bilevel problem is strongly NP-hard. This is demonstrated via a polynomial-time reduction from the Numerical 3-Dimensional Matching (NUM-3DM) problem.
• Follower's Sub-problem:
  • If job sizes are equal, the problem is solvable in polynomial time ($O(n \log n)$).
  • With arbitrary processing times on identical machines, the problem is weakly NP-hard (reduced from Even-Odd Partition).
  • With arbitrary processing times on a variable number of machines, it is strongly NP-hard.
• Approximability: The problem is shown to be inapproximable in polynomial or pseudo-polynomial time unless P = NP.
• Polynomial Hierarchy: Due to the existence of a Mixed Integer Programming (MIP) formulation, the problem is not complete for the second level of the polynomial hierarchy ($\Sigma_2^P$), confirming it is strongly NP-hard but potentially solvable via exact methods for small instances.

2.3 Exact Algorithms

The authors propose three exact approaches:

1. Mixed Integer Programming (MIP) Formulation:

   • A concise MIP model is developed using the block structure.
   • It utilizes binary variables to assign jobs to specific locations within blocks and constraints to enforce the block filling rules and completion time calculations.
   • The model has $O(N(n+m))$ variables and $O(N^2 + Nm^2)$ constraints.

2. Dynamic Programming (DP):

   • A moderately exponential-time DP algorithm is designed based on the block structure.
   • It works backward from the last block, filling them with jobs while tracking machine completion times and the set of available jobs.
   • Complexity: $O(2^m (\sum p_j)^m N n^2 \log n)$. This is theoretically significant but practically limited to small $m$.

3. Branch-and-Bound (BaB) with Column Generation:

   • Branching Scheme: The algorithm branches on the blocks ($B_1, \dots, B_{b_{max}}$) rather than individual jobs. At each node, it decides whether to select a job and assign it to an available location in the current block.
   • Lower Bound (Column Generation): To compute tight lower bounds, the authors extend the column generation approach (Van den Akker et al., 1999).
     • Master Problem: A set-covering problem selecting machine schedules.
     • Pricing Problem: Solved via a specialized dynamic programming algorithm to find machine schedules with negative reduced cost. This pricing problem handles equal-size jobs efficiently ($O(n_g^3)$) using a modified knapsack-like logic.
   • Memorization: The algorithm employs a "Branch-and-Memorize" strategy. It stores data structures of explored nodes (partial schedules, remaining jobs, completion times) to prune dominated subproblems based on dominance conditions derived in Theorem 2.7.
   • Upper Bound: A heuristic improves the initial solution found by the MIP solver.

3. Key Contributions

1. Complexity Proof: First proof of strong NP-hardness for this specific class of optimistic bilevel scheduling problems on uniform parallel machines.
2. Structural Insight: Identification and utilization of the block structure for the Follower's problem, which is crucial for both the complexity proofs and the design of exact algorithms.
3. Algorithmic Innovation:
   • Development of a Column Generation scheme tailored for bilevel scheduling to compute lower bounds.
   • Integration of Memorization (Branch-and-Memorize) to handle the combinatorial explosion of the search tree.
   • A specialized pricing algorithm for equal-size jobs that improves computational efficiency.
4. MIP Formulation: A novel MIP model that explicitly rules out the possibility of the problem being in the second level of the polynomial hierarchy.

4. Experimental Results

• Setup: Experiments were conducted on randomly generated instances with up to 80 jobs and 4 machines (2 high-speed, 2 low-speed).
• Comparison: The proposed Branch-and-Bound (BaB) algorithm was compared against a standard MIP solver (CPLEX).
• Performance:
  • BaB Superiority: The BaB algorithm generally outperformed CPLEX, solving more instances to optimality within a 300-second time limit.
  • Scalability: Both methods struggled with larger instances. The BaB algorithm could solve instances up to $N=80$ for specific configurations, but performance degraded significantly as the number of machines increased (due to the exponential growth of the branching factor $O((m+1)^N)$).
  • Hard Instances: For "hard" instances (where $n \approx N/2$), BaB explored significantly fewer nodes than MIP (up to a factor of 2 reduction) for 2 machines, though MIP performed slightly better on node count for 4 machines in some cases.
  • Limitations: The problem remains extremely challenging; instances larger than 80 jobs or with more machines are currently out of reach for these exact approaches.

5. Significance and Future Directions

• Theoretical Impact: The paper bridges the gap between bilevel optimization theory and practical scheduling, providing a rigorous complexity classification for a problem relevant to modern manufacturing (Industry 4.0).
• Practical Relevance: It offers a framework for decision-making in hierarchical systems where a central planner must account for the optimal reaction of decentralized agents.
• Future Work: The authors suggest developing heuristic approaches (e.g., Beam Search leveraging the BaB structure or Machine Learning techniques) to tackle larger instances, as exact methods hit a scalability wall.

In summary, this paper provides a comprehensive theoretical and algorithmic treatment of a complex bilevel scheduling problem, proving its hardness and offering the first exact solution methods capable of handling moderate-sized instances through sophisticated integration of block structures, column generation, and memorization.