Nyitott üzlet ütemezése - Open-shop scheduling
A nyitott bolt ütemezése vagy a nyitott bolt ütemezése ( OSSP ) optimalizálási probléma a számítástechnika és a műveletek kutatásában . Ez az optimális munkaütemezés egyik változata . Az általános munkahelyi ütemezési probléma csak adott n munkahely J 1 , J 2 , ..., 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 nyílt bolt ütemezésének nevezett konkrét változatban minden egyes feladat O 1 , O 2 , ..., O n műveletek sorozatából áll, amelyeket tetszőleges sorrendben kell feldolgozni . A problémát először Teofilo F. Gonzalez és Sartaj Sahni tanulmányozta 1976-ban.
Az optimális munkaütemezési problémák standard hárommezős jelölésében az első mezőben a nyitott bolt változatát O -val jelöljük . Például az " O3 | | " - vel jelölt probléma egy 3 gépes munkaüzem problémája, egység feldolgozási időkkel, ahol a maximális teljesítési idő minimalizálása a cél.
Meghatározás
A nyitott bolt ütemezési problémájának bemenete n job készletből, egy másik m munkaállomás készletből és egy kétdimenziós táblából áll, hogy mennyi időt töltsön el az egyes munkák az egyes munkaállomásokon (esetleg nulla). Minden munka egyszerre csak egy munkaállomáson dolgozható fel, és minden munkaállomás egyszerre csak egy munkát dolgozhat fel. Azonban a szaküzlet problémájával ellentétben a feldolgozási lépések sorrendje szabadon változhat. A cél az, hogy minden egyes munkaidőhöz hozzárendeljenek egy munkát, amelyet az egyes munkaállomások feldolgoznak, úgy, hogy egyazon munkaidőhöz ne legyen két munka egyszerre hozzárendelve, egyszerre két munkaállomáshoz ne legyen hozzárendelve minden feladat minden munkaállomáshoz a kívánt ideig. A szokásos minőség mércéje az a megoldás, hogy makespan , hogy mennyi idő kezdetétől a menetrend (az első feladat a munkát egy munkaállomás) a végén (a befejezés idejét az utolsó feladat az utolsó munkaállomás).
Számítási bonyolultság
A nyitott bolt ütemezési problémája polinom időben megoldható azoknak az eseteknek, amelyeknek csak két munkaállomása vagy csak két feladata van. Megoldható polinomidőben is, amikor az összes nem nulla feldolgozási idő megegyezik: ebben az esetben a probléma ekvivalenssé válik egy olyan kétoldalas gráf élének kiszínezésével , amelynek csúcsai a munkák és a munkaállomások, és amelynek minden munka-munkaállomás pár él amelynek nem nulla feldolgozási ideje van. A színezés egy élének színe annak az időszegmensnek felel meg, amelyen a munka-munkaállomás pár feldolgozását ütemezik. Mivel a vonalas grafikonok a páros gráfban a tökéletes grafikonok , páros gráfban lehet szélén színű polinomiális időben.
Három vagy több munkaállomás, vagy három vagy több munka esetében, eltérő feldolgozási idővel, a nyitott bolt ütemezése NP-nehéz .
Kapcsolódó problémák
- A munka-bolt ütemezése hasonló probléma, de még további korlátozással - a műveleteket meghatározott sorrendben kell végrehajtani.
- A flow-shop ütemezése egy job-shop ütemezés, de további áramlási korlátozással - minden műveletet egy adott gépen kell végrehajtani.