×

Resource-constrained assignment scheduling. (English) Zbl 0609.90087

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.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI