In theoretical scheduling, we often assume a world of perfect fluidity: tasks can be paused (preempted) at any moment and instantly moved (migrated) to any available processor. In reality, modern computing environments—from cloud data centers to fog-based IoT networks—are far more rigid. Once a financial transaction or a neural network inference batch begins, it must typically run to completion on the same hardware to avoid massive state-management overhead or data-locality penalties.
This research direction explores the "rigidity gap"—the mathematical and practical cost of scheduling when tasks are non-preemptive and non-migratory.
The Preemption Gap
The core challenge of non-preemptive scheduling is the loss of adaptability. In a preemptive system, a high-priority job arriving at time $t$ can immediately displace a lower-priority job. In a non-preemptive system, that high-priority job must wait, potentially missing its deadline.
Philippe Baptiste, Christoph Dürr, and their colleagues highlight in Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted Throughput that this lack of interruption significantly increases computational complexity. While preemptive versions of these problems often have efficient polynomial-time solutions, their non-preemptive counterparts frequently become NP-hard or require much higher competitive ratios in online settings. As Kevin Schewior and Lin Chen 0009 note in New Results on Online Resource Minimization, without the ability to pause, algorithms struggle to adapt to "bursty" arrivals, often requiring a linear number of extra machines to match the performance of an optimal offline scheduler.
The Migration Barrier
Even if a task is interruptible, moving it between machines (migration) is often prohibitively expensive due to the cost of transferring memory state or maintaining data locality. Janardhan Kulkarni and colleagues demonstrate in Tight Bounds for Online Vector Scheduling that non-migratory constraints force a scheduler to live with its mistakes. Every assignment is a permanent commitment; an error in initial placement cannot be rectified by later rebalancing, forcing the scheduler to account for the long-term impact of every single decision.
This is particularly visible in MapReduce and big data environments. Evripidis Bampis and Ioannis Milis argue in Energy Efficient Scheduling of MapReduce Jobs that tasks are often pre-assigned to specific processors to preserve data locality. This restriction prevents the system from using dynamic task placement to optimize for energy efficiency or load balancing.
Commitment and the Power of Slack
A recurring concept in this field is commitment: the requirement that once a provider accepts a job, they must finish it. This is a standard Service Level Agreement (SLA) in cloud computing, as discussed by Weidong Ma and Tao Qin in Online Mechanism Design for Cloud Computing.
Intuitively, commitment should make scheduling much harder. However, a breakthrough by Franziska Eberle, Nicole Megow, and Kevin Schewior in Online Throughput Maximization on Unrelated Machines: Commitment is No Burden proves otherwise. They show that if jobs have even a small amount of "slack" (the difference between a job's processing time and its deadline), a scheduler can achieve competitive ratios similar to those of non-commitment models.
The intuition behind their "Region Algorithm" is to partition time into segments based on job laxity. By only committing to jobs that fit within these calculated regions, the scheduler ensures it doesn't "lock up" its resources so tightly that it cannot handle future high-value arrivals.
Domain-Specific Rigidity
The impact of these constraints varies across domains:
- IoT and Fog Computing: Abolfazl Younesi and Muhammad Shafique explain that fog nodes are often too resource-constrained to support the context-switching required for preemption, making non-preemptive models the only viable option for real-time reliability.
- Medical Monitoring: In hospital settings, YUNFAN ZHAO shows that once a vital sign monitor is assigned to a patient, it cannot be easily reassigned, creating a "permanent transition" in resource availability that standard scheduling models fail to capture.
- Machine Learning: Minghao Yan and Shivaram Venkataraman note that batch-level constraints in neural network inference prevent sub-batch preemption, leading to potential latency violations if a long-running batch cannot be interrupted.
By treating non-preemption and non-migration not as "missing features" but as fundamental constraints, this research direction provides the mathematical tools necessary to build robust, real-world systems that can't afford the luxury of pausing.