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

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

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics, programming: dynamic
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.