Approximation algorithms for minimizing the total weighted earliness on machines scheduling

Abstract

Minimizing the total weighted earliness is not well-studied objective in scheduling theory, which is very little understood from the point of view of approximation algorithms. In an attempt to make progress, we study the approximability of minimum total weighted earliness with a modified objective which includes an additive the total weighted completion time. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in Just-In-Time production systems.Keyword: Scheduling, Weighted Earliness, Approximation