The discrete resource allocation problem in flow lines

The discrete resource allocation problem in flow lines

0.00 Avg rating0 Votes
Article ID: iaor19961495
Country: United States
Volume: 41
Issue: 9
Start Page Number: 1417
End Page Number: 1430
Publication Date: Sep 1995
Journal: Management Science
Authors: , ,
Keywords: scheduling, programming: integer
Abstract:

In this paper the authors address the discrete resource allocation problem in a deterministic flow line. They assume that the processing times are convex and nonincreasing in the amount of resources allocated to the machines. The authors consider the resource allocation problem for a fixed sequence of jobs for various performance criteria (makespan, weighted sum of completion times, cycle time for cyclic schedules), and develop a formulation of the problem as a convex program, where the number of constraints grows exponentially with the number of jobs and machines. They also present a generalization of the formulation for resource allocation problems in acyclic directed graphs. The authors demonstrate that the problem is NP-complete in the strong sense and present an effective solution procedure. The solution procedure is an implicit enumeration scheme where a surrogate relaxation of the formulation is used to generate upper and lower bounds on the optimal objective function value. Finally, the authors address the simultaneous scheduling and resource allocation problem, and they present an approximate and iterative solution procedure for the problem.

Reviews

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