Article ID: | iaor2005511 |
Country: | United Kingdom |
Volume: | 31 |
Issue: | 13 |
Start Page Number: | 2279 |
End Page Number: | 2289 |
Publication Date: | Nov 2004 |
Journal: | Computers and Operations Research |
Authors: | Kaspi Moshe, Shabtay Dvir |
Keywords: | heuristics, programming: dynamic |
The scheduling problem of a single machine with the minimum total weighted flow time criterion is extended to the case of allocating a continuously nonrenewable limited resource where the model of operations is assumed to be a specific convex function of the amount of resource consumed. The optimal resource allocation is obtained for any arbitrary job sequence. The computational complexity of the general problem remains an open question, but we present and analyze some special cases that are solvable by using polynomial time algorithms. An exact dynamic programming algorithm for small to medium size problems is suggested, while for large-scale problems we suggest some heuristic algorithms which appear to be very efficient.