Toewijzingsproblemen

Toewijzingsproblemen vormen een klasse van optimalisatieproblemen waarin een set taken moet worden toegewezen aan een set middelen of agenten. Het doel is meestal om de totale kosten te minimaliseren of de totale winst te maximaliseren, met de voorwaarde dat elke taak aan precies één agent wordt toegewezen en elke agent aan precies één taak (in het klassieke, gebalanceerde geval). Bij ongelijke aantallen taken en agenten kunnen dummy taken of dummy agenten worden toegevoegd om het probleem in een vierkante vorm te brengen.

Wiskundig kan een toewijzingsprobleem als volgt worden geformuleerd. Laat I de taken en J de agenten voorstellen, en cij i,j de kosten van het toewijzen van taak i aan agent j. Beslissingsvariabelen x i,j nemen waarde 1 aan wanneer taak i aan agentj wordt toegewezen en 0 anders. Het doel is doorgaans minimalisatie van de totale kosten: min sum_{i in I} sum_{j in J} c_{i,j} x_{i,j}. De beperkingen zijn: voor elke taak i geldt sum_{j in J} x_{i,j} = 1 en voor elke agent j geldt sum_{i in I} x_{i,j} = 1 (in gebalanceerde vormen). Voor ongebalanceerde gevallen worden vaak dummy taken of agenten toegevoegd met nul- of vastgestelde kosten.

Oplossingsmethoden: de klassieke oplossing is de Hungarian algorithm (ook wel Kuhn-Munkres-algoritme), met een tijdscomplexiteit van O(n^3) voor een n bij n-matrix. Andere benaderingen zijn lineaire programmering, netwerkstroommodellen en heuristieken voor grotere of minder gestructureerde varianten.

Varianten en gerelateerde problemen omvatten onder meer het Generalized Assignment Problem (GAP), waarbij capaciteitsbeperkingen van agenten bestaan, evenals verschillende ongebalanceerde of kosten- en winstgerelateerde formuleringen. Toepassingen komen voor in personeel- en shiftplanning, productie- en machine-toewijzing, crew scheduling, en het koppelen van studenten aan projecten.