Article ID: | iaor1993997 |
Country: | Netherlands |
Volume: | 12 |
Issue: | 5 |
Start Page Number: | 321 |
End Page Number: | 330 |
Publication Date: | Nov 1992 |
Journal: | Operations Research Letters |
Authors: | Chu Chengbin |
Keywords: | heuristics |
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. The paper proves a sufficient and necessary condition for local optimality which can also be considered as a priority rule and proposes some efficient heuristics using this condition. The algorithm performances are evaluated with respect to classical heuristics. The worst-case performances are also provided.