Article ID: | iaor2005905 |
Country: | Netherlands |
Volume: | 47 |
Issue: | 2/3 |
Start Page Number: | 123 |
End Page Number: | 140 |
Publication Date: | Oct 2004 |
Journal: | Computers & Industrial Engineering |
Authors: | Guo Y., Lim A., Rodrigues B., Yu S. |
We study the problem of minimizing total flow time on a single machine with job release times. This problem is NP-complete for which there is no constant ratio approximation algorithm. Our objective is to study experimentally how well, on average, the problem can be solved. The algorithm we use produces non-preemptive schedules converted from preemptive ones. We evaluate average solution quality for the problem to identify the characteristics of difficult instances. Results obtained are compared with those recently obtained by other researchers. Based on extensive experiments, we also develop an empirical model to predict solution quality using interpolation.