generalized assignment problem

Angol

Főnév

generalized assignment problem (tsz. generalized assignment problems)

(informatika) A Generalized Assignment Problem (GAP, általánosított hozzárendelési probléma) egy kombinatorikus optimalizálási probléma, amelyben a cél az, hogy feladatokat (vagy projekteket) rendeljünk hozzá ügynökökhöz (vagy erőforrásokhoz) úgy, hogy:

minden feladatot pontosan egy ügynökhöz rendelünk,
az ügynökök kapacitása nem léphető túl,
és a hozzárendelés összköltsége minimális legyen (vagy haszon maximális).

Ez egy NP-nehéz probléma, azaz nincs ismert polinomidőben futó algoritmus az optimális megoldásra.

🧠 Formális definíció

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.

Döntési változók:

$x_{ij}={\begin{cases}1&{\text{ha az }}j{\text{ feladatot az }}i{\text{-edik ügynök végzi el}}\\0&{\text{különben}}\end{cases}}$

Célfüggvény (költség minimalizálása):

$\min \sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}$

Feltételek:

Minden feladat legyen hozzárendelve egy ügynökhöz:

$\sum _{i=1}^{m}x_{ij}=1\quad \forall j=1,\dots ,n$

Ne lépjük túl az ügynökök kapacitását:

$\sum _{j=1}^{n}r_{ij}x_{ij}\leq b_{i}\quad \forall i=1,\dots ,m$

Bináris változók:

$x_{ij}\in \{0,1\}$

📊 Példakép (gép-feladat hozzárendelés)

	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.

🔁 Megoldási módszerek

Pontos algoritmusok:

Integer Linear Programming (ILP) – pl. CPLEX, Gurobi, CBC
Branch and Bound
Dynamic Programming (kis példákra)

Heurisztikák, metaheurisztikák:

Greedy algoritmus (pl. legolcsóbb megoldás elsőként)
Tabu search
Genetikus algoritmus
Simulated Annealing

🧩 Alkalmazási területek

Projektmenedzsment: Feladatok szétosztása dolgozók között
Gyártás: Gépek kapacitásának optimalizálása
Számítástechnika: Virtuális gépekhez feladatok rendelése
Szállítás: Fuvarfeladatok elosztása járművek között
Cloud computing: Felhős erőforrás-hozzárendelés

📌 Kapcsolat más problémákkal

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

🧮 C++ példa kis GAP-re (greedy)

struct Task {
    int cost[3]; // költségek gépekre
    int req[3];  // szükséges kapacitás
};

int main() {
    const int M = 3; // gépek
    const int N = 4; // feladatok
    int cap[M] = {5, 7, 6};

    Task tasks[N] = {
        {{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[j].req[i] <= cap[i] && tasks[j].cost[i] < minCost) {
                best = i;
                minCost = tasks[j].cost[i];
            }
        }
        if (best != -1) {
            cap[best] -= tasks[j].req[best];
            std::cout << "Task " << j << " -> Machine " << best << "\n";
        } else {
            std::cout << "Task " << j << " cannot be assigned!\n";
        }
    }
}

🧠 Összefoglalás

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

További információk

generalized assignment problem - Szótár.net (en-hu)
generalized assignment problem - Sztaki (en-hu)
generalized assignment problem - Merriam–Webster
generalized assignment problem - Cambridge
generalized assignment problem - WordNet
generalized assignment problem - Яндекс (en-ru)
generalized assignment problem - Google (en-hu)
generalized assignment problem - Wikidata
generalized assignment problem - Wikipédia (angol)