Schema

Kärnan i klassschemaläggning är schemaläggningsteori . Schemaläggningsteorin har studerats väl och beskrivits i många verk sedan 1960-talet. Det används i stor utsträckning både för att organisera företagens arbete och är tillämpligt på utbildningsinstitutioner [3] [4] [5] .

Klassernas schema ur formaliseringssynpunkt i teorin om scheman är definitionen på tidsskalan för platsen för att genomföra klasser i givna utbildningsdiscipliner med uppfyllandet av kraven för dem. Krav utformas av deltagare i utbildningsprocessen och vägledningsdokument.

De första komponenterna i denna process är:

• P - inlärningsströmmar, som inkluderar från en till flera träningsgrupper, eller undergrupper, som bildas genom att dela upp en eller flera grupper (ström) i separata enheter.
• T - lärare, som är huvudmekanismen för att påverka lärandeflöden. I motsats till de klassiska tillvägagångssätten i schemaläggningsteorin (en mekanism - en operation) kan det i denna situation finnas situationer när flera lärare kan kombineras till en "mekanism" för att genomföra en lektion.
• D - träningsdiscipliner, vars grund är en tematisk träningsplan, inklusive olika typer av klasser.
• A - publik som är en plats för att genomföra klasser (utföra en operation). I många befintliga teorier och system som implementerar schemaläggning tas denna deltagare ur den allmänna uppgiften för att förenkla systemet.

Att sätta en uppgift för planering

I många arbeten är den formulerad som en uppräkning av alla möjliga alternativ för alla initiala data i planeringsprocessen (den kartesiska uppsättningen R = {P*T*D*A*z}, där z är lektionens perioder ( datum och par) med att hitta det optimala enligt matchningskriteriet Med detta tillvägagångssätt dras en slutsats om komplexiteten i schemaläggning, eftersom när man löser det uppstår en exponentiell ökning av antalet kombinationer, vilket gör problemet NP-komplett . [3]

Detta tillvägagångssätt är dock inte alltid korrekt, eftersom denna kombination redan i den preliminära förberedelsen för planering reduceras genom att kombinera läraren, flödet, publiken (eller eventuell publik) och den pågående lektionen enligt den tematiska planen till en planeringsenhet - ofta kallad lektionen.

Om vi ​​betraktar planering i detta fall som processen för att bestämma tidsperioden för en viss lektion, så blir uppgiften klassisk ur schemaläggningsteorinsynpunkt. Det vill säga, för ett givet antal arbeten (discipliner) och operationer (ockupation av en disciplin), bestäm sådana tidsperioder så att det sammanställda schemat uppfyller de specificerade optimalitetskriterierna och kraven.

För att skapa ett schema måste följande fastställas:

1. Discipliner och klasser om dem (arbeten och operationer) - grunden är den tematiska planen för att studera disciplinen.  
2. Lärare och klassrum (bilar och placering av bilar) för att genomföra klasser. I de flesta fall är lärare (hård länk) och möjliga målgrupper (flytande länk) definierade för alla klasser i temaplanen.  
3. Ordningen för godkända klasser (operationer på maskiner). För närvarande utelämnas detta objekt vid schemaläggning av klasser utifrån ett acceptabelt antagande att det inte är kritiskt när man behärskar disciplinens material. Det vill säga, ur schemaläggningssynpunkt kommer klassernas ordning att vara slumpmässig.  
4. Schemautvärderingskriteriet är en viss parameter som beräknas från det erhållna schemat, som visar dess optimalitet ur de givna synpunkterna. För utbildningsprocessen är kriteriet för att utvärdera schemat en multiparameterfunktion som inkluderar både diskreta obligatoriska krav och rekommenderade optimeringskrav. I många arbeten är denna funktion avgörande för optimal schemaläggning. Eftersom det ofta används funktionen för summan av böter, vilket gör att du helt enkelt kan utvärdera optimaliteten hos det sammanställda schemat. 

För automatiserad schemaläggning räcker det att ställa in de två första punkterna. Den fjärde punkten (utvärderingskriteriet) implementeras utifrån operatörernas erfarenhet av schemaläggning. En viktig punkt för automatisering är skapandet av ett sådant tillvägagångssätt som skulle göra det möjligt för operatören att göra ett schema för de valda klasserna på minimal tid med kontroll på programnivå eller av operatören visuellt över uppfyllandet av specificerade krav. Faktum är att i det här fallet handlar lösningen av problemet om att hitta det bästa gränssnittet för programmet och är en ren ingenjörsuppgift. För att underlätta operatörens arbete i det första steget av automatisering kan du använda den dynamiska programmeringsalgoritmen . Det vill säga ordningen för schemaläggning av discipliner bestäms på ett sådant sätt att planeringsprocessen delas upp i deluppgifter, vars schemaläggning kommer att vara relativt enkel. Samtidigt kommer huvuduppgiften i det här fallet att vara att bestämma kriteriet för rankning av discipliner.

För detta tillvägagångssätt kan följande kriterium användas [6] :

Kopt(i,j)=Wrd(i)/Wmo(j) , där

i är numret på läraren (maskinen) i intervallet från 1 till M;

i är numret på disciplinen (arbetet) i intervallet från 1 till N;

Wrd är antalet klasser (operationer) som ska utföras i den valda disciplinen (arbete);

Wmo är antalet klasser (operationer) som en lärare (maskin) kan genomföra under den planerade tidsperioden, med hänsyn tagen till de begränsningar som åläggs klassernas prestation inom denna disciplin och läraren.

Rangordningen av discipliner för schemaläggning utförs i ordning efter att det erhållna kriteriet minskas.

I schemaläggningsteorin hänvisas ofta till detta kriterium som en reserv av tid för att slutföra arbete - skillnaden mellan hur lång tid maskinen har och mängden tid att arbeta [5] . I det här fallet föreslås det att använda förhållandet mellan dessa variabler, vilket gör det möjligt att inte bara ordna disciplinerna i planeringsordning, utan också kontrollera möjligheten att planera arbete enligt formeln:

, där N är antalet discipliner för denna lärare.

Om den resulterande indikatorn är större än 1, betyder det att läraren inte har tillräckligt med tid att genomföra klasser. I det här fallet är det nödvändigt att minska restriktionerna för att genomföra dessa klasser, eller byta ut läraren.

Det sammanställda schemat för klasser enligt denna algoritm kommer endast att vara delvis optimalt. Men i de flesta fall av moderna tillvägagångssätt för att schemalägga klasser är det resulterande schemat en slags kompromiss för att genomföra klasser, erhållen på grundval av operatörernas erfarenhet och kraven för att genomföra klasser.

Vid implementering av detta tillvägagångssätt måste en iterativ metod användas . Det vill säga, när man schemalägger efter varje disciplin, rangordnas arbetet om.

Om en situation uppstår när planering är omöjlig för den valda nästa disciplinen, görs omschemaläggning. Som en omplanerad disciplin väljs den med det minsta värdet av indikatorn Kopt(i,j) .

För att lösa problemet med begränsningar som åläggs av komponenterna i planeringsprocessen är det möjligt att använda en återkommande algoritm för att anpassa planeringsprocessen. Det består i att, på grundval av befintliga tidigare scheman, erhålla indikatorer som gör det möjligt att konkretisera a priori information om planeringsprocessen baserat på befintliga erfarenheter. Det vill säga, i det här fallet, organisera feedback för planeringsprocessen på tidigare planeringsperioder, vilket kommer att fungera som en i efterhand standard för schemaläggning av klasser.

Se även

• Schema
• Programguide
• mediaplan
• Algoritm
• utsändning

Anteckningar

1. ↑ Stridsschema  // Militär uppslagsverk  : [i 18 volymer] / ed. V. F. Novitsky  ... [ och andra ]. - St Petersburg.  ; [ M. ] : Typ. t-va I. D. Sytin , 1911-1915.
2. ↑ Stridsscheman  // Militär uppslagsverk  : [i 18 volymer] / ed. V. F. Novitsky  ... [ och andra ]. - St Petersburg.  ; [ M. ] : Typ. t-va I. D. Sytin , 1911-1915.
3. ↑ 1 2 Schema teori och datorer. Ed. T.EX. Koffman .. - M . : Nauka, 1984.
4. ↑ Conway R. V., Maxwell V. L., Miller L. V. Schema teori. - M . : Huvudutgåva av den fysiska och matematiska litteraturen från förlaget "Nauka", 1975.
5. ↑ 1 2 Tanaev V.S., Shkurba V.V. Introduktion till schemaläggningsteori. - M . : Huvudutgåva av den fysiska och matematiska litteraturen från förlaget "Nauka", 1975.
6. ↑ Kuzmichev A.B. Om strategin för automatisering av schemaläggning i en utbildningsinstitution // Tekhnika mashinostroeniya : zhurnal. - 2014. - Nr 3 . - S. 23-26 . — ISSN 2074-6938 .