Resource-Constrained Assignment Scheduling

Joseph B. Mazzola and Alan W. Neebe
Additional contact information
Joseph B. Mazzola: Duke University, Durham, North Carolina
Alan W. Neebe: The University of North Carolina, Chapel Hill, North Carolina

Operations Research, 1986, vol. 34, issue 4, 560-572

Abstract: Many resource-constrained assignment scheduling problems can be modeled as 0-1 assignment problems with side constraints (APSC). Unlike the well-known assignment problem of linear programming, APSC is NP-complete. In this paper we define a branch-and-bound algorithm for solving APSC to optimality. The algorithm employs a depth-first, polychotomous branching strategy in conjunction with a bounding procedure that utilizes subgradient optimization. We also define a heuristic procedure for obtaining approximate solutions to APSC. The heuristic uses subgradient optimization to guide the search for a good solution as well as to provide a bound on solution quality. We present computational experience with both procedures, applied to over 400 test problems. The algorithm is demonstrated to be effective across three different classes of resource-constrained assignment scheduling problems. The heuristic generates solutions for these problems that are, on average, within 0.8% of optimality.

Keywords: 627 algorithm for resource-constrained assignment scheduling; 632 heuristic for resource-constrained assignment scheduling (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.4.560 (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:oropre:v:34:y:1986:i:4:p:560-572

Access Statistics for this article

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