We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A constrained matching problem.
- Authors
Hefner, Andreas; Kleinschmidt, Peter
- Abstract
We show that certain manpower scheduling problems can be modeled as the following constrained matching problem. Given an undirected graph G = (V,E) with edge weights and a digraph D = (V,A). A Master/Slave-matching (MS-matching) of G with respect to D is a matching of G such that for each arc (u, ν) ∈ A for which the node u is matched, the node v is matched, too. The MS-Matching Problem is the problem of finding a maximum-weight MS-matching. Let k(D) be the maximum size of a (weakly) connected component of D. We prove that MS-matching is an NP-hard problem even if G is bipartite and k(D) ≤ 3. Moreover, we show that in the relevant special case where k(D) ≤ 2, the MS-Matching Problem can be transformed to the ordinary Matching Problem.
- Subjects
PRODUCTION scheduling; LABOR supply; MATHEMATICAL models; MANAGEMENT; PRODUCTION control
- Publication
Annals of Operations Research, 1995, Vol 57, Issue 1-4, p135
- ISSN
0254-5330
- Publication type
Article
- DOI
10.1007/BF02099694