2012 Single-machine scheduling with a logarithm deterioration function

Research Overview

This study introduces a novel deterioration model using logarithmic functions to represent how job processing times increase over time, providing a more realistic representation of performance degradation in manufacturing systems compared to linear or exponential models.

Key Contributions

Mathematical Modeling:

• Develops a logarithmic deterioration function that captures the gradual increase in processing times as equipment ages or workers become fatigued
• Provides theoretical justification for why logarithmic models better represent certain types of deterioration phenomena
• Establishes mathematical properties of the logarithmic deterioration function including monotonicity and convexity

Optimization Algorithms:

• Derives optimal polynomial-time algorithms for minimizing makespan under logarithmic deterioration
• Develops efficient solution procedures for minimizing total completion time and weighted completion time
• Provides complexity analysis showing that certain problem variants remain tractable despite the non-linear deterioration function

Comparative Analysis:

• Compares logarithmic deterioration with other deterioration models (linear, exponential, power functions)
• Demonstrates scenarios where logarithmic models provide better fit to real-world data
• Shows computational advantages of logarithmic models in certain optimization contexts

Practical Applications:

• Identifies manufacturing scenarios where logarithmic deterioration is most applicable (equipment wear, worker fatigue, environmental factors)
• Provides guidelines for parameter estimation and model calibration
• Demonstrates significant improvements in schedule quality when appropriate deterioration models are used

Impact and Significance

Published in Optimization Letters, this research contributes to the theoretical foundations of scheduling with deteriorating jobs while providing practical tools for manufacturing optimization. The logarithmic deterioration model has influenced subsequent research in non-linear deterioration effects and has found applications in maintenance scheduling and workforce management.

Recommended citation: Peng-Jen Lai, Chin-Chia Wu and Wen-Chiung Lee. (2012). "Single-machine scheduling with a logarithm deterioration function." Optimization Letters. Volume 6, Issue 8, Pages 1719-1730.
Download Paper