generalized assignment problem (tsz. generalized assignment problems)
Ez egy NP-nehéz probléma, azaz nincs ismert polinomidőben futó algoritmus az optimális megoldásra.
Legyen:
m
ügynök (pl. gépek, dolgozók),n
feladat (pl. munkák),c_{ij}
a költség, ha j
feladatot az i
ügynök hajtja végre,r_{ij}
az i
ügynöknél a j
feladat által igényelt erőforrás,b_i
az i
ügynök kapacitása.
Feladat 1 | Feladat 2 | Feladat 3 | Kapacitás | |
---|---|---|---|---|
Gép A | c=5, r=2 | c=6, r=4 | c=4, r=3 | b=5 |
Gép B | c=4, r=3 | c=7, r=2 | c=3, r=2 | b=6 |
Cél: minden feladatot rendelj egy géphez úgy, hogy ne lépd túl a kapacitást, és a költségek összege minimális legyen.
Probléma | GAP specializációja? |
---|---|
Klasszikus Assignment Problem (AP) | Igen – nincs kapacitáskorlát |
Bin Packing | Rokon probléma – kapacitáskihasználás |
Knapsack problem | Egy gépre nézve GAP = knapsack |
Vehicle Routing Problem (VRP) | GAP része lehet az alproblémának |
struct Task {
int cost; // költségek gépekre
int req; // szükséges kapacitás
};
int main() {
const int M = 3; // gépek
const int N = 4; // feladatok
int cap = {5, 7, 6};
Task tasks = {
{{3, 2, 4}, {2, 1, 3}},
{{5, 3, 2}, {3, 2, 2}},
{{4, 6, 3}, {1, 3, 2}},
{{3, 2, 1}, {2, 1, 2}}
};
for (int j = 0; j < N; ++j) {
int best = -1;
int minCost = 1e9;
for (int i = 0; i < M; ++i) {
if (tasks.req <= cap && tasks.cost < minCost) {
best = i;
minCost = tasks.cost;
}
}
if (best != -1) {
cap -= tasks.req;
std::cout << "Task " << j << " -> Machine " << best << "\n";
} else {
std::cout << "Task " << j << " cannot be assigned!\n";
}
}
}
Fogalom | Leírás |
---|---|
GAP | Hozzárendelési probléma, kapacitáskorlátokkal |
NP-nehéz | A probléma méretének növekedésével robbanásszerűen nő a keresési tér |
Cél | Minimális költségű, kapacitáson belüli hozzárendelés |
Alkalmazás | Logisztika, gyártás, cloud, menedzsment |