Minimizing the total weighted flow time in a single machine with controllable processing times

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. (C) 2003 Elsevier Ltd. All rights reserved.