Mazzola, Joseph B.; Neebe, Alan W. Resource-constrained assignment scheduling. (English) Zbl 0609.90087 Oper. Res. 34, 560-572 (1986). 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, with 0.8% of optimality. Cited in 1 ReviewCited in 28 Documents MSC: 90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) 65K05 Numerical mathematical programming methods Keywords:resource-constrained assignment scheduling; NP-complete; branch-and-bound algorithm; depth-first, polychotomous branching strategy; subgradient optimization; heuristic procedure; approximate solutions; computational experience PDFBibTeX XMLCite \textit{J. B. Mazzola} and \textit{A. W. Neebe}, Oper. Res. 34, 560--572 (1986; Zbl 0609.90087) Full Text: DOI