The Discrete Resource Allocation Problem in Flow Lines

Selcuk Karabati, Panagiotis Kouvelis and Gang Yu
Additional contact information
Selcuk Karabati: Bilkent University, Management Department, Faculty of Business Administration, Bilkent, Ankara 06533, Turkey
Panagiotis Kouvelis: Duke University, The Fuqua School of Business, Durham, North Carolina 27706
Gang Yu: The University of Texas at Austin, Management Science and Information Systems Department, College of Business Administration CBA 5.202, Austin, Texas 78712

Management Science, 1995, vol. 41, issue 9, 1417-1430

Abstract: In this paper we address the discrete resource allocation problem in a deterministic flow line. We assume that the processing times are convex and nonincreasing in the amount of resources allocated to the machines. We 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. We also present a generalization of the formulation for resource allocation problems in acyclic directed graphs. We 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, we address the simultaneous scheduling and resource allocation problem, and we present an approximate and iterative solution procedure for the problem.

Keywords: resource allocation; flow shop scheduling; integer programming; surrogate relaxation (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.41.9.1417 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:41:y:1995:i:9:p:1417-1430

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().