Minimizing the Weighted Makespan with Restarts on a Single Machine

Basic Information

• Paper ID: 2510.09589
• Title: Minimizing the Weighted Makespan with Restarts on a Single Machine
• Authors: Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton, Rob van Stee, Corinna Wambsganz
• Classification: cs.DS (Data Structures and Algorithms)
• Publication Date: October 10, 2025
• Paper Link: https://arxiv.org/abs/2510.09589

Abstract

This paper investigates the problem of minimizing weighted makespan with restart mechanisms on a single machine. The restart mechanism is similar to preemption but weaker: jobs can be interrupted but must restart from the beginning rather than resume from the interruption point. The objective is to minimize the weighted makespan, defined as the maximum weighted completion time across all jobs. The research establishes a lower bound of 1.4656 on the competitive ratio for deterministic online algorithms. For the special case where all jobs have identical processing times, a deterministic online algorithm is designed and analyzed, improving the competitive ratio to better than 1.3098, and a lower bound of 1.2344 is proven for this case.

Research Background and Motivation

Problem Definition

The core problem studied in this paper is the weighted makespan minimization problem in single-machine scheduling, denoted as 1|rj, online, restart|WCmax. Each job j possesses the following characteristics:

• Processing time pj
• Arrival time rj
• Weight wj

The objective function is WCmax = max{wjCj}, where Cj is the completion time of job j.

Research Significance

1. Theoretical Value: Makespan minimization is a fundamental problem in scheduling theory with important theoretical implications
2. Practical Applications: In cloud computing and operating system task scheduling scenarios, jobs may be interrupted and restarted due to the arrival of higher-priority tasks
3. Model Innovation: The restart model better reflects certain practical application scenarios compared to traditional preemption-resume models

Limitations of Existing Approaches

• Li 12 established a competitive ratio lower bound of 2 for the single-machine problem and provided an online algorithm with competitive ratio 3
• Chai et al. 4 improved the single-machine competitive ratio to 2
• For the identical processing time case, Li proposed an optimal algorithm with competitive ratio (√5+1)/2
• Liang et al. 13 studied the problem under limited restart constraints, which differs from the unlimited restart model in this paper

Core Contributions

1. Established Lower Bounds for the General Case: Proved that any deterministic online algorithm has a competitive ratio of at least R₁ ≈ 1.4656, where R₁ is the real root of the equation R₁³ - R₁² - 1 = 0
2. Designed Improved Algorithms: Proposed the Limited Largest Weight (LLW) algorithm for the unit processing time case with competitive ratio better than 1.3098
3. Provided Tight Analysis: Proved a lower bound of R₂ ≈ 1.2344 for the unit processing time case, where R₂ is the real root of the equation 4R₂³ - R₂² - 6 = 0
4. Perfected the Theoretical Framework: Provided a systematic analysis methodology for scheduling problems with restarts

Methodology Details

Problem Formulation

Input: A sequence of jobs arriving online, each job j with arrival time rj, processing time pj, and weight wj Output: A scheduling scheme that minimizes the weighted makespan WCmax = max{wjCj} Constraints: Jobs can be restarted (from the beginning) but cannot resume from the interruption point

Core Algorithm: Limited Largest Weight (LLW)

The LLW algorithm's core idea is to balance between greedy strategies (prioritizing heavy jobs) and time efficiency. The algorithm rules are as follows:

1. Initial Phase: The first arriving job starts processing immediately
2. Decision Rules:
   • If a job starts at time t ≥ (2-R)/(R-1) ≈ 2.2279, run the LW algorithm without allowing interruptions
   • If a job starts at time t < (2-R)/(R-1), run the LW algorithm allowing interruptions until time t' = (t+2)/R - 1
3. LW-phase Concept: For jobs starting at time t < (2-R)/(R-1), the interval (t, t') is called the LW-phase
4. Interruption Update: If an interruption occurs at time ti, update t := ti and recalculate t'

Technical Innovations

1. Time Threshold Design: Determine critical time points (2-R)/(R-1) through mathematical analysis, allowing interruptions before this point and prohibiting them afterward
2. Dynamic Threshold Adjustment: The end time of the LW-phase is dynamically adjusted based on interruption times
3. Competitive Ratio Analysis: Systematically analyze the algorithm's competitive ratio through the "good set" concept

Theoretical Analysis

Lower Bound Proof Methods

Lower Bound for the General Case (Theorem 1): Construct an adversarial instance:

• Time 0: Job 1 arrives with w₁=1, p₁=1
• Time r₂ = 1/(R₁(R₁-1)) - 1: Job 2 arrives with w₂=1/(R₁-1), p₂=0

Prove through case analysis that any algorithm's competitive ratio is at least R₁ ≈ 1.4656.

Lower Bound for the Unit Processing Time Case (Theorem 3): Construct more complex adversarial instances involving a sequence of 4 jobs, proving the competitive ratio is at least R₂ ≈ 1.2344.

Upper Bound Proof Methods

Proof of Theorem 2 employs proof by contradiction and case analysis:

1. Assume the existence of a minimal counterexample
2. Define the "good set" concept
3. Progressively eliminate all possible scheduling patterns through 5 key properties

Key properties include:

• Property 1: Job 1 arrives at time s₁ and starts immediately
• Property 2: There exists an interrupted job satisfying specific time constraints
• Properties 3-5: Progressively restrict possible scheduling patterns

Experimental Setup

Theoretical Verification Methods

This paper is primarily theoretical work, employing mathematical proofs rather than experimental validation:

1. Lower Bound Construction: Construct adversarial instances and optimize parameters
2. Computer-Assisted Verification: Use computers to optimize adversarial instance parameters
3. Exact Analysis: Obtain precise competitive ratio bounds by solving equation systems

Key Parameters

• R₁ ≈ 1.4656: Lower bound on competitive ratio for the general case
• R ≈ 1.3098: Competitive ratio of LLW algorithm for unit processing time case
• R₂ ≈ 1.2344: Lower bound on competitive ratio for unit processing time case

Main Results

Summary of Competitive Ratio Results

Comparison with Existing Work

• Improvement Magnitude: Compared to Li's results, improved from (√5+1)/2 ≈ 1.618 to 1.3098 for the unit processing time case
• Theoretical Contribution: First to provide tight analysis under the restart model

Algorithm Performance Guarantees

The LLW algorithm guarantees:

• Competitive ratio strictly less than 1.3098
• This bound is tight (there exist instances achieving this ratio)

Related Work

Scheduling Theory Foundations

• Graham et al. 9 established the three-field notation system for scheduling problems
• Classical makespan minimization problems have been extensively studied

Weighted Makespan Research

• Feng and Yuan 16 first considered the single-machine weighted makespan problem
• Li 12 established lower bound 2 and upper bound 3 for the online version
• Chai et al. 4 improved the competitive ratio to 2

Restart Model Research

• Shmoys et al. 17 first introduced the restart concept
• The restart model has been proven to improve online algorithm performance under various objective functions 1,2,11,18
• Liang et al. 13 studied the variant with limited restart counts

Conclusions and Discussion

Main Conclusions

1. Theoretical Bounds: Established competitive ratio bounds for the weighted makespan problem with restarts
2. Algorithm Design: The LLW algorithm achieves significant improvements for the unit processing time case
3. Analysis Methodology: Provided a systematic competitive ratio analysis framework

Limitations

1. Existing Gap: An approximately 0.075 gap remains between upper and lower bounds for the unit processing time case
2. General Case: Only lower bounds are provided for the general processing time case, lacking a matching upper bound algorithm
3. Practical Applications: Theoretical analysis lacks validation in practical application scenarios

Future Directions

1. Narrowing the Gap: Further improve algorithms or strengthen lower bounds to reduce the theoretical gap
2. General Case Algorithm: Design algorithms with competitive ratio approaching 1.4656 for the general processing time case
3. Extended Models: Consider more complex scheduling environments such as multi-machine and parallel batch processing

In-Depth Evaluation

Strengths

1. Theoretical Rigor: Mathematical proofs are complete with clear logic
2. Technical Innovation: The LLW algorithm design is clever, balancing greedy strategies and efficiency considerations
3. Analysis Depth: Provides systematic analysis framework through the "good set" concept
4. Practical Relevance: The restart model better aligns with certain practical application scenarios

Weaknesses

1. Theory-Oriented: Lacks practical application validation and experimental evaluation
2. Larger Gap: Lacks upper bound algorithms for the general case
3. Complexity: The proof process is relatively complex with room for improved readability

Impact

1. Theoretical Contribution: Provides important theoretical foundations for the restart model in scheduling theory
2. Methodological Value: Analysis methods can be generalized to other scheduling problems
3. Practical Potential: Has application prospects in cloud computing, real-time systems, and other domains

Applicable Scenarios

1. Cloud Computing: Virtual machine scheduling with task restarts
2. Real-Time Systems: Preemptive scheduling of high-priority tasks
3. Operating Systems: Process scheduling with time-slice round-robin mechanisms

References

This paper cites 20 relevant references covering classical works and recent advances in scheduling theory, providing a solid theoretical foundation for the research. Key references include Graham et al.'s scheduling problem classification system, Li's online scheduling algorithms, and Shmoys et al.'s pioneering work on restart models.

Overall Assessment: This is a high-quality theoretical computer science paper that makes important contributions to scheduling theory. Although primarily focused on theoretical analysis, it provides important theoretical guidance for practical applications. The paper's mathematical analysis is rigorous and the results have significant academic value.