13. fejezet - „Futószalag” feladat

13.1. 13.1. A feladat megfogalmazása

Jelölje a személyeket, pedig egy futószalagon lévő munkahelyeket (munkákat). Legyen adva az alábbi táblázat, amelynek (egész) eleme azt jelenti, hogy az munkás a munkát mennyi idő alatt tudja elvégezni. A személyek és a munkák számának azonosnak kell lenni!

A „futószalag” feladat az alábbi sémával jellemezhető:

Mielőtt a feladatot megfogalmaznánk definiáljuk a futószalag ütemidejét. A futószalag addig áll, amíg a futószalag munkahelyein munkavégzés folyik, amikor minden munka befejeződött, akkor a futószalag továbblép. Ezt az állásidőt nevezzük a futószalag továbbítási ütemének vagy röviden a futószalag ütemidejének. A futószalag ütemidejét tehát a futószalagon lévő munkák közül a leghosszabb műveleti idejű határozza meg.

A „futószalag” feladat megfogalmazása:

Rendeljük a személyeket a futószalag munkahelyeihez kölcsönösen egyértelmű módon úgy, hogy a futószalag ütemideje a lehető legkisebb legyen.

A hozzárendelést a szokásos módon olyan döntési változóval jelöljük, amelynek értéke , ha az személy hozzá van rendelve a munkához és , ha nincs.

Matematikai megfogalmazás:

Jelölje a kölcsönösen egyértelmű hozzárendelést.

Meghatározandó a kölcsönösen egyértelmű hozzárendelés úgy, hogy a

mennyiség minimális legyen.

Az olyan optimalizálási feladatokat, amelyekben a célfüggvény valamilyen maximális érték és ennek a maximális értéknek kell a minimumát keresni szűk-keresztmetszet feladatoknak nevezzük.