ISSN: 1813-0410

Author : A. Mohammed, Hussam

Approximation algorithms for minimizing the total weighted earliness on machines scheduling

Hussam A. Mohammed

journal of kerbala university, Volume 4, Issue 3, Pages 23-33

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