Online Scheduling

The defining constraint of online scheduling is the lack of future knowledge. Decisions must be made incrementally as tasks arrive, without awareness of future job characteristics, arrival times, or durations. This models real-world logistics where customer orders, machine breakdowns, or traffic conditions are revealed over time.

• Contrast with Offline Scheduling: Offline algorithms have complete problem data upfront.
• Uncertainty Types: Includes unknown job arrivals, stochastic processing times, and dynamic resource availability.
• Impact: Forces the use of competitive analysis to evaluate algorithm performance against a hypothetical optimal offline clairvoyant scheduler.

Once a scheduling decision is made—such as assigning a task to a specific robot or starting a job on a machine—it cannot be reversed without significant cost. This commitment must be made with only current and historical data.

• Real-World Analogy: Dispatching an autonomous mobile robot (AMR) to a picking station; recalling it mid-route is inefficient.
• Algorithmic Consequence: Emphasizes the need for robust heuristics that perform well across many possible futures, rather than seeking a single perfect plan.
• Exception: Some preemptive online models allow job interruption, but this still involves an irrevocable decision to preempt.

Performance is measured via competitive ratio, a worst-case guarantee comparing the online algorithm's cost (e.g., makespan, total completion time) to the optimal offline cost. An algorithm is c-competitive if, for all possible input sequences, its cost is at most c times the optimal offline cost.

• Formula: cost(online) ≤ c * cost(optimal_offline) + α, where α is a constant.
• Example: The classic Greedy algorithm for load balancing is 2-competitive for makespan minimization.
• Purpose: Provides a rigorous, mathematical bound on performance degradation due to uncertainty, assuring system designers of predictable worst-case behavior.

Online schedulers must process new information and produce decisions within strict time constraints, often on the order of milliseconds for robotic fleet control. This precludes the use of computationally expensive exact optimization methods for each decision.

• Requirement: Low-latency decision cycles are critical for dynamic task allocation and real-time replanning.
• Enabling Techniques: Use of constant-time heuristics, pre-computed policies, or lightweight model predictive control (MPC) with a very short receding horizon.
• Trade-off: Speed is prioritized over optimality, accepting good-enough solutions to maintain system reactivity.

Theoretical online scheduling often considers an adversarial input model, where future job arrivals are designed to force poor performance. Designing for this worst-case scenario ensures the algorithm is resilient to unexpected or highly variable demand patterns.

• Adversarial Queueing Theory: Studies stability of network schedules under worst-case traffic.
• Practical Implication: Algorithms proven robust against an adversary will handle real-world volatility, such as sudden bulk orders or agent failures in a warehouse.
• Alternative Models: Stochastic models assume known probability distributions for arrivals, enabling better average-case performance.

In practical systems like fleet orchestration, pure online scheduling is often embedded within a replanning loop. A receding horizon controller frequently solves a refreshed, short-horizon optimization problem using the latest state and predictions.

• Architecture: 1. Observe current system state. 2. Solve a scheduling problem for the next N minutes. 3. Execute the immediate decision. 4. Repeat at the next time step.
• Benefit: Balances the reactivity of online decision-making with the improved coordination of short-term planning.
• Connection to MPC: This is a direct application of Model Predictive Control, a cornerstone of modern autonomous system coordination.

In real-time logistics, tasks like picking orders or moving materials arrive continuously. Online scheduling algorithms assign these tasks to the nearest or most suitable autonomous mobile robot (AMR) or manual vehicle as they appear, without knowing the full day's workload. This minimizes agent idle time and response latency.

• Example: An e-commerce warehouse uses an online scheduler to instantly assign newly created pick orders to available robots, optimizing for proximity and current battery level.

Operational disruptions—such as a blocked aisle, agent failure, or a new high-priority task—require immediate schedule adjustments. Online schedulers continuously re-optimize the remaining plan from the current state. This is a form of receding horizon control, where only the immediate next actions are fixed.

• Core Mechanism: Upon detecting an exception, the scheduler re-solves a truncated version of the problem, considering all uncompleted tasks and current agent states, to generate a new feasible schedule.

For electric fleets, charging is a non-preemptible task with dynamic deadlines. Online scheduling must interleave work assignments with charging cycles without knowing future energy demands precisely. Algorithms use threshold-based policies (e.g., send to charger at 20% battery) or predictive models of energy consumption to avoid deadlock where all agents are simultaneously discharged.

• Key Constraint: Scheduling must respect capacity constraints of charging stations and the time required to recharge.

In mixed fleets, some tasks require human operators (e.g., complex kitting, quality inspection). Online scheduling must dynamically queue these tasks for human workstations and synchronize the flow of robots delivering and retrieving work. This involves managing buffer zones and temporal constraints to prevent robot congestion at human stations.

• Challenge: Unpredictable human task completion times add significant uncertainty that the scheduler must absorb.

High-priority tasks (e.g., urgent expedite, safety-related moves) can arrive at any moment. An online scheduler must preempt current plans, potentially reassigning or delaying lower-priority jobs. Effective strategies include defining preemption rules and calculating the minimal-cost insertion point for the urgent task.

• Metric Impact: This often increases the makespan of lower-priority tasks, requiring careful trade-off analysis between responsiveness and overall throughput.

A theoretical lens for evaluating online algorithms. Since the optimal offline schedule is unknown, performance is measured by the competitive ratio: the worst-case ratio between the online algorithm's cost and the optimal offline cost. For example, a 2-competitive algorithm is never worse than twice the optimal.

• Common Strategy: Greedy algorithms like 'always assign to the nearest available agent' are simple but may have poor competitive ratios. More sophisticated algorithms use delay or batching strategies to improve this guarantee.

A Markov Decision Process (MDP) is the foundational mathematical framework for modeling sequential decision-making under uncertainty. It provides the formal structure for online scheduling problems, defining:

• States: The current configuration of the system (e.g., agent locations, task backlog).
• Actions: The decisions available to the scheduler (e.g., assign task X to robot Y).
• Transition Probabilities: The stochastic model of how the system evolves after an action.
• Reward Function: The immediate cost or benefit of taking an action in a given state. Online scheduling algorithms, particularly those using Reinforcement Learning, are often solutions to MDPs where future job arrivals and durations are unknown.

Model Predictive Control (MPC), or Receding Horizon Control, is a dominant online control strategy that solves a finite-horizon optimization problem at each decision epoch. It is a core technique for implementing online scheduling in dynamic physical systems like fleets. The process is:

1. Predict: Use a model (e.g., of traffic, task duration) to forecast system behavior over a short future window.
2. Optimize: Solve for the optimal sequence of actions over that horizon.
3. Execute: Implement only the first action from the optimized plan.
4. Repeat: At the next time step, re-solve with updated state information, moving the horizon forward. This approach explicitly handles constraints (capacity, time windows) and provides a principled way to incorporate short-term forecasts while acknowledging long-term uncertainty.

Stochastic Programming is an optimization framework for decision-making under uncertainty where problem parameters (e.g., job processing times, travel durations) are modeled as random variables with known probability distributions. It contrasts with online scheduling's sequential, real-time nature by often considering a two-stage or multi-stage structure:

• First-Stage Decisions: 'Here-and-now' decisions made before uncertainty is realized.
• Recourse Decisions: 'Wait-and-see' adaptive actions taken after uncertainty is revealed. The objective is to minimize the expected total cost. While often computationally intensive for real-time use, its formulations provide benchmarks and inspiration for designing robust online policies that account for probabilistic futures.

Robust Optimization is a methodology that seeks solutions which remain feasible and perform acceptably for all possible realizations of uncertain parameters within a predefined uncertainty set. It is a worst-case approach that prioritizes absolute constraint satisfaction over average performance. In the context of online scheduling, robust techniques might be used to design policies that guarantee no collisions or deadline misses, provided disturbances (e.g., agent delay) stay within a bounded set. This is crucial for safety-critical fleet operations. The trade-off is typically conservatism; robust solutions may be less efficient under normal conditions than those from stochastic or adaptive approaches.

Competitive Analysis is the theoretical framework used to evaluate the performance of online algorithms, including online schedulers, in the absence of probabilistic assumptions about the future. An online algorithm is said to be c-competitive if, for any input sequence, its cost is at most c times the cost of an optimal offline algorithm that knows the entire future in advance.

• Competitive Ratio (c): The worst-case performance guarantee. A ratio of 2 means the online algorithm is never worse than twice the optimal offline solution. This analysis provides fundamental performance limits and is used to prove the quality of algorithms like the greedy algorithm for certain online scheduling variants, offering deterministic guarantees instead of probabilistic or empirical ones.

A Digital Twin and Discrete-Event Simulation (DES) are critical enabling technologies for developing and testing online scheduling algorithms.

• Digital Twin: A virtual, data-driven replica of the physical fleet and its environment. It receives real-time telemetry and provides a sandbox for simulating 'what-if' scenarios to evaluate scheduling decisions before they are deployed.
• Discrete-Event Simulation (DES): The underlying modeling technique within a digital twin. It represents the system as a sequence of events (e.g., 'task arrives', 'robot finishes move'), allowing for the efficient evaluation of complex scheduling policies over long time horizons. Together, they allow for the offline stress-testing of online schedulers against historical or synthetic data, tuning parameters, and validating robustness before live deployment.