Online Assignment

Decisions are made sequentially as tasks arrive and are typically irrevocable; an assignment cannot be undone later when a better-suited agent becomes available. This is the defining constraint that differentiates online from offline assignment. The algorithm's performance is measured by its competitive ratio, comparing its cumulative outcome against an optimal offline algorithm that knows the entire task sequence in advance.

Performance is formally evaluated using competitive analysis. An algorithm is c-competitive if, for all possible input sequences, its total reward (or cost) is within a factor c of the optimal offline algorithm's reward. For example:

• A 2-competitive algorithm is guaranteed to achieve at least half the optimal reward.
• The competitive ratio quantifies the 'price of not knowing the future.' This analytical framework is central to proving worst-case guarantees for online algorithms like the Greedy Algorithm for bipartite matching.

A canonical and simple online algorithm that assigns each arriving task to the best currently available agent, according to an immediate utility or cost function. While often not optimal, it provides a baseline:

• Advantage: Extremely low computational overhead, suitable for high-frequency task arrivals.
• Limitation: Can make short-sighted decisions that block future, higher-value assignments.
• Guarantee: For bipartite matching where each agent handles one task, the Greedy algorithm is 1/2-competitive; it achieves at least half the value of the optimal offline matching.

To improve performance, algorithms often assume tasks arrive according to a known stochastic model. Common models include:

• Independent and Identically Distributed (i.i.d.): Each task is drawn independently from a fixed, known probability distribution.
• Random Order Model: The set of all tasks is fixed but unknown, and they are presented to the algorithm in a uniformly random permutation. These models allow for algorithms that use sampling or reservation techniques, holding back some capacity for potentially high-value future tasks, leading to better competitive ratios than the purely adversarial worst-case.

In heterogeneous fleet orchestration, online assignment is critical for real-time logistics. Examples include:

• Ride-hailing: Matching passenger requests to nearby drivers of suitable vehicle type.
• Warehouse robotics: Assigning newly arrived picking tasks to the nearest available autonomous mobile robot or manual picker based on current location and payload capacity.
• Food delivery: Dispatching orders to couriers, balancing preparation time, delivery location, and courier efficiency. The algorithm must respect hard constraints like agent capabilities and battery life while optimizing for objectives like minimizing wait time or maximizing throughput.

Online assignment interacts closely with other pillars of dynamic orchestration:

• Dynamic Rebalancing: Acts as a continuous, fine-grained form of rebalancing as tasks arrive.
• Market-Based Task Allocation: Online combinatorial auctions are a decentralized implementation of online assignment.
• Real-Time Scheduling: A specialization where tasks have explicit deadlines, making timeliness part of the assignment utility.
• Service Discovery: The online process of identifying which agents are capable and available for an incoming task is a prerequisite for assignment.

Platforms like Uber and DoorDash use online assignment to match drivers or couriers to incoming trip or delivery requests in real-time. The system must decide within seconds, balancing:

• Minimizing wait time for the customer.
• Maximizing driver utilization and earnings.
• Accounting for dynamic variables like traffic, restaurant prep time, and driver proximity. Algorithms continuously re-evaluate the global state as new requests arrive and driver locations change, making it a classic sequential decision-making problem under uncertainty.

In automated fulfillment centers, a mixed fleet of Autonomous Mobile Robots (AMRs) and manual pickers receives tasks (e.g., 'retrieve item A from bin B') as customer orders stream in. An online assignment engine:

• Instantly assigns each picking task to the most suitable available robot or worker.
• Considers real-time constraints like battery levels, current location, and payload capacity.
• Dynamically re-routes agents if a higher-priority order arrives or a path becomes blocked. This enables just-in-time material handling, dramatically reducing order cycle times compared to batch-based offline planning.

Large-scale compute clusters (e.g., AWS, Google Cloud) use online schedulers to assign incoming user jobs (virtual machines, containers, batch processes) to physical servers. The orchestrator must:

• Place each job upon submission without knowing future job arrivals.
• Optimize for multiple objectives like minimizing energy cost, maximizing hardware utilization, and meeting Service Level Agreements (SLAs).
• Handle heterogeneous resources like GPUs, high-memory machines, and different CPU architectures. This is a massive-scale bin packing problem where 'bins' (servers) have complex, multi-dimensional capacities and 'items' (jobs) arrive continuously.

When a user loads a webpage, an auction for an ad impression occurs in milliseconds. Demand-Side Platforms (DSPs) use online assignment algorithms to decide, for each incoming impression:

• Which advertiser's ad to bid on behalf of, based on user profile and campaign goals.
• How much to bid in the real-time auction.
• Whether the impression fits the remaining budget and pacing goals for the day. Each decision is made in isolation, without knowledge of future user visits, making it a stochastic optimization problem where the algorithm must learn and adapt to shifting bid landscapes.

The overarching real-time process of assigning work items from a shared pool to a heterogeneous set of agents. Unlike online assignment, which is defined by its sequential, unknown-future decision process, dynamic task allocation is the general field that includes both online and offline assignment strategies. It continuously matches tasks to agents based on:

• Real-time agent state (location, battery, capability)
• System objectives (throughput, cost, fairness)
• Environmental constraints (zones, traffic, obstacles)

The class of algorithms that make task allocation decisions with complete a priori knowledge of all future tasks and agent states. This allows for globally optimal planning, in contrast to the sequential, myopic decisions of online assignment. It is applicable in controlled environments where the entire problem instance is known beforehand. Key techniques include solving the assignment problem using the Hungarian algorithm or formulating it as a multi-objective optimization to find solutions on the Pareto frontier.

A fundamental combinatorial optimization problem in operations research that aims to find a minimum-cost or maximum-profit matching between two sets of items, such as tasks and agents. It is the mathematical core of many allocation systems. For online assignment, the problem is solved repeatedly as new tasks arrive. The classic solution is the Hungarian Algorithm, which finds an optimal matching in polynomial time for a static, known set.

Two fundamental dispatching models that define the control flow of task allocation.

• Push-Based Assignment: A centralized model where a scheduler proactively assigns tasks to agents as soon as they become available, based on a global view. This is common in online assignment systems where a central orchestrator makes all decisions.
• Pull-Based Assignment: A decentralized model where agents, upon becoming idle, actively request or 'pull' the next task from a shared queue. This reduces central coordination overhead and is often paired with work stealing for load balancing.

The discipline of allocating tasks to resources where correct system behavior depends not only on logical results but also on the timeliness of those results. Online assignment is inherently a real-time scheduling problem, as decisions must be made sequentially as tasks arrive, often with hard or soft deadlines. This introduces constraints like:

• Task preemption: Interrupting a lower-priority task.
• Dynamic rebalancing: Redistributing tasks in response to changes.
• Fault-tolerant allocation: Ensuring completion despite agent failures.

The process of simultaneously optimizing for several, often conflicting, system objectives. Online assignment algorithms must balance these in real-time. Common objectives include:

• Minimizing makespan (total completion time)
• Maximizing throughput (tasks completed per hour)
• Minimizing travel cost or energy use
• Ensuring fairness in agent workload Solutions are evaluated on the Pareto frontier, where no objective can be improved without worsening another. An allocation policy defines the trade-off between these goals.