2010 Single-machine scheduling with a nonlinear deterioration function

Research Overview

This paper extends the classical single-machine scheduling framework by incorporating nonlinear deterioration functions, addressing the limitation of previous models that assumed linear or simple exponential deterioration patterns.

Key Contributions

Nonlinear Deterioration Modeling:

• Introduces general nonlinear functions to model deterioration effects that reflect more complex real-world scenarios
• Develops mathematical frameworks for handling arbitrary nonlinear deterioration patterns
• Provides conditions under which optimal solutions can be efficiently computed

Algorithmic Development:

• Designs polynomial-time algorithms for specific classes of nonlinear deterioration functions
• Establishes computational complexity results for various objective functions under nonlinear deterioration
• Develops approximation algorithms for computationally intractable cases

Theoretical Analysis:

• Proves optimality conditions for makespan minimization under general nonlinear deterioration
• Derives structural properties of optimal schedules that guide algorithm design
• Establishes worst-case performance bounds for proposed algorithms

Practical Relevance:

• Demonstrates applications in manufacturing systems where deterioration follows complex patterns (equipment degradation, environmental effects, cumulative fatigue)
• Provides parameter estimation methods for calibrating nonlinear deterioration functions from empirical data
• Shows significant improvements in schedule performance when realistic deterioration models are employed

Impact and Significance

Published in Information Processing Letters (SCI Impact Factor: 0.877), this concise but impactful paper has advanced the theoretical understanding of scheduling under realistic deterioration conditions. The nonlinear deterioration framework has influenced subsequent research in maintenance scheduling, production planning, and resource management, providing foundations for more sophisticated models of system degradation.

Recommended citation: Peng-Jen Lai and Wen-Chiung Lee. (2010). "Single-machine scheduling with a nonlinear deterioration function." Information Processing Letters. Volume 110, Issue 11, Pages 455-459.
Download Paper