Állásbolt ütemezése - Job-shop scheduling

Job-shop ütemezési vagy a munka-shop probléma ( JSP ) 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 feladat ü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 - a az ütemezés teljes hossza (azaz amikor az összes munka befejezte a feldolgozást). A job-shop ütemezés néven ismert specifikus változatban minden munka O ₁ , O ₂ , ..., O _n műveletek halmazából áll, amelyeket meghatározott sorrendben kell feldolgozni ( elsőbbségi korlátozások ). Minden műveletnek van egy saját gépe, amelyen fel kell dolgozni, és egy adott munka során csak egy művelet feldolgozható. Gyakori kikapcsolódás a rugalmas job shop, ahol minden művelet feldolgozható egy adott készlet bármelyik gépén (az egyes szettek gépei azonosak).

A név eredetileg jött a menetrendi munkahelyek egy bértermelőről , de a téma széles alkalmazások túl típusát pl. Ez a probléma az egyik legismertebb kombinatorikus optimalizálási probléma, és ez volt az első probléma, amellyel Graham 1966 -ban bemutatta a versenyképes elemzést . A legjobb problémamegoldások az alapmodell és a tervezési célkitűzés között Taillard.

Az optimális munkaütemezési problémákra vonatkozó szabványos hárommezős jelölésben a job-shop változatot J jelöli az első mezőben. Például a " J3 | | ${\ displaystyle p_ {ij}}$ " jelzésű probléma egy 3 gépből álló job-shop probléma egységfeldolgozási idővel, ahol a cél a maximális befejezési idő minimalizálása. ${\ displaystyle C _ {\ max}}$

Probléma variációk

A probléma számos változata létezik, beleértve a következőket:

A gépek rendelkezhetnek másolatokkal (rugalmas munkakör duplikált gépekkel), vagy azonos gépek csoportjába tartozhatnak (rugalmas munkabolt).
A gépek megkövetelhetnek egy bizonyos szakadékot a munkák között, vagy semmiféle tétlenséget.
A gépek sorrendfüggő beállításokkal rendelkezhetnek.
Az objektív funkció lehet a minta minimalizálása, az L _p norma, késleltetés, maximális késés stb. Többcélú optimalizálási probléma is lehet.
A munkáknak lehetnek korlátai, például egy i feladatnak be kell fejeznie a j feladat elindítását (lásd a munkafolyamatot ). Ezenkívül a célfüggvény több kritérium is lehet.
A feladatok különböző gépekhez tartozhatnak.
Determinisztikus (rögzített) feldolgozási idők vagy valószínűségi feldolgozási idők.

NP-keménység

Mivel az utazó ügynök probléma az, NP-nehéz , a munka-shop probléma szekvencia-függő beállítás egyértelműen is NP-nehéz, mivel a TSP egy speciális esete a JSP egyetlen feladat (a városok a gépek és az eladó is a munka).

Problémaábrázolás

A diszjunktív gráf az egyik népszerű modell, amelyet a job-shop ütemezési problémapéldák leírására használnak.

A probléma matematikai megfogalmazása a következőképpen történhet:

Legyen és legyen két véges halmaz . Figyelembe véve az ipari eredetű a probléma, az úgynevezett gépek és nevezzük munkahelyeket . ${\ displaystyle M = \ {M_ {1}, M_ {2}, \ pöttyök, M_ {m} \}}$ ${\ displaystyle J = \ {J_ {1}, J_ {2}, \ pöttyök, J_ {n} \}}$ ${\ displaystyle \ displaystyle M_ {i}}$ ${\ displaystyle \ displaystyle J_ {j}}$

Hagyja halmaza összes sorozatos rendelt feladatok gépek, oly módon, hogy minden munkát végzi minden gép pontosan egyszer; Az elemek mátrixként írhatók , amelyek oszlopai sorrendben felsorolják a gép által elvégzendő feladatokat . Például a mátrix ${\ displaystyle \ displaystyle \ {\ mathcal {X}}}$ ${\ displaystyle x \ in {\ mathcal {X}}}$ ${\ displaystyle n \ x m}$ ${\ displaystyle \ displaystyle i}$ ${\ displaystyle \ displaystyle M_ {i}}$

{\ displaystyle x = {\ begin {pmatrix} 1 & 2 \\ 2 & 3 \\ 3 & 1 \ end {pmatrix}}}

azt jelenti, hogy a gép elvégzi a három feladatot a sorrendben , míg a gép a sorrendben elvégzi a feladatokat . ${\ displaystyle \ displaystyle M_ {1}}$ ${\ displaystyle \ displaystyle J_ {1}, J_ {2}, J_ {3}}$ ${\ displaystyle \ displaystyle J_ {1}, J_ {2}, J_ {3}}$ ${\ displaystyle \ displaystyle M_ {2}}$ ${\ displaystyle \ displaystyle J_ {2}, J_ {3}, J_ {1}}$

Tegyük fel azt is, hogy van valamilyen költségfüggvény . A költségfüggvény "teljes feldolgozási idő" -ként értelmezhető, és kifejezheti az időket , a gép munkájának költségeit/idejét . ${\ displaystyle C: {\ mathcal {X}} \ to [0,+\ infty]}$ ${\ displaystyle C_ {ij}: M \ alkalommal J \ - [0,+\ infty]}$ ${\ displaystyle \ displaystyle M_ {i}}$ ${\ displaystyle \ displaystyle J_ {j}}$

A job-shop problémája az, hogy olyan feladatok kiosztását találjuk meg , amelyek minimálisak, vagyis nincs ilyen . ${\ displaystyle x \ in {\ mathcal {X}}}$ ${\ displaystyle \ displaystyle C (x)}$ ${\ displaystyle y \ in {\ mathcal {X}}}$ ${\ displaystyle \ displaystyle C (x)> C (y)}$

Az ütemezés hatékonysága

Az ütemezés hatékonysága egy ütemezéshez definiálható a gép teljes tétlensége és a teljes feldolgozási idő aránya szerint, az alábbiak szerint:

${\ displaystyle C '= 1+{\ sum _ {i} l_ {i} \ over \ sum _ {j, k} p_ {jk}} = {Cm \ over \ sum _ {j, k} p_ {jk }}}$

Itt van a gép üresjárati ideje , a gyártmány és a gépek száma. Vegye figyelembe, hogy a fenti meghatározás szerint az ütemezési hatékonyság egyszerűen a gépek számához és a teljes feldolgozási időhöz normalizált gyártási idő. Ez lehetővé teszi az erőforrások felhasználásának összehasonlítását a különböző méretű JSP példányok között. ${\ displaystyle l_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle C}$ ${\ displaystyle m}$

A végtelen költségek problémája

Az egyik első probléma, amellyel foglalkozni kell a JSP -ben, hogy sok javasolt megoldás végtelen költséggel jár: azaz létezik ilyen . Valójában meglehetősen egyszerű példákat találni arra, hogy két gép zsákutcába kerüljön , és így mindegyik várja a másik következő lépését. ${\ displaystyle x _ {\ infty} \ itt: {\ mathcal {X}}}$ ${\ displaystyle C (x _ {\ infty}) =+\ infty}$ ${\ displaystyle x _ {\ infty}}$

Főbb eredmények

Graham már 1966 -ban megadta a List ütemezési algoritmust, amely $(2 -1/ m)$ versenyképes, ahol m a gépek száma. Bebizonyosodott továbbá, hogy a List ütemezés az optimális online algoritmus 2 és 3 géphez. A Coffman – Graham algoritmus (1972) egyenletes hosszúságú munkákhoz szintén optimális két gép számára, és $(2 -2/ m)$ versenyképes. 1992 -ben Bartal, Fiat, Karloff és Vohra bemutattak egy algoritmust, amely 1.986 versenyképes. Karger, Philips és Torng 1994-ben bemutatott egy 1.945-ös versenyképes algoritmust. 1992-ben Albers egy másik algoritmust adott meg, amely 1.923-as versenyképes. Jelenleg a legismertebb eredmény egy Fleischer és Wahl által adott algoritmus, amely 1.9201 versenyképességi arányt ér el.

Az 1.852 alsó határt Albers mutatta be. A Taillard-példányoknak fontos szerepe van a job-shop ütemezés kialakításában a makroszintű cél érdekében.

1976-ban Garey bizonyítékot szolgáltatott arra, hogy ez a probléma NP-teljes m> 2 esetén, vagyis három vagy több gép esetében nem lehet optimális megoldást ellenőrizni polinomidőben (kivéve, ha P = NP ).

2011 -ben Xin Chen és mtsai. optimális algoritmusokat biztosított az online ütemezéshez két kapcsolódó gépen, javítva a korábbi eredményeket.

Az offline tesztek minimalizálása

Atomi munkák

Az offline makepan minimalizálási probléma legegyszerűbb formája az atomfeladatokkal foglalkozik, vagyis olyan feladatokkal, amelyek nincsenek több műveletre felosztva. Ez egyenértékű azzal, ha számos különböző méretű elemet rögzített számú tárolóba csomagol, hogy a szükséges maximális tárolóméret a lehető legkisebb legyen. (Ha ehelyett a tárolók számát minimálisra kell csökkenteni, és a tartály méretét rögzíteni kell, akkor a probléma más problémává válik, az úgynevezett tartálycsomagolási probléma .)

Dorit S. Hochbaum és David Shmoys 1987-ben bemutattak egy polinom-idő közelítési sémát , amely tetszőleges pontossággal talál hozzávetőleges megoldást az offline feladatok minimalizálására az atomfeladatokkal.

Több műveletből álló munkák

A feladatok többféle (M) művelettel, M gépeken történő ütemezésének problémájának alapvető formája úgy, hogy az összes első műveletet az első gépen kell elvégezni, a második műveleteket a másodikon stb., És egyetlen feladatot nem lehet párhuzamosan végrehajtani, az úgynevezett flow-shop ütemezési probléma. Különféle algoritmusok léteznek, beleértve a genetikai algoritmusokat is .

Johnson algoritmusa

Az SM Johnson heurisztikus algoritmusával megoldható a 2 gép N feladat problémája, amikor minden munkát azonos sorrendben kell feldolgozni. Az algoritmus lépései a következők:

A P _i feladatnak két művelete van, a P _i1 , P _i2 időtartamú , amelyeket az M1, M2 gépen kell elvégezni ebben a sorrendben.

1. lépés: A lista = {1, 2,…, N}, L1 lista = {}, L2 lista = {}.
2. lépés. Az összes rendelkezésre álló működési időtartam közül válassza ki a minimumot.

Ha a minimum P _k1 ,

Törölje K -t az A listából; Adja hozzá a K -t az L1 lista végéhez.

Ha a minimum P _{k2 -hez} tartozik ,

Törölje K -t az A listából; Adja hozzá K -t az L2 lista elejéhez.

3. lépés Ismételje a 2. lépést, amíg az A lista ki nem ürül.
4. lépés: Csatlakozzon az L1, L2 listához. Ez az optimális sorrend.

Johnson módszere csak két gép esetén működik optimálisan. Mivel azonban optimális és könnyen kiszámítható, egyes kutatók megpróbálták alkalmazni M gépekre, ( M > 2.)

Az ötlet a következő: Képzeld el, hogy minden egyes feladathoz m műveletekre van szükség egymás után, M1, M2… Mm. Az első m /2 gépeket egyesítjük egy (képzeletbeli) megmunkálóközpontba, MC1, a többi gépet pedig egy MC2 megmunkálóközpontba. Ekkor a teljes munkafeldolgozási idő egy P munkára az MC1 -en = összeg (működési idők az első m /2 gépen), és a feldolgozási idő a P feladatra az MC2 -n = összeg (működési idők az utolsó m /2 gépen).

Ezzel csökkentettük az m-Machine problémát két megmunkáló központ ütemezési problémává. Ezt Johnson módszerével oldhatjuk meg.

Teszti előrejelzés

A gépi tanulást a közelmúltban használták a JSP -példány optimális gyártási idejének előrejelzésére anélkül, hogy ténylegesen elkészítenék az optimális ütemtervet. Az előzetes eredmények körülbelül 80% -os pontosságot mutatnak, amikor felügyelt gépi tanulási módszereket alkalmaztak a véletlenszerűen generált kis JSP -példányok osztályozására az átlagoshoz képest optimális ütemezési hatékonyságuk alapján.

Példa

Íme egy példa egy job-shop ütemezési problémára, amelyet az AMPL- ben vegyes egész programozási problémaként fogalmaztak meg indikátorkorlátozásokkal:

param N_JOBS;
param N_MACHINES;

set JOBS ordered = 1..N_JOBS;
set MACHINES ordered = 1..N_MACHINES;

param ProcessingTime{JOBS, MACHINES} > 0;

param CumulativeTime{i in JOBS, j in MACHINES} =
   sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];

param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} =
   max {j in MACHINES}
     (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);

var end >= 0;
var start{JOBS} >= 0;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)} binary;

minimize makespan: end;

subj to makespan_def{i in JOBS}:
   end >= start[i] + sum{j in MACHINES} ProcessingTime[i,j];

subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   precedes[i1,i2] ==> start[i2] >= start[i1] + TimeOffset[i1,i2];

subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   !precedes[i1,i2] ==> start[i1] >= start[i2] + TimeOffset[i2,i1];

data;

param N_JOBS := 4;
param N_MACHINES := 4;

param ProcessingTime:
  1 2 3 4 :=
1 4 2 1
2 3 6 2
3 7 2 3
4 1 5 8;

Kapcsolódó problémák

A folyamatáramlás ütemezése hasonló probléma, de anélkül, hogy minden műveletet egy adott gépen kell elvégezni (csak a rendelési korlátozás marad meg).
A nyitott üzletütemezés hasonló probléma, de a megrendelés korlátozása nélkül is.

Lásd még

Hivatkozások

Külső linkek

Bécsi Egyetem A dinamikus optimalizálás módszertanának, rendszereinek és szoftvereinek katalógusa.
Taillard -példányok
Brucker P. Ütemezési algoritmusok . Heidelberg, Springer. Ötödik kiadás. ISBN 978-3-540-24804-0
Állásbolt vizuális ütemezése

Languages

In other projects