Flow-shop ütemezés - Flow-shop scheduling

Flow-shop ütemezési egy optimalizálási probléma a számítástechnika és operációkutatás . Ez az optimális munkaütemezés egyik változata . Az általános munkahelyi ütemezési probléma csak adott n munkahely J ₁ ,  J ₂ , ...,  J _n változó feldolgozási időt, amelyet át kell ütemezni m gépek különböző feldolgozási teljesítmény, miközben megpróbálja minimalizálni a makespan - az ütemezés teljes hossza (vagyis amikor az összes munka befejezte a feldolgozást). A flow-shop ütemezés néven ismert konkrét változatban minden job pontosan m műveletet tartalmaz . A munka i- edik műveletét az i- edik gépen kell végrehajtani . Egyetlen gép sem képes egyszerre több műveletet végrehajtani. Az egyes munkák minden műveletéhez megadják a végrehajtási időt.

A Flow-shop ütemezés a job-shop ütemezés speciális esete, amikor az összes munkán végrehajtandó műveletek szigorú sorrendben vannak. Az áramlás-üzlet ütemezése a gyártási létesítményekre, valamint a számítási tervekre is vonatkozhat. A flow-shop ütemezési probléma speciális típusa a permutation flow-shop ütemezési probléma, amelyben az erőforrásokon lévő jobok feldolgozási sorrendje a feldolgozás minden következő lépésében megegyezik.

Az optimális munkaütemezési problémák szokásos hárommezős jelölésében a flow-shop változatot F jelöli az első mezőben. Például az " F3 | |${\ displaystyle p_ {ij}}$ " - vel jelölt probléma egy 3 gépes folyamatáruház-probléma, egységnyi feldolgozási időkkel, ahol a cél a maximális befejezési idő minimalizálása. ${\ displaystyle C _ {\ max}}$

Formális meghatározás

Vannak n gépek és m munkahelyeket. Minden feladat pontosan m műveletet tartalmaz . A munka i- edik műveletét az i- edik gépen kell végrehajtani . Egyetlen gép sem képes egyszerre több műveletet végrehajtani. Az egyes munkák minden műveletéhez megadják a végrehajtási időt.

Az egy munkán belüli műveleteket a megadott sorrendben kell végrehajtani. Az első műveletet az első gépen hajtják végre, majd (amikor az első művelet befejeződik) a második műveletet a második gépen, és így tovább az n- edik műveletig. A munkák bármilyen sorrendben végrehajthatók. A probléma meghatározása azt jelenti, hogy ez a munkarend minden gépnél pontosan megegyezik. A probléma az optimális ilyen elrendezés meghatározása, vagyis a lehető legrövidebb teljes munkafuttatással.

Szekvenciális teljesítménymérések (γ)

A szekvenálási probléma megállapítható az S szekvencia meghatározásaként úgy, hogy egy vagy több szekvenálási cél optimális legyen.

1. (Átlagos) áramlási idő, ${\ displaystyle \ sum (w_ {i}) F_ {i}}$
2. Makespan, C _max
3. (Átlagos) késés, ${\ displaystyle \ sum (w_ {i}) T_ {i}}$
4. ....

a teljesítménymérés részletes tárgyalása megtalálható Malakooti (2013).

A flow-shop ütemezés összetettsége

Amint azt Garey és mtsai. (1976) szerint a flow-shop-ütemezési problémák kiterjesztéseinek nagy része NP-nehéz, és ezek közül kevés megoldható optimálisan O-ban (nlogn); például az F2 | prmu | C _max a Johnson-szabály használatával optimálisan megoldható .

A Taillard jelentős referenciaproblémákat jelent a flow-boltok, nyitott üzletek és állásboltok ütemezése során.

Megoldási módszerek

A flow-shop-ütemezési problémák megoldására javasolt módszerek pontos algoritmusok , például elágazás és kötött, valamint heurisztikus algoritmusok , például genetikai algoritmusok közé sorolhatók .

Minimalizálja a gyártási időt, C _max

Az F2 | prmu | C _max és F3 | prmu | C _max a Johnson-szabály használatával optimálisan megoldható, de általános esetben nincs olyan algoritmus, amely garantálja a megoldás optimális működését.

A flow shop n feladatot tartalmaz, amelyek egyidejűleg elérhetőek a nulla időpontban, és amelyeket két gép sorozatokban rendez el, korlátlan tárhely közöttük. Az összes munka feldolgozási ideje biztosan ismert. A munkák minimálisra csökkentése érdekében n munkát kell ütemezni a gépeken. Az alábbiakban ismertetjük a Johnson szabályát a munkák ütemezésére kétgépes áramlásüzletben.

Optimális ütemezésben az i feladat megelőzi a j munkát, ha min {p _1i , p _2j } <min {p _1j , p _2i } . Ahol, p _1i az i feladat feldolgozási ideje az 1. gépen, és p _2i az i feladat feldolgozási ideje a 2. gépen. Hasonlóképpen, p _1j és p _2j a j feladat feldolgozási ideje az 1. és a 2. gépen.

Johnson algoritmusához:

Legyen p _1j a j feladat feldolgozási ideje az 1. gépen

és p _2j a j gép 2. feldolgozási ideje a 2. gépen

Johnson algoritmusa:

1. Form1 készlet, amely tartalmazza az összes olyan feladatot, ahol p _1j <p _2j
2. Form2 készlet, amely tartalmazza az összes p _1j > p _2j feladatot, a p _1j = p _{2j feladatok} bármelyikbe beilleszthetők.
3. A sorrendet az alábbiak szerint alakítsa ki:

   (i) Az 1. készletben szereplő feladat megy először a sorrendben, és növekvő sorrendben megy p _1j (SPT)

   (ii) A 2. készletben szereplő munkák csökkenő sorrendben következnek p _2j (LPT) szerint. A kötelékek önkényesen szakadnak meg.

Ezt a típusú ütemezést SPT (1) –LPT (2) ütemtervnek nevezik.

A rendelkezésre álló megoldási módszerek részletes tárgyalását Malakooti (2013) nyújtja .

Lásd még

• Nyitott üzlet ütemezése
• Munkahely-bolt ütemezése

Hivatkozások