A probléma az ütemezési középiskolában

előző ◈ a következő

A cikk foglalkozik a felmerülő problémák előállítására órarende, és megoldást nyújt menetrendi leírt kritériumok. Ez is egy példa egy algoritmus által tervezett automatikus ütemezés osztályok.

Ütemezése - az egyik leggyakoribb probléma a tervezés és az optimalizálás az oktatási folyamat az iskolákban. Akármilyen jól kidolgozott ütemterv hatékonyságától függ a pedagógusok munkáját, a tanítás és a mastering anyag diákok, racionális felhasználása anyagi erőforrások.
Automatizálása ütemezés - a klasszikus probléma az intézmény irányítási rendszerek, de abban a pillanatban nincs egyetlen, általánosan elfogadott módon kell megoldani.
Minden megközelítések ütemezési alapuló heurisztikus módszerek, hogy jön az ember a tapasztalat. Hivatalossá ezek a módszerek problémás, ha azok a döntési szereplő, menetrend, amely vezérli a tapasztalat és az intuíció. Gyakran saját alkalmazottja, menetrend, nem tud válaszolni a kérdésre, hogy miért választotta az adott szállás lehetőség osztály, inkább, mint bármely más között elfogadható. De annak ellenére, hogy bonyolult a hivatalossá algoritmusok kiemelhetünk funkciók, mint heurisztikus megközelítések követelmények alapján a menetrend. Természetesen az egyes intézmények, ezek a követelmények eltérőek, mert történelmileg meghatározott jellemzői a szervezet az oktatási folyamat. Azonban még az összes adatot, lehetséges, hogy közös követelmények a menetrend:

  1. A minimális óraszámban a tanulók naponta;
  2. A maximális óraszámot, az óraszám heti minden hallgató;
  3. A maximális osztályok száma a tanulók naponta;
  4. Minimalizálása ablakok diákok;
  5. Elszámolása idő közötti távolságok a ház, ha változik a test tutori;
  6. Véve a kívánságait tanárok;
  7. egy sor osztályok fegyelem nem végződhet előadások, ha van egy szeminárium (gyakorlati) osztályokba;
  8. fegyelem képzési ciklusban nem kezdődhet szemináriumi (gyakorlat) ülésén, ha van előadás;
  9. Minden patak előadások minden csoportban kell megközelíteni kapott azonos számú órát szemináriumok (gyakorlati) képzés;
  10. Nem költenek többet, mint két előadás az azonos fegyelem a nap, és nem több, mint egy / két szeminárium ugyanazon a napon a fegyelem;
  11. A minimális óraszámban a tanár naponta;
  12. A maximális óraszámban a tanár naponta;
  13. Minimalizálása ablakok a kar (a továbbiakban: PPS);
  14. Minimalizálása a túlóra tanárok szerint a személyzettel;
  15. Számának minimalizálása, egyidejűleg azonos tantárgyak az iskolában egy és ugyanabban az időben. Ez közvetlenül érinti a juttatott összeg PPP hogy egy óraszám;
  16. Maximálisan kihasználja a tantermi alap. Ezek közé tartozik a követelményeket a legsűrűbb elhelyezésének diákok szerint a legújabb közönség kapacitás, és minimálisra csökkenti az állásidőt helyiségeiben;
  17. Elszámolása ideje közötti távolság a ház, ha változik tanár házban.

Feladat ütemezés függ a kezdeti feltételek. Akkor csoportos feladatok ütemezése ilyen körülmények között az egyes csoportokban:

  1. Ütemezés eleve ismert információ az elosztó csoportjai között PPP;
  2. Ütemezése kivéve PPP terhelést alkalmazva székek;
  3. Ütemezés anélkül, hogy figyelembe véve a terhelés székek.

Úgy véljük, részletesebben a jellemzőit minden a fenti csoportok feladatokat.
A probléma az ismert információt az elosztó csoportok közötti PPP probléma Registry oktató kívánságait, utazás vezérlő megváltoztatja a ház lécek tanár menetrend (több osztály ugyanabban az időben). Munkavállaló, ütemezés, szükség van a készítményben az ólom csak két támogató menetrendek: Menetrend-csoport és a PPP-menetrend. Különösen nehéz a feladat válik, ha a tanár megosztani a terhelést egymással akár a csoport, és az üzemeltető nem tudja megváltoztatni a menetrend eloszlást. Ezért az egyik megközelítés, hogy csökkentse a merev keret a megszorítások, ami az üzemeltető, hogy használja a forgalmazás tanárok nélkül csoportok: a tanárok jelzik csak a kar, a tanfolyam és a csoportok száma, akkor következik a félév során. Különös csoport hozzárendel egy üzemeltető ütemezni. Ez lehetővé teszi, hogy egy másik extra szabadsági fok, ami csökkenteni fogja a holtpontok.
A problémák, amelyek csak egy rakás szék, az üzemeltető már nem kell figyelembe venni a kívánságait a PPP vagy a kereszteződésekben a foglalkoztatási, az üzemeltető nem köteles megtartani csak két rend: csoport és tanár. Ugyanakkor közvetve az üzemeltető kell még venni, hogy a minisztérium kell minimalizálni a szükséges kar oktatói terhelés, mert nagyon fontossá válik, hogy hajtsák végre a követelményeknek száma 15. A figyelembe ezt a követelményt megjelenéséhez vezet olyan nagyságrendű, mint a szék a hatalom, ami azt mutatja, hogy hány munkamenet vezethet Tanszék ugyanazon fegyelem ugyanabban az időben. Miután megírta osztályoknak meg kell rendezni a menetrendjei tanárok maguk is.
Az ütemezési probléma figyelmen kívül hagyva az osztályoknak szabadsági fok sokkal több, mint a többiek, ezért nagyon logikus megközelítés mozogni egy csoport vagy menet. Azonban ebben az esetben, ha menetrendi nem lehet figyelembe venni kidolgozása során a kapcsolódó követelmények tanár (№ 6, 11-17).
Minden követelmény a menetrend a fenti (1-17), ró az adott ütemezés. Például az egyidejű jelenléte a feladat követelményeit a 3., 4., 10., 11., 12. és 15. optimális elhelyezését ülés 1. csoport a tanár és az áramlás, hogy megpróbálja elhelyezni a terhelés, amely beolvassa egy tanár az összes áramlási csoportban. Az optimális elhelyezése osztályok 2. csoport hiánya miatt az információt a tanár az áramlás, hogy megpróbálja, hogy tegye az első előadás, sőt, a következő pár, képzéseknek, előadások, melyeket az előző pár, amely lehetővé teszi, hogy összekapcsolják a teher ugyanazon fegyelem. Ez lehetővé teszi, hogy közvetlenül figyelembe véve a követelményeket 11, 12, 15, társított tanár.
A követelmény száma 16, hogy optimálisan elő, ha az összes osztály az iskolában tartják a fix rács egy (összesen) tárcsázza tervet. Ha az iskolai osztályok, amelyek nem tartoznak a rács terv hívások, illetve a hívások egy rács tervet, amely eltér az általános, majd a kereszteződés ezen órák gyakorlatok átfogó terv felszólít vezet egy egyszerű iskolai alap 20-40 perc alatt és az egész félévben összesen Egyszeri helyiségek állásidő halmozódott fel.
Egy másik probléma lehet azonosítani azáltal alaptantárgyaihoz óra (ha az áramlás csoportban nincs személyzet a profilban), választható kurzusok, idegen nyelv, testnevelés és a választható kurzusok. A probléma lényege az, hogy nem mindig ismert, bármilyen tudományos csoportok felvett egyik vagy másik csoport, hogy látogassa meg a fent említett diszciplínák, ami oda vezethet, hogy a mellékletet a diákok, ha egy és ugyanazon időben elhelyezni osztályok témákban feltétlenül az első tanulmány, valamint a fent említett tudományágak . Az, hogy ki ez a helyzet sem a kiválasztás egyes nap ezek a tudományágak, vagy az elhelyezése ezen osztályok az első vagy az utolsó pár.
A másik probléma az ütemezési feladat egy patak. Az áramlatok lehet létrehozni nemcsak az előadás (talán a legegyszerűbb eset), hanem az egyéb tevékenységek, például szemináriumok. Segítségével patakok szemináriumokkal bonyolítja a problémát, mert a hely mindig zavaró hullámok, mint osztályok egy csoportja. Az is lehet jelen hasító csoportok alcsoportokba laboratóriumi osztályok, osztályok tartott a spec. helyiségek, stb Amikor ütemezési ilyen esetekben használjon elhelyezés osztályok egy alcsoport héten egy paritás és a többi alcsoport másik paritás, az osztályok kerülnek külön dedikált nap vagy az elején / végén tevékenységek a nap folyamán, így a hallgatók nem különböznek alcsoportok képződött ablakban. Ezen kívül, ajánlott, hogy ezeket a vizsgálatokat az első helyen.
Egy másik fontos jellemzője az ütemezési probléma az, hogy figyelembe veszi a követelményeket az üzemeltető input menetrendek: súly (jelentőség) követelmények (1-17) dinamikusan változtatható attól függően, a helyi viszonyoknak minden egyes lépésében ütemezés. Az algoritmus heurisztikus súlya is változik.
A fő probléma az automatikus ütemezés - értékeli a minőségi ütemezés. A következő becslésekkel lehet kiemelni:

  1. Óra házigazdája ülések;
  2. Óra nem teljesen telepített osztályokba;
  3. Óra nem teljesen telepített osztályokba;
  4. A számos kiemelkedő tudományágak és csoportok;
  5. az összeg nem teljesen feltöltött tudományágak és csoportok;
  6. az összeg nem teljesen feltöltött tudományágak és csoportok;
  7. A teljes időtartama az ablakok a diákok;
  8. A teljes hossza az ablakok tanárok;
  9. A maximális időtartama a tanuló ablak;
  10. maximális időtartamát a tanár az ablak;
  11. átlagos száma ülések tanár egy nap;
  12. A minimális óraszámban a tanár naponta;
  13. A maximális óraszámban a tanár naponta.

Ha az automatikus ütemezés tevékenységek használjuk 2. csoport céljai, akkor célszerű felmérni 11-13 helyébe a következő rendelkezés lép:

  • az átlagos órák fegyelem a nap az iskolában;
  • A minimális óraszámban a fegyelem a nap az iskolában;
  • a maximális számú tanulmány a témában a nap az iskolában.
Amikor algoritmusok tervezésénél automatikus ütemezés ezeket a becsléseket lehet tekinteni, mint a kritériumokat kell optimalizálni, és az a része lehet tekinteni, mint egy korlátozás. Továbbá, ha ütemezési a kritériumok használhatók különféle típusú szeres [2, 5] csökkentésére a problémát, hogy egy kritérium optimalizálási problémák, vagy kezelésére multiobjective optimalizálási probléma használ Pareto dominancia elvét [8, 9, 10], valamint az azt követő építési multi-kritériumok kompromisszumot [11 ]. Ennek a végrehajtására algoritmust használni kívánt optimalizálási módszerek. Van egy nagy a választék és számos megoldási módjait, optimalizálási problémák. A leggyakrabban alkalmazott algoritmusok ilyen problémák - a „mohó” algoritmus [1]. Jellemzőjük, kapcsolatban az ütemezési probléma döntés minden iteráció alapján a jelenlegi kritériumok értékeit, így a korai stop az algoritmus és az eredmény lokális minimumok (zsákutca foglalkoztatás elhelyezési lehetőségeket). Akkor össze a „mohó” helyi keresési algoritmusok globális keresési algoritmus [3, 4, 6, 7], de ez jelentősen növeli a lehetőségek számát figyelembe kell vennie az algoritmus a folyamat elhelyezés osztályok.

Operator viselkedés ütemezése során több, mint a viselkedés a „mohó” algoritmus: az üzemeltető egymás helyezi az osztály, nem próbál építeni, vagy hogy fontolja meg egynél több lehetőség elhelyezést osztályok, ő ugyanis nagyon ritkán töröl házigazdája osztályok és válasszon másik szállást lehetőséget. De az üzemeltető, tapasztalataik alapján és az intuíció minden döntést a választás változatai forgalomba foglalkoztatás túlbecsüli a fontosságát az egyes kritériumok / korlátozások, ami nagyon hatékonyan és eredményesen hozzá a kívánt eredményt.
Ez azért van, mert az a tény, hogy hivatalossá összes követelmény a menetrend nagyon nehéz és kemény, hogy vegye figyelembe az egyedi üzleti folyamatait az egyes intézmények, a használata „mohó” algoritmusok használata nélkül heurisztikus megközelítések eredményre vezet, amely nem felel minden egyes oktatási intézménynek. Ez nem munka, hogy dolgozzon ki egy olyan algoritmust, amely figyelembe veszi az összes funkcióját minden oktatási intézményekben.
Ezért a legtöbb helyes megközelítés az ilyen helyzetekben, hogy tervezési algoritmus automatikus ütemezés igényei, valamint figyelembe véve a sajátosságokat az egyes oktatási intézmények heurisztikus megközelítések legközelebb akció az üzemeltető. Ez arra enged következtetni, hogy az algoritmus az automatikus ütemezés egyes intézményekben még mindig az övé.
Ahhoz, hogy vegye figyelembe a változékonyság az üzemeltető döntéshozatal ütemezés a helyzettől függően, akkor tönkreteheti a kidolgozási folyamatának a menetrend a következő lépéseket, amelyek mindegyike a döntési elv nem változik. Ez a szakaszban - egy csoportja olyan állapotok, amelyekben az operátor döntést hoz ugyanazt az algoritmust.
Tekintsük a példát az egyik heurisztikus algoritmusok célja, hogy egy adott oktatási intézmény többlépcsős áramkört.
Ebben az iskolában a feladat ütemezésére a kezdeti feltételek olyan csoport, 2: a tanárok nem tudják, azonban köteles figyelembe venni közvetetten őket a követelmény száma 15.
A kompozíció a következő megkötésekkel: ablakok hallgató legyen legalább 1 aktivitás napi tanulás, amennyire csak lehetséges - 4, legfeljebb két előadás egy nap a témában a hallgató, nem több, mint egy nelektsionnogo órák fegyelem a napon a hallgató számára. Kritériumokat a minőségi menetrend: 1-6.

Az algoritmus elkészítésének ütemezését az első többlépcsős, ahol minden lépést optimalizált „mohó” algoritmus alapján fa elhelyezését megoldások különböző összetételű korlátozásokat. A kompozíció a következő szakaszokból áll:
1. Kézi elhelyezése Testnevelésórán képzés számítógépes osztályok, ino-furcsa nyelvet.
2. Helyezzünk egy folytonos ciklus előadások idejére a menetrend öt napig. Sőt, ha forgalomba a nap a héten lesz egy előadás. Ez figyelembe veszi a követelményeknek 2, 3, 4, 5, 10, 15, 16. Az a követelmény, az 1. számú, hogy vegye figyelembe a jelenlegi szakaszban nincs értelme, mert a képzési eszközök még nem teljes a nap.
3. Gyakorlat osztályok nelektsionnyh folyamatos ciklus idejére a versenyek, írások csak nelektsionnye nappal öt napig. Sőt, ha forgalomba a nap a héten lesz egy előadás. Ez figyelembe veszi igénypontok 2, 3, 4, 5, 8, 10, 15, 16.
4. Döntse el minden csoport elosztásának további hat napon át. Nap kiemelkedik, ha valaha is volt egy előadás, amely képes befogadni egy folytonos ciklus idejére a menetrend. Ha egy ilyen nap van rendelve, akkor ezek a csoportok töltötte be a hatodik nap a héten előadások. Ez figyelembe veszi igénypontok 2, 3, 4, 5, 10, 15, 16.
5. helyezés előadások maradványok az előadás napokban. Ebben az esetben, akkor az új előadás nappal, de nem több mint öt nappal minden osztály a csoport. Ez figyelembe veszi igénypontok 2, 3, 4, 5, 10, 15, 16.
6. Gyakorlat előadások levő maradványok nelektsionnye nap. Ebben az esetben, akkor az új nelektsionnye nappal, de nem több mint öt nappal minden osztály a csoport. Ez figyelembe veszi igénypontok 2, 3, 4, 5, 10, 15, 16.
7. helyezése nelektsy maradékok nelektsionnye nap. Ebben az esetben, akkor az új nelektsionnye nappal, de nem több mint öt nappal minden osztály a csoport. Ez figyelembe veszi a követelményeket 1, 2, 3, 4, 5, 8, 10, 15, 16.
8. helyezése nelektsy maradványok az előadás napokban. Ez figyelembe veszi a követelményeket 1, 2, 3, 4, 5, 8, 10, 15, 16.
9. Bármely fennmaradt szabad ülés marad a kézi feldolgozás. Ugyanakkor saját belátása szerint a döntéshozó, akkor távolítsa el az összes osztályok, amelyek nem felelnek meg a követelménynek 1 eredményeként az előző szakaszban.

Így. Az optimális használat érdekében az automatikus ütemezés úgy kell kialakítani, heurisztikus algoritmusokat, amelyek figyelembe veszik a sajátos az egyes intézmények külön-külön, és használata lépéseket-heurisztikus ad egy csomó rugalmasságot döntéshozatalban. Az egyetlen módja annak, hogy jó eredményt érjen el.

Kapcsolódó cikkek

előző ◈ a következő