EFFICIENT HEURISTICS TO MINIMIZE TOTAL FLOW TIME WITH RELEASE DATES

This paper addresses the one machine scheduling problem to minimize total flow time with different release dates. This problem is known to be strongly NP-hard. We prove a sufficient and necessary condition for local optimality which can also be considered as a priority rule and propose some efficient heuristics using this condition. The algorithm performances are evaluated with respect to classical heuristics. The worst-case performances are also provided.