Lektionsschemat reglerar rytmen i skollivet, arbetet och resten av elever och lärare.
Effektiviteten av hela utbildningsprocessen beror till stor del på dess kvalitet.

Behörighet till lektioner och skolschema

Skolans utbildningsregim måste motsvara elevernas funktionella förmågor. Omfattning, innehåll och organisation utbildningsprocess måste säkerställa ett tillstånd i kroppen där tröttheten helt skulle försvinna under viloperioden.

Huvudkriterierna för att bedöma lektioner i termer av elevers funktionsförmåga är svårighet och trötthet. Trötthet kännetecknas av en förändring i prestation, och ämnets svårighet kännetecknas av prestationsnivån, det vill säga graden av behärskning utbildningsmaterial. Därför måste båda faktorerna beaktas lika vid schemaläggning.

I den juridiska aspekten återspeglas problemet med att upprätta ett skolschema i nya hygienkrav för schemaläggning, som bygger på moderna data vetenskaplig forskning biorytmologi mental prestation och svårighetstabeller för objekt I.G. Sivkova. Men för skolans biträdande direktör, som upprättar schemat, är det viktigt att inte bara veta hur svårt ämnet är, utan också att föreställa sig styrkan i den tröttsamma effekten av lektioner i ett visst ämne på elevernas hälsa. . Tyvärr har svårighetstabellen I.G. Sivkova tar inte hänsyn till en sådan del av träningen som tröttheten i ämnen, vilket främst påverkar elevens hälsa.

Modern forskning ger insikt i sambandet mellan ämnets trötthet och svårighet, även om dessa indikatorer i vissa ämnen varierar avsevärt. Dessa representationer gör det möjligt att kombinera två indikatorer till en - objektets acceptans. Därför har tabell I.G. Sivkov, vi kan föreslå ett alternativ - en skala för ämnesacceptans, som skulle ta hänsyn till komponenterna i svårighet och tråkig inlärning, såväl som egenskaperna hos varje läroanstalt och läroplan för varje årskurs.

Acceptansskalan består av kolumnen "Artiklar efter rang", som innehåller poster vars rangordning erhölls baserat på resultaten av diagnostisering av metodens svårighetsgrad och tråkighet. expertbedömningar– deras algoritm presenteras i bilaga 1. Den föreslagna skalan är konstant till sin struktur, men varierande till innehåll (se tabell 1).

bord 1

Ungefärlig objektacceptansskala

Som framgår av tabell 1 består skalan av fem svårighetsgrupper. Varje grupp har en poäng - detta är en konstant komponent i skalan och är inte föremål för några förändringar. Innehållet (d.v.s. en uppsättning objekt) i varje grupp kan ändras beroende på diagnostiska resultat. Den representerar den rörliga delen av skalan.

I genomsnitt gymnasieskola nr 618 i St. Petersburg, fick vi följande skala för objektacceptans (se tabell 2).

Tabell 2

Acceptansskala för föremål

Schemaläggningsalgoritm

Eftersom varje läroanstalt kommer att ha sin egen acceptans av ämnen, bör läsarna inte kopiera den givna en-till-en-skalan. Det är tillrådligt att diagnostisera svårighetsgraden och tröttheten för ämnen i din skola med hjälp av expertbedömningsmetoden.

När man gör upp ett schema är det dessutom meningsfullt att vägledas av en tabell som rangordnar elevernas prestationsnivå i olika klasser i olika lektioner under skolveckan (se bilaga 2).

Vi har skapat en algoritm för att skapa ett fysiologiskt baserat schema som tar hänsyn till realistiska hygienkrav. Denna algoritm kan användas för att skapa ett utbildningsschema både i en skola med ett stort antal klasser i andra och tredje klass, och i en relativt liten läroanstalt. Algoritmen är avsedd för specialister som skapar ett schema utan att använda ett datorprogram.

När du använder automatiserade program är det tillrådligt att arrangera objekt med hjälp av ett automatiserat program i steg baserat på den föreslagna algoritmen. Som praxis visar kan dessa program endast användas som ett extra verktyg för:

• initialt arrangemang av objekt följt av manuell efterbehandling;
• spara information och skriva ut den.

Efter den automatiserade distributionen av objekt (programmet ordnar som regel från 40 till 70%), är det nästan omöjligt att ta hänsyn till de hygieniska kraven för lektionsschemat, eftersom det inte bara är nödvändigt att leverera de återstående oordnade objekten , men också att avsevärt ändra (upp till 60%) det automatiserade arrangemanget av objekt enligt principen "bara för att ordna det."

Därför, när du använder ett datorprogram för att skapa ett rationellt schema, med hänsyn till realistiskt genomförbara hygieniska och pedagogiska krav och specifikationerna för en utbildningsinstitution, är det nödvändigt att ordna ämnen i etapper med den algoritm som föreslagits ovan. I det här fallet måste varje steg av att arrangera en grupp av objekt avslutas med manuell efterbehandling, med fokus på ovanstående krav. Detta gör att du kan göra ett mer rationellt schema och, om möjligt, ta hänsyn till alla nödvändiga villkor.

Procedur för att ändra schemat

Algoritm för att justera skolschemat

Om du behöver ändra ditt schema under läsåret, vilket händer ganska ofta, måste du arbeta med tabellupplägget. För att ändra schemat på den måste du utföra följande beräkningar och omarrangemang.

Den föreslagna metoden för att skapa ett schema tar inte längre tid än vanligt, men låter dig skapa ett schema korrekt, dvs:

• gör din egen skala för ämnesacceptans (svårighet och trötthet) för att skapa ett mer rationellt skolschema;
• hålla en tillräckligt stor mängd nödvändig information i synfältet för skolans biträdande direktör;
• fördela lektionerna jämnt för varje dag (undvik ett för stort antal sjunde lektioner);
• starta alla klasser från den första lektionen, vilket möjliggör inlärning i samma rytm, eftersom eleverna börjar skoldagen vid samma tid varje dag;
• reglera svårighetsgraden på skoldagen beroende på dynamiken i skolbarnens veckoprestationer;
• arrangera lektioner med praktiskt taget inga "fönster" eller med ett minsta antal av dem, vilket gör att du kan upprätthålla rytmen i lärarens arbete och skapa en gynnsam arbetsmiljö;
• rationellt alternerande föremål i olika riktningar;
• rationellt arrangera de nödvändiga dubbellektioner;
• snabbt ändra och anpassa schemat på grund av produktionsbehov.

Dessutom kräver denna metod inte en betydande mängd pappersämnen (ytterligare tabeller, särskilt om skolan har många andra och tredje klasser (30 eller fler).

För att förbereda ett högkvalitativt schema som skulle motsvara förmågan hos en viss utbildningsinstitution, är det nödvändigt att utföra din egen diagnos av svårighetsgraden och tröttheten hos ämnena i varje parallell. Studenter bör vara experter i det här fallet, eftersom ingen bättre än de kan säga vilket ämne som är svårt och tråkigt.

Kriterier för hygienisk bedömning av skolschemat

1. Antal klasser grundskola – ______.

2. Antal klasser huvud- och gymnasium – ___________.

3. Totalt antal klassrum som används för lektioner – ___________.

4. Tillgänglighet för en godkännandeskala för din utbildningsinstitution:

5. Med hänsyn till skalan av ämnesacceptans i skolans läroplan:

6. Fördelning av lektioner per dag för studenter:

7. Alla klasser börjar sina studier med den första lektionen:

8. Rationell växling av ämnen av olika riktningar och komplexitet:

9. Överensstämmelse med elevernas prestationer i schemat (veckodynamik):

10. Rationellt arrangemang av lektioner för lärare:

11. Maxbelopp lektioner från lärare per dag:

a) upp till 4 lektioner – för____ lärare – ______ (%);

b) 5 och 6 lektioner - ____ lärare - _____ (%);

c) 7 lektioner eller mer - ___ lärare - ___ (%).

12. Metodisk dag tillgänglig (ange antalet lärare):

a) med en arbetsbelastning på upp till 24 timmar i veckan – för ____ lärare;

b) med en arbetsbelastning på 25 till 30 timmar per vecka – för ___ lärare;

c) med en arbetsbelastning på mer än 30 timmar i veckan – för___ lärare.

1. Förbered uppsättningar med namn på föremål från 5:e till 11:e klass.
2. Ge eleverna uppsättningar av ämnesnamnkort och svarsblad.
3. Erbjud dig att välja kort med namnen på de ämnen som studeras i denna klass (med hjälp av en dagbok).
4. Förtydliga begreppet "svårighet" för föremål.
5. Erbjud dig att självständigt bestämma varje ämnes svårighetsgrad genom rangordning, d.v.s. lägga ut korten i fallande ordning efter ämnets svårighetsgrad (lägg korten uppifrån och ned, d.v.s. i första hand överst är kortet med det svåraste ämnet, nedan är det mindre svåra, etc.).
6. Skriv ner det resulterande arrangemanget av poster på svarsbladet.
7. Efter detta, analysera och förtydliga begreppet "tröttande" av föremål.
8. Utför en liknande rangordningsprocedur och skriv ner den resulterande justeringen på svarsbladet.
9. Samla in och bearbeta svarsblad (se sammanfattningstabellformuläret nedan).

– där: mk – GPA i ett ämne i en klass;

n – antal klasser i den parallell som studeras;

eller med formeln:

– där: Mk – summan av poäng i ett ämne i en klass;

n – antalet studenter från samma parallell som deltar i studien.

Till exempel, i 7:e klassparallellen finns det fem klasser, 130 personer deltog i diagnosen. Summan av poäng i det ryska språket i parallellen var 469. Vi ersätter talen i formeln:

ons. b. pr. = (469/130) = 3,61 – medelpoängen i ryska språket i 7:e klass var 3,61, barn upplever detta ämne som ganska svårt.

På samma sätt beräknas medelpoängen för varje ämne i form av trötthet separat.

Den genomsnittliga acceptanspoängen för varje ämne hittas sedan. För att göra detta läggs två indikatorer samman: den genomsnittliga svårighetspoängen och den genomsnittliga tråkighetspoängen, och sedan delas resultatet med 2. Detta ger ämnets genomsnittliga acceptanspoäng.

Baserat på de erhållna uppgifterna sammanställs en individuell tabell över behörighet för ämnen vid en viss utbildningsinstitution för varje parallell.

Pivottabellformulär för bearbetning av svar

Bilaga 2

Rangordning av studietimmar under veckan
beroende på prestationsnivån hos eleverna i olika klasser

1 – mest fördelaktiga timmar; 10 – den mest ogynnsamma.

6–7 – minskad prestationsnivå (ogynnsamma timmar för att genomföra lektioner).

8–10 – låg prestationsnivå (ogynnsamma timmar för att genomföra lektioner).

Lärarens veckotabell för arbetsbelastningsfördelning

Bilaga 3

Teknik för att utföra layouten av lektionsschematabellen

För att slutföra layouten måste du förbereda:

• 4 ark kartong (tjocklek 1–2 mm, höjd – 42 cm, bredd – 22 cm; radhöjd – 0,8 cm, kolumnbredd – 1 cm)*;
• 4 ark färgat papper (helst ljusa färger) med en densitet på 200 g/cm och mått som liknar kartongark;
• bred transparent tejp;
• lederin (pappersvinyl) för limning av kartong i en folder (band 4–5 cm breda; 49–50 cm långa);
• PVA-lim (ganska starkt, som "silakra").

Layoutexekveringsalgoritm

1. Limma fast kartongark i en "mussla":

2. Lägg all nödvändig information för att skapa ett schema på ett ark färgat papper (lägg på ett kartongark nr 1); exempel: tabell på sid. 27.

3. Rita ett rutnät på de följande två arken med färgat papper, tre dagar på varje ark, 7 celler för varje dag (lägg på det andra och tredje kartongarket).

4. På det 4:e arket ritar du ett kontinuerligt rutnät utan att dela upp i dagar (celler har liknande storlekar).

5. Täck de färdigfodrade arken med tejp så att det inte finns några revor när du skär cellerna.

6. Gör slitsar i cellerna i storlek från 0,5–0,6 cm.

7. Limma fast pappersarken längs sidorna av kartongarken på det färdiga "clamshell". Layouten är klar.

8. Gör separata flerfärgade taggar med klassbokstaven (5:e "A", 7:e "G", etc.), mängden baserat på belastningen av en 5- eller 6-dagars vecka + dessutom för lektioner där klasserna är uppdelade i undergrupper. Tagsstorlek: bredd – 8 mm; höjd – 15 mm.

9. Förbered taggar av valfri färg utan betygsbokstavsinskriptioner för att beräkna den veckovisa arbetsbelastningen för varje lärare. Mått: bredd 5 mm; höjd 12–14 mm.

Denna layout är bekväm att använda, eftersom all nödvändig information alltid är framför ögonen på biträdande direktören. Den kan vikas ihop till en mapp, vilket gör den lätt att bära. I det här fallet kommer taggarna att hållas i luckorna.

Information som behövs för att skapa ett schema

___________ * Måtten på kartongarket är individuella, eftersom... Varje skola har olika antal lärare, olika arbetstider (5- och 6-dagars skolvecka). Vi föreslår schemastorlekar baserat på en 6-dagars skolvecka och en skola med 50-55 lärare.

Tystnaden rådde, som bröts av Schweik själv och suckade:
– ... Det måste finnas disciplin i militärtjänstgöringen – utan den skulle ingen lyfta ett finger för saken. Vår cheflöjtnant Makovets sa alltid: "Disciplin, idioter, är nödvändigt. Utan disciplin skulle du klättra i träd som apor. Militärtjänst Han kommer att göra människor av er, hjärnlösa dårar!” Tja, är det inte så? Föreställ dig ett torg, säg, på Karlstorget, och på varje träd sitter en soldat utan någon disciplin. Det här skrämmer mig fruktansvärt.
Jaroslav HASHEK DEN GODE SOLDATEN SCHWEIKS ÄVENTYR

Klassschemat är kombinationen i rum och tid av en disciplin (ämne), lärare (lärare), publik och grupp (undergrupp, ström) av elever.

Formulering av problemet

Jag ska fatta mig kort.

• Under en lektion kan eventuella deltagare vara frånvarande, till exempel på ett institutionsmöte, studenter kommer i regel inte eller studenter har gått till jobbet. militäravdelning(de har sitt eget schema), och för den här typen av klasser finns det ingen disciplin, lärare och publik.
• Kontinuitet (inga fönster) är i regel ett nödvändigt krav för elever och helst för lärare.
• Schemat kan sammanställas för en termin/halvtermin för vecka, med två veckor och täljare/nämnare (udda vecka/jämn vecka). Det finns också ett månadsschema.
• Klasser ska kunna ställas in i manuellt läge (med andra ord i editorn). Till exempel, ett akademiskt råd eller ett par av en stor chef, eller till och med ockupationen av bara en bra person.
• Det måste finnas ett system med förbud för alla deltagare i lektionen. Till exempel, nu tjänar nästan alla lärare pengar vid sidan om (annars kommer du inte att kunna överleva) eller så är klassrumsfonden uppdelad mellan fakulteter och klasser kan inte hållas i delar av klassrummen efter lunch.
• Närvaron av sofistikerade önskningar från lärare, en får 5 lektioner om dagen för att frigöra andra dagar, och den andra får inte mer än två lektioner om dagen, han blir övertrött, och om det är en föreläsning, då en klass och definitivt 2:a eller 3:e klassen.
• Klasser i olika byggnader kräver mer tid för övergång än rasterna mellan klasserna. Villkoret för att minimera rörelser är också naturligt.

Slutsats. Som framgår av utlåtandet är det möjligt att bedöma schemats kvalitet först efter att det är helt sammanställt. Därför kan användningen av genetiska algoritmer göra det möjligt att konstruera en lösning på det önskade problemet och till och med få, på sätt och vis, en av de bra. Samtidigt konvergerar genetiska algoritmer mycket snabbt till den optimala i början, vilket innebär att det praktiskt taget inte kommer att finnas några begränsningar för mängden indata.

Bilden är tagen härifrån.

Genetisk algoritm

Rent retoriskt kommer jag att upprepa huvudstadierna i den genetiska algoritmen:

1. Ställ in målfunktionen (fitness) för individer i befolkningen
2. Skapa en initial population
3. (Start av cykeln)
   1. Reproduktion (korsning)
   2. Mutation
   3. Beräkna värdet av målfunktionen för alla individer
   4. Bildande av en ny generation (urval)
   5. Om stoppvillkoren är uppfyllda, då slutet av slingan, annars (början av slingan).

Det vanligaste felet i användningen av genetiska algoritmer är i urvalet av gener. Ofta är de gener som väljs helt enkelt själva lösningen. Valet av gener är det mest icke-triviala och kreativa elementet när man skapar en genetisk algoritm. Personligen anser jag att valet av gener bör uppfylla följande två grundläggande krav.

1. Baserat på uppsättningen gener bör lösningen på det önskade problemet konstrueras snabbt och entydigt.
2. Vid korsning måste avkomman ärva karaktärsdrag föräldrar.

En kommentar. Uppsättningen gener bör tillhandahålla hela uppsättningen av (möjligen optimala) lösningar på problemet. I princip är det inte nödvändigt att kräva en-till-en, det räcker att kartläggningen av gener på lösningsutrymmet är på(översikt).

Schemaläggningsalgoritm

Jag kommer bara att beskriva själva generna, algoritmen för att konstruera en lösning baserad på dem, korsning och mutation.

Hur en erfaren dispatcher gör ett schema. Ordet erfaren betyder att avsändaren redan har gjort upp schemat en gång och känner till dess flaskhalsar. Till exempel bristen på stora strömmande publik eller datorklasser. Den första kursen, eftersom de har många strömmande föreläsningar och samtidigt lektioner i undergrupper i datorklasser, engelska/engelska från grunden/tyska/franska etc., och myndigheterna kräver att den första kursen inte i något fall har några fönster och ingen mer än två föreläsningar per dag och dagarna var jämnt belastade. Därför ordnar en erfaren dispatcher första "smala klasser", lektioner av myndigheterna på deras begäran och klasser med särskilt irriterande lärare. Sedan, med hjälp av de arrangerade klasserna som ett skelett, slutför han snabbt schemat. Låt oss försöka imitera, på sätt och vis, denna process.

Några av klasserna finns redan på vårt schema, resten kommer att numreras i tur och ordning. Vi kommer att betrakta uppsättningen av ockupationsnummer som ett genom, även om i princip bara ordningsföljden på yrken är viktig här. För att bygga ett schema kommer vi att extrahera klassnummer i följd och sätta den valda klassen på schemat, vilket uppfyller de nödvändiga kraven och maximerar den objektiva funktionen för elever, lärare och publik (de har också anställningskriterier).
Om de nödvändiga kraven inte kan uppfyllas kan en individ med ett sådant genom kasseras som icke-livsduglig. Om det inte är möjligt att skapa ett schema kan du ersätta de nödvändiga kraven med en straffavgift i den objektiva funktionen.

Korsning kan organiseras på flera sätt. Till exempel en av dem. Låt oss ha följande gener

3 1 2 5 6 4 7
2 3 5 7 1 4 6

Här kan du se att aktivitet 3 förekommer i båda generna upp till position 2 inklusive, och till exempel från position 2 till position 5 finns ett intervall för 1 aktivitet. Låt oss göra följande tecken

_ * * * * _ _ för 1 lektion
* * * _ _ _ _ för lektion 2
* * _ _ _ _ _ för lektion 3
_ _ _ _ _ * _ för lektion 4
_ _ * * _ _ _ för lektion 5
_ _ _ _ * * * för lektion 6
_ _ _ * * * * för lektion 7

här anger asteriskerna möjliga positioner för ättlingens yrkesnummer. Du kan välja mellan en eller flera möjliga lösningar som barn eller barn till dessa föräldrar. Det finns alltid en lösning för att välja gener för en ättling, till exempel är båda föräldrarna själva nöjda. Låt oss skriva om tabellen genom uppsättningar av möjliga positioner

1 position (2, 3)
2:a position (1, 2, 3)
3:e position (1, 2, 5)
4:e position (1, 5, 7)
5 positioner (1, 6, 7)
6:e position (4, 6, 7)
7 position (6, 7)

För att konstruera lösningar kan du använda följande algoritm. Först kommer vi att sätta antalet klasser som är mindre vanliga. Om vi ​​sorterar dem i stigande ordning kommer vi att ha det
1 gång 4
2 gånger 3,5
3 gånger 2, 6
4 gånger 1, 7
Därför lägger vi först lektion 4 på 6:e positionen, sedan 3 eller 5 i positionerna (1, 2) respektive (3, 4). Vid varje steg kan du kasta en låda med tändstickor. Som ett resultat kan du till exempel få följande steg för korsningsalgoritmen

* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6

Eftersom det är möjligt att den korrekta sekvensen kanske inte är konstruerad är det bättre att organisera algoritmen i form av en enkel rekursion för att kunna upprepa algoritmen, d.v.s. organisera lite sökning.

Mutationen kan organiseras helt enkelt genom att slumpmässigt omorganisera yrkesnumren.

Slutsats

Det här är en fortsättning på sätt och vis på mina inlägg Program för att schemalägga lektioner vid ett universitet och Beräkna arbetsbelastningen för institutionen.

Jag föreslår återigen följande lösning (skiss).

• GUI på PyQt eller PySide
• PosgreSQL DBMS (jag har ca 80% redo här), förutom själva schemat innehåller det även applikationer och lärarbelastningar, läroplaner och mycket mer (för detta ändamål kommer jag att publicera ett eller flera ämnen)
• webbgränssnitt på CherryPy+Cheetah (men detta kan diskuteras)
• export av alla rapporter (scheman, utbildningsuppdragskort, etc.) i OpenDocument-format (GOST R ISO/IEC 26300-2010. Gosstandart of Russia (06/01/2011)) via ODFPY
• schemaläggningsalgoritmer från mig (det här ämnet handlar om det)
• produktion från mig
• för den intresserade, arbeta med den gemensamma kärnan
• för de intresserade, anpassning till sitt eget universitet och förmågan att förändra allt flexibelt, livet går vidare och tjänstemännen sover inte

Tack till alla som svarat, efter att ha diskuterat detta ämne kommer det att vara möjligt att organisera sig.

Nyligen kom ämnet klassschema upp här, och jag ville prata om min erfarenhet av att bygga en schemaläggningsalgoritm för ett universitet, eller snarare mer om den heuristik som jag använde.

För inte så länge sedan 2002, när jag tog examen från ett universitet (Yaroslavl-grenen av MESI), med huvudämne i "Applied Informatics in Economics", stod jag inför uppgiften att välja avhandling. Den föreslagna listan med ämnen var deprimerande, mestadels tråkig databasutveckling. I princip skulle jag kunna ta en del av mina befintliga utvecklingar som grund, som chefen föreslog. avdelning, men mitt blod kokade, jag ville göra något intressant och nytt för mig själv. Jag föreslog chefen ämnet schemaläggning, särskilt eftersom jag arbetade i IT-tjänsten vid ett universitet och jag var ansvarig för KIS UZ-systemet (Integrated Information System for Educational Institution Management), en produkt från ett Yaroslavl-företag. KIS UZ var bra, men hon kunde inte skapa ett schema själv. Dessutom strävade jag efter målet att göra något användbart, men det visade sig att det inte fanns några försök att implementera det, kanske åtminstone att publicera det på Habré kommer att gynna någon.

Så det var nödvändigt att lära datorn att skapa ett veckoschema med klasser, och så bra som möjligt. Jag insåg storleken på sökutrymmet och satte inte upp målet att hitta det bästa alternativet. Först måste du bestämma vilka klasser som är och vad som är bra och vad som är dåligt. Följande modell valdes, som har följande indata:
- antal dagar i veckan
- antal lektioner per dag
- lista över lärare
- lista över grupper, undergrupper och trådar
- antal publik efter specifik typ
- en uppsättning grupper av uppgifter (aktiviteter):

• klass
• lärare
• ström eller grupp
• målgruppstyp
• antal klasser i denna grupp av klasser
• tid, om regissören vill "stelt" ställa in denna aktivitet vid en viss tidpunkt

Processen bör ordna klasser på ett tidsschema - ett schema. 4 parametrar är involverade i utvärderingen av schemat - antalet "fönster" i schemat för gruppen och lärarna, den jämna fördelningen av klasser över dagar för gruppen och lärarna. Betydelsen av dessa parametrar bestäms av regissören. Först ville jag tillämpa metoden att analysera hierarkier i objektivfunktionen, men jag skulle behöva införa en parvis jämförelse av dessa parametrar, så jag nöjde mig med en linjär funktion.

När det gäller klassrummen förenklade jag det, tog bort det från schemat, vilket gjorde det till en begränsning; vid sökning togs hänsyn till antalet lediga klassrum vid en viss tidpunkt. Efter att ha genererat schemat i tid ordnades publiken. I allmänhet är detta den enkla modellen jag beskrev. Jag experimenterade lite med den genetiska algoritmen, skissade upp ett program baserat på biblioteket under dagen, men jag gillade inte resultatet, och utan att tänka två gånger bytte jag till andra algoritmer. Jag tror att det dåliga resultatet berodde på mitt ogrundade tillvägagångssätt; sannolikt kodade jag utan framgång modellen i termer av GA. Jag började fundera på gren- och bindningsmetoden. Sökutrymmet är ett träd, där en nivå representerar en sysselsättning och en gren representerar ett tidsrutnätselement. Schemat anses vara en väg från trädets rot till en av de hängande hörnen. Längs vägen, under förgreningsprocessen, kontrolleras möjligheten och genomförbarheten av bypass enligt olika kriterier: lärarens sysselsättning, grupper, bedömning. Förbi trädet, naturligtvis, på djupet. På varje nivå finns det fria rutnätsceller för den aktuella uppgiften. Om regissören "stelt" har tilldelat en given uppgift för en viss tid, byggs en gren som motsvarar en viss tid. Vidare passerar grenen en uppskattning av den övre gränsen (plus att denna övervakas för närvaron av gratis publik av denna typ), och om uppskattningen av den övre gränsen är högre än uppskattningen av det för närvarande bästa schemat som hittats (och om det finns en ledig publik av denna typ), så går vi längs grenen, annars går vi vidare till nästa gren. I gren- och gränsmetoden är den viktigaste och viktiga punkten algoritmen för att hitta den övre gränsuppskattningen. Utan vidare bedömde jag det nuvarande ofullständiga schemat och jämförde det med det nuvarande bästa schemat som hittats. Eftersom, om man går längre, kommer uppskattningen av det ofullständiga schemat att bli sämre, om det redan är sämre än uppskattningen av det bästa schemat, så avvisas grenen. Och så, efter att ha programmerat det hela, förberett datan (jag tog det från systemet baserat på riktiga data), startade jag det på kvällen och gick hem. På morgonen, när jag kom till jobbet, laddade jag upp det bästa av de miljarder scheman som hittats till UZ CIS, men det var omöjligt att titta på det utan tårar. Jag var besviken, uppgiven och visste inte vad jag skulle göra härnäst. På kvällen gick jag med vänner för att dricka öl, och nu står jag vid hållplatsen, full och väntar på sista spårvagnen, och i mitt huvud är det bara träd, grenar, gränser, skattningar... och så gryr det på mig att på något sätt på varje nivå, när du bestämmer grenarna, sortera dem, se till att de alternativen går först som är mer sannolikt än andra att vara en del av det bästa schemat. Men hur gör man detta? Tanken kom när jag redan höll på att ta ur min andra cigarett. Det är först nödvändigt att bygga upp dina egna idealiska scheman för varje ämne i schemat, och för varje gren, beräkna graden av inkludering i dessa scheman och sortera efter det. På morgonen gick jag till jobbet snabbare än vanligt och ritade tekniska detaljer i huvudet längs vägen; vid lunchtid var heuristiken inbyggd, resultatet såg ganska anständigt ut i UZ CIS och jag log under den återstående halvan av arbetsdagen .

PS. Senare, när jag hörde talas om PageRank, trodde jag att den hade något liknande denna heuristik.

Det mesta du läser här är nonsens. Icke desto mindre, på vissa ställen, enligt min mening, finns det sunt förnuftstankar, tyvärr finns det inte så många sådana platser. L Tänk inte ens på att ta detta där problem med schemaläggningsteori studeras på allvar. För alla som vill skriva något bättre än detta rekommenderar jag starkt att läsa Hus bok. T. "Heltalsprogrammering och flöden i nätverk", dessutom är det förmodligen värt att läsa föreläsningarna av VMiK om teorin om optimering av N.M. Novikova (jag kommer inte ihåg var det finns på internet). Nu arbetar jag aktivt med problem med optimeringsteori, så alla som också är intresserade av detta ämne är alltid glada att prata. Skriva [e-postskyddad].

Introduktion. 8

1. Beskrivning av det tekniska området. 10

1.1. Formulering av schemaläggningsproblemet. 10

1.1.1. Allmän formulering av schemaläggningsproblemet. 10

1.1.2. Formulering av uppgiften att upprätta ett schema som tillämpas på schemat för träningspass. elva

1.2. Analys av befintlig programvara... 12

1.3. Formulering av problemet. 15

2. Utveckling av en matematisk modell och praktisk implementering av ett automatiskt schemaläggningssystem. 16

2.1. Matematisk modell av tidtabell vid ett universitet. 16

2.1.1. Notation. 16

2.1.2. Variabler. 18

2.1.3. Restriktioner. 19

2.1.4. Målfunktion. 21

2.2. Metoder för att lösa problemet. 22

2.2.1. Heltalsalgoritm. 23

2.2.2 Direkt heltalsprogrammeringsalgoritm. 28

2.2.3. Teknik för att erhålla en initial godtagbar grund. 32

2.3. Funktioner i den praktiska implementeringen av systemet.. 36

2.3.1. Modellval. 36

2.3.2. Beskrivning av ingångsinformation. 39

2.3.3. Utveckling av informationsstöd för uppgiften. 41

2.3.4. Funktioner i bildandet av restriktioner matematisk modell schemalägga uppgifter. 44

2.4. Resultat av programmet.. 45

2.5. Analys av de erhållna resultaten. 49

Slutsatser... 50

Litteratur. 51

Bilaga 1. Mjukvaruprodukters funktioner för schemaläggningssystem. 52

Bilaga 2. Lista över mjukvarumodulen över metoder för att lösa problemet med automatisk schemaläggning. 61

Introduktion

Kvaliteten på utbildningen av specialister vid universitet och särskilt effektiviteten av att använda vetenskaplig och pedagogisk potential beror till viss del på nivån på organisationen av utbildningsprocessen.

En av huvudkomponenterna i denna process - klassschemat - reglerar arbetsrytmen och påverkar lärarnas kreativa produktion, därför kan det betraktas som en faktor för att optimera användningen av begränsade arbetsresurser - lärarpersonal. Tekniken för att utveckla ett schema bör inte bara uppfattas som en arbetsintensiv teknisk process, ett objekt för mekanisering och automatisering med hjälp av en dator, utan också som en åtgärd för optimal hantering. Detta är alltså problemet med att utveckla optimala klassscheman på universitet med uppenbara ekonomiska fördelar. Eftersom deltagarnas intressen i utbildningsprocessen är olika, är uppgiften att skapa ett schema flera kriterier.

Uppgiften att skapa ett schema bör inte bara betraktas som ett slags program som implementerar funktionen för mekanisk distribution av klasser i början av terminen, då dess (programmets) användning slutar. Ekonomisk effekt från mer effektiv användning arbetsresurser kan endast uppnås som ett resultat av mödosamt arbete med att förvalta dessa arbetsresurser. Schemat här är bara ett verktyg för sådan hantering, och för dess fullaste användning är det nödvändigt att programmet kombinerar inte bara medel för att skapa ett optimalt schema, utan också medel för att bibehålla sin optimalitet i händelse av en förändring av vissa indata, som vid tidsplanens upprättande ansågs konstanta . Dessutom är optimal kontroll av ett så komplext system omöjligt utan ackumulering av viss statistisk information om de processer som sker i systemet. Därför är själva uppgiften att skapa ett optimalt schema bara en del av ett komplext ledningssystem för utbildningsprocesser.

Flerkriterierna hos detta problem och komplexiteten hos objektet för vilket en matematisk modell är byggd nödvändiggör en seriös matematisk studie av objektet för att öka funktionaliteten hos schemaläggningsalgoritmer utan att avsevärt komplicera modellen och, som en konsekvens, öka mängden minne som används och den tid som krävs för att lösa problemet.

1. BESKRIVNING AV DET TEKNISKA OMRÅDET 1.1. Formulering av schemaläggningsproblemet

Problemet med schemaläggningsteori i dess allmänna formulering anses vara mycket attraktivt, även om att uppnå även små framsteg mot en lösning vanligtvis är förknippat med enorma svårigheter. Trots att många högt kvalificerade specialister har hanterat problemen med schemaläggningsteori har ingen hittills kunnat få några betydande resultat. Misslyckade försök att få sådana resultat publiceras som regel inte, och detta beror delvis på det faktum att problemet fortsätter att locka många forskares uppmärksamhet på grund av dess uppenbara enkelhet i formuleringen.

1.1.1. Allmän formulering av schemaläggningsproblemet

I sin mest allmänna formulering är schemaläggningsuppgiften följande. Med hjälp av en viss uppsättning resurser eller serveringsanordningar måste ett visst fast system av uppgifter utföras. Målet är att hitta en effektiv algoritm för att beställa uppgifter som optimerar eller tenderar att optimera det erforderliga effektivitetsmåttet, givet egenskaperna hos uppgifter och resurser och de restriktioner som åläggs dem. De viktigaste effektivitetsmåtten är schemats längd och den genomsnittliga uppehållstiden för jobben i systemet. Modellerna för dessa problem är deterministiska i den meningen att all information som ligger till grund för beställningsbeslut är känd i förväg.

1.1.2. Formulering av uppgiften att upprätta ett schema som tillämpas på schemat för träningspass.

Den allmänna teorin om schemaläggning antar att alla serveringsenheter (eller processorer) inte kan utföra mer än en uppgift vid en given tidpunkt, vilket inte är tillräckligt för att schemalägga undervisningsklasser om klassrummet tas som en processor vid distribution av uppgifter. Så i vissa fall kan klasser med mer än en grupp samtidigt hållas i ett klassrum, till exempel allmänna föreläsningar för flera strömmar.

Därför, när den allmänna teorin om scheman överfördes till träningsschemat, gjordes följande antaganden:

Alla processorer (d.v.s. i fallet med ett utbildningsschema - ett klassrum) har en kapacitet - ett visst antal C ≥ 1. Kapaciteten hos en processor bestämmer antalet uppgifter som den samtidigt kan "bearbeta" vid en given tidpunkt (med med tanke på att processorer inte är enhetliga, skulle det vara intressant att överväga alternativet när processorn inte är publiken utan läraren och uppgiften är en ström från en eller flera utbildningsgrupper som han arbetar med);

Uppsättningen av uppgifter för distribution inkluderar lärarens utbildningssessioner med studiegrupper;

Tidsmodellen i systemet är diskret; hela fördelningen antas periodiskt upprepas över ett visst tidsintervall;

Alla uppgifter slutförs på samma tid, vilket tas som en enhet för diskretisering av tidsintervallet;

Uppgifter tillhör objekt, som är studiegrupper och lärare.

Som ett resultat är formuleringen av problemet med att schemalägga utbildningssessioner som följer: "För en given uppsättning klassrum (i detta fall betyder ett klassrum ett brett utbud av rum där utbildningssessioner hålls (från ett datorrum till ett gym)) och en given uppsättning tidsintervall (d.v.s. i huvudsak lektioner eller träningspar) för att konstruera en sådan fördelning av träningspass för alla objekt (lärare och träningsgrupper) för vilka det valda optimalitetskriteriet är det bästa."

1.2. Analys av befintlig programvara

Vid denna tidpunkt representeras mjukvarumarknadssektorn för klassschemasystem av ett stort antal olika mjukvaruprodukter. Tabell 1 visar endast ett fåtal av de som jag känner till.

Av objektiva skäl måste schemaläggningssystemet vid ett universitet (vilket betyder ett stort statligt universitet) nödvändigtvis implementera ett antal grundläggande funktioner:

Med hänsyn till lärarnas önskemål;

Säkra önskad publik;

Ange önskade målgrupper;

Redovisning av övergången mellan byggnader;

Kombinera grupper till strömmar för vilken uppsättning discipliner som helst;

Indelning i undergrupper;

Efter att ha upprättat schemat byt vid behov ut lärare eller ändra tidpunkten för lektionen.

Dessutom finns det också specifika krav för varje universitet för mjukvaruproduktens funktionalitet.

Möjligheterna hos, enligt min mening, de mest populära mjukvaruprodukterna på den ryska marknaden ges i bilaga 1.

Från listan ovan kanske bara "Methodist"-programmet mer eller mindre motsvarar den nödvändiga funktionaliteten hos en mjukvaruprodukt för schemaläggning vid ett universitet. Detta tillstånd förklaras lätt av det faktum att skolutbildningen idag är mer "standardiserad" (i betydelsen att organisera utbildningsprocessen) än universitetsutbildning. Denna standardisering leder till en stor potentiell marknad för mjukvaruförsäljning och återbetalning av utveckling genom att sälja ett stort antal exemplar av produkten till ett relativt lågt pris.

När det gäller universiteten är efterfrågan på schemaläggningssystem kanske till och med större än för skolor, men saken kompliceras av den stora specificiteten i organisationen av utbildningsprocessen vid varje enskilt universitet. Det är inte möjligt att skapa enhetlig programvara, och kostnaden för att skapa en specialiserad produkt från tredjepartsutvecklare visar sig vara orimligt hög. En förutsättning är dessutom att det finns ett ”fastställt” schema, vilket förutsätter möjligheten att ersätta lärare eller ändra tidpunkten för lektionerna. Hittills tillåter ingen mjukvaruprodukt dig att göra detta helt enkelt (även om Methodist har vissa möjligheter).

1.3. Formulering av problemet.

Syftet med detta arbete var att skapa en matematisk modell av ett universitetsschema som skulle göra det möjligt för en att effektivt (inom en given tidsram och med en given grad av optimalitet) lösa problemet med automatisk schemaläggning och som skulle ha flexibiliteten (mindre förändringar i vid förändringar av indata) för att anpassa systemet inom en specifik praktiska problem. För att förenkla problemet något, inledande skede Några designantaganden gjordes:

Schemat är baserat på högst två par per dag (vilket är ganska lämpligt för kvällslektioner);

Alla par hålls i en byggnad;

Problemet ställs i termer av linjär programmering;

Ingen ytterligare nedbrytning av modellen utförs;

Alla modellkoefficienter och önskade variabler är heltal;

Problemet måste lösas med en av de universella (oberoende av koefficienternas heltalsvärden) metoder för linjär heltalsprogrammering.

2. Utveckling av en matematisk modell och praktisk implementering av ett automatiskt schemaläggningssystem 2.1. Matematisk modell för universitetets schemaläggning

Låt oss bygga en matematisk modell av ett universitetsschema när det gäller linjär programmering. Låt oss introducera notation och definiera variabler och begränsningar.

2.1.1. Beteckningar

Universitetet har N studiegrupper, sammanslagna till R-strömmar; r – strömnummer, r = 1, ..., R, k r – studiegruppsnummer i ström r, k r = 1, ..., G r.

Indelningen i grupper i trådar görs utifrån principerna:

1. Användningen av två grupper av samma klassrumsfond för sina föreläsningar innebär automatiskt att de placeras i en ström (det antas att alla föreläsningar i studiegrupperna hålls tillsammans).

2. En grupp (eller en del av den), som en enhet i utbildningsprocessen vid ett universitet, kan ingå i olika strömmar, men bara en gång i var och en av dem.

3. Antalet trådar är inte begränsat.

Lektioner hålls på vardagar i en och en halv timmes intervall, som vi kommer att kalla par.

Låt oss beteckna:

t – nummer på veckans arbetsdag, t Є T kr, där

T kr – uppsättning arbetsdagsnummer för grupp k r;

j – parnummer, j = 1 ,..., J;

J – totalt antal par.

Med varje studiegrupp k r ström r under veckan, enligt läroplanen, bedrivs W kr lektioner, varav S r föreläsningar och Q kr praktiska. Låt oss beteckna:

s r – antal discipliner i listan över föreläsningsklasser för ström r, s r = 1 ,...,S r ;

q kr – disciplinnummer i listan över praktiska klasser för grupp k r, q kr = 1,..., Q kr.

Det förutsätts att föreläsningar hålls för alla grupper i strömmen samtidigt och i samma klassrum. Sedan, om mer än en lektion undervisas i en viss disciplin under en vecka, nämns denna disciplin i listan över föreläsningar eller praktiska lektioner så många gånger som de tillhandahålls läroplan för varje tråd eller grupp.

LÄRARE

Låt p vara talet (namnet) på läraren, p = 1 ,..., P. Låt oss introducera de booleska värdena och :

Lärarnas undervisningsbelastning planeras innan klassschemat upprättas, vilket gör att värdena i detta skede kan anses givna. För varje lärare p, p = 1 ,...,P anges även hans klassrumsbelastning - N p timmar per vecka.

REVISIONSFOND

Lektioner i varje ström kan endast hållas i vissa klassrum (exempelvis kan praktiska lektioner i datavetenskap endast hållas i visningsklasser). Låt vara:

(A 1 r ) – uppsättning publik för föreläsningar på stream r;

(A 2 r) – uppsättning klassrum för praktisk träning på ström r;

A 1 r – antal element i uppsättningen (A 1 r);

A 2 r – antal element i uppsättningen (A 2 r);

A 1 r + A 2 r – antalet åhörare i föreningen av uppsättningar (A 1 r )∩(A 2 r ).

Publikfonden bestäms innan schemaläggningen börjar, så uppsättningarna kan anses givna.

2.1.2. Variabler

Uppgiften med schemaläggning är att för varje föreläsning (på strömmen) och praktisk lektion (i gruppen) bestämma veckodagen och paret på denna dag, med hänsyn till uppfyllandet av begränsningarna som konstrueras nedan och minimeringen av en viss objektiv funktion.

Låt oss introducera följande nödvändiga booleska variabler:

=

Vid schemaläggning för grupper av kvällsklasser J=2. För en generalisering av modellen till alla former av lärande, se sidan 669.

2.1.3. Restriktioner

För varje grupp k r måste alla typer av klassrumsarbete slutföras under veckan:

Varje föreläsning s r respektive praktisk lektion q kr, för alla strömmar r och alla grupper k r kan inte hållas mer än en gång på någon dag t:

Om variablerna kopplar samman alla typer av aktiviteter med tidpunkten för deras implementering, då produkterna och associera tiden med namnet på läraren.

Varje dag t och i varje par j kan lärare p inte undervisa mer än en lektion i en disciplin i en ström eller i en grupp:

Slutligen, varje dag i varje klass bör antalet föreläsningar och praktiska lektioner inte överstiga den klassrumsfond som finns tillgänglig vid universitetet:

Dessutom, för alla uppsättningar av korsande uppsättningar (A 1 r) och (A 2 r) måste följande villkor vara uppfyllda:

De presenterade relationerna uttömmer de ovillkorliga restriktioner som alltid beaktas vid upprättandet av ett schema. Det kan dock finnas särskilda villkor, först och främst, att utföra vissa typer av arbete i den "övre" eller "nedre" veckan (dvs. en akademisk timme per vecka). Andra är inte uteslutna speciella villkor, men för att förenkla modellen övervägdes de inte.

2.1.4. Objektiv funktion

För att fullt ut kunna bedriva vetenskapligt, pedagogiskt och metodiskt arbete och förbereda sig för lektioner måste en universitetslärare ha ledig tid. Detta villkor är inte tillräckligt, men nödvändigt. Uppenbarligen ska han inte ha ledig tid i ett "trasigt" läge, som till exempel "fönster" mellan klasser med elever, utan om möjligt på helt fria arbetsdagar. Detta motsvarar att maximera lärares arbetsbelastning i klassrummet de dagar de har den (se (5)). Men samtidigt har lärare ojämlika anspråk på fritid, eftersom de har olika kreativ potential. Därför är det nödvändigt att införa viktningskoefficienter med vilka lärarens motsvarande status bör beaktas - hans akademiska examina och titel, befattning, vetenskaplig och social verksamhet m.m. I vissa fall är det, utifrån expertbedömningar, möjligt att använda individuella viktningskoefficienter som tar hänsyn till andra faktorer.

Så vi kommer att välja ett kriterium för kvaliteten på schemaläggning av klasser i form av att maximera det viktade antalet dagar fria från klassrumsarbete för alla lärare, vilket, givet en fast längd på arbetsveckan, motsvarar den maximala totala komprimeringen av klassrummets belastning.

Låt oss betrakta uttrycket för värdet av klassrumsbelastningen på dag t för lärare p:

där M är ett godtyckligt positivt tillräckligt stort antal; - den önskade booleska variabeln.

Av (10) följer att om , då = 1, och om , då = 0.

Med hänsyn till ovanstående materiella innebörd av optimeringskriteriet i ytterligare restriktioner (10), samt införandet av viktningskoefficienterna för lärarstatus, får vi det erforderliga optimalitetskriteriet:

Den införda objektiva funktionen är inte den enda möjliga. Införandet av andra objektiva funktioner förändrar inte begränsningarna för den matematiska modellen och metoder för att lösa problemet, men kan väsentligt påverka resultaten av beräkningar.

2.2. METODER FÖR LÖSNING AV PROBLEMET

Problemet med att maximera en linjär objektivfunktion som ställdes i föregående stycke under ett givet system av begränsningar är ett linjärt heltalsbooleskt programmeringsproblem, eftersom alla begränsningskoefficienter är heltal på grund av den diskreta naturen hos problemets initiala data; Dessutom kan de nödvändiga variablerna i den matematiska modellen bara ha två värden. Vid denna tidpunkt finns det flera möjliga metoder för att lösa denna typ av problem.

B – metoder för ordnad indexering och modifierade markeringar beskrivs, baserat på den lagrangiska nedbrytningen av den ursprungliga modellen till ett antal enradsproblem lösta med metoderna för att ordna indexering respektive modifierade markeringar. Tyvärr tillåter inte antalet operationer för varje metod en polynomuppskattning; Dessutom ökar dimensionen av tabellen med uppsättningar (mellanvärden) av metoder kraftigt med ökande dimension av problemet som löses, vilket är oacceptabelt i vårt fall. Kanske kommer en ändring av nedbrytningsalgoritmen för en specifik matematisk modell att minska storleken på tabellerna, men en sådan algoritm finns inte ännu.

I detta avseende valdes de lösningsmetoder som beskrivs i modifieringen av simplexmetoden för fallet med ett heltalslinjärt programmeringsproblem. I allmänt fall antalet operationer av simplexmetoden tillåter inte en polynomuppskattning (det visades till och med en klass av problem där antalet operationer är O(e n)), men för vårt problem tillåter det genomsnittliga antalet operationer en polynomuppskattning: O(n 3 m 1/(n-1 )) (n – antal variabler; m – antal restriktioner).

2.2.1. FULL HELTALSGORITM

Denna algoritm kallas för heltal eftersom om den ursprungliga tabellen består av heltalselement, så innehåller alla tabeller som härrör från algoritmen endast heltalselement. Liksom dual simplex-metoden utgår algoritmen från en dubbelt tillåten tabell. Om a i 0 (i = 1 ,..., n+m; a i 0 är koefficienterna för den objektiva funktionen) är icke-negativa heltal, då är problemet löst. Om för någon sträng a i 0

Låt ett heltals linjärt programmeringsproblem ges:

maximera

under förhållanden

Villkor (12) kan skrivas som

Låt oss anta att för t=0 (d.v.s. för den ursprungliga tabellen) är alla a ij heltal och kolumner (j = 1 ,..., n) är lexikografiskt positiva. Då förblir alla kolumner lexikografiskt positiva genom hela beräkningarna.

Innan vi presenterar en metod för att erhålla en ytterligare begränsning från den genererande strängen, introducerar vi en ny representation av tal. Låt [x] beteckna det största heltal som inte är större än x. För valfritt tal y (positivt eller negativt) och positivt kan vi skriva:

där (r y är en icke-negativ rest när man dividerar y med ). Särskilt, . Därför, om , då r = 1. Om , då r = 0.

Den införda ytterligare ojämlikheten måste uppfyllas för varje heltalslösning av problem (12). Betrakta någon ekvation i t-tabellen (som utelämnar radindex) med en 0

där x är motsvarande komponent i vektorn och är de aktuella icke-grundläggande variablerna. Vi kan uttrycka x, a 0 och a j med hjälp av representationen (14) som introducerades ovan:

Genom att ersätta uttryck (16) och (17) med (15) och ordna om termerna får vi:

Eftersom , och variablerna x och är föremål för kravet på icke-negativitet, är den vänstra sidan av ekvation (18) alltid icke-negativ. Tänk på uttrycket på höger sida, inneslutet i lockiga hängslen. Koefficienterna i detta uttryck är heltal, och variablerna är föremål för heltalskravet. Därför måste hela uttrycket inom parentes vara ett heltal. Låt oss beteckna det med s, dvs:

.

Den heltalssvaga variabeln s är icke-negativ. Om s var negativa, dvs. skulle ta värdena -1, -2, ..., och sedan multiplicera med skulle göra hela den högra sidan av ekvation (18) negativ, medan den vänstra sidan är icke-negativ.

Låt oss överväga två fall och . För och. Genom att ersätta uttrycket för x från (15) i ekvation (19), får vi:

Ekvation (21) måste vara uppfylld för varje heltalslösning på problem (12). Observera att om en 0 i ekvation (21). Därför kan ekvation (21) användas som en ledande linje i simplexmetoden. I synnerhet kan du alltid välja tillräckligt stort så att det ledande elementet i rad (21) blir lika med –1, vilket kommer att bevara tabellens integeritet. Valet av lämplig kommer att påverka konvergenshastigheten för algoritmen. Först och främst, låt oss beskriva själva algoritmen. Som en inledande lösning är det nödvändigt att ta en dubbelt genomförbar lösning, som kan erhållas genom att addera begränsningen x n + m+1 =M – x 1 - - … - x n 0, där M är en tillräckligt stor konstant, och bära ut en iteration med den tillagda raden och med den lexikografiskt minimala kolumnen , tagna som ledare. Algoritmen består av följande steg:

Steg 0. Börja med en dubbelt tillåten matris A 0 i ekvation (13), vars element är heltal (matrisen A 0 kan också innehålla icke-heltalselement, se om detta, sidan 306).

Steg 1. Bland raderna med a i 0 0 (i=1, ..., n+m), då är problemet löst.)

Steg 2. Välj (valsregeln kommer att beskrivas senare) och skriv ytterligare en rad längst ner i tabellen

Denna linje är vald som den inledande linjen.

Steg 3. Utför steget med dubbla simplexmetoden, stryk över den extra raden och återgå till steg 1.

För bevis på algoritmens ändlighet, se s. 303-304.

Urvalsregeln är formulerad enligt följande.

Steg 0. Låt raden med nummer v generera.

Steg 1. Låt vara den lexikografiskt minimala kolumnen bland kolumnerna med en vj

Steg 2. För varje a vj är det största heltal så att (lexikografiskt mindre).

Steg 3. Låt , a (rad v genererar). Sedan

.

Steg 4. Sätt för en vj

Urvalsregeln som beskrivs ovan låter dig göra det inledande elementet lika med -1, samtidigt som tabellens dubbla giltighet bibehålls och samtidigt kommer nullkolumnen att reduceras lexikografiskt så mycket som möjligt.

2.2.2 Direkt heltalsprogrammeringsalgoritm

Termen "direkt" när den tillämpas på en heltalsprogrammeringsalgoritm hänvisar till en metod som leder till en optimal lösning genom att successivt erhålla "förbättrbara" lösningar. Var och en av dessa lösningar är giltig i den meningen att den uppfyller både de linjära begränsningarna och heltalsvillkoret. En av de troliga fördelarna med algoritmen är möjligheten att avbryta beräkningarna innan den optimala lösningen erhålls och använda den bästa lösningen som erhållits som en ungefärlig lösning. Dessutom kan den direkta algoritmen användas i samband med dubbla algoritmer för att producera olika sammansatta algoritmer som kan gå från en fas som producerar dubbelt genomförbara lösningar till en fas som producerar direkt genomförbara lösningar.

Ett naturligt prejudikat för den direkta algoritmen är Gomori-algoritmen med heltal, eftersom processen för denna algoritm producerar en sekvens av dubbelt genomförbara heltalslösningar. Det bör påminnas om att Gomori-algoritmen för heltal är en modifiering av den dubbla simplexmetoden. Den största skillnaden med denna algoritm är att den ledande strängen är en Gomori-skärning med ett ledande element på -1. Detta snitt erhålls från den genererande strängen, som definieras som en av de möjliga ledande strängarna i den dubbla simplexmetoden. Att använda ett sådant snitt som en ledande rad kommer att bevara tabellens dubbla giltighet och integritet efter iteration.

Det visar sig att du på samma sätt kan modifiera simplexmetoden på ett sådant sätt att du får en algoritm som bevarar direkt tillåtlighet och integeritet för tabeller. För att beskriva beräkningsproceduren, överväg följande heltalsprogrammeringsproblem:

maximera

Antag att kolumnen är vald som den ledande och raden v är den ledande raden i iterationen av simplexmetoden, dvs. för alla rader I där a är >0. Innan vi utför den Gaussiska elimineringsproceduren i simplexmetoden, lägger vi till Gomori cutoff som erhålls från raden v till tabellen:

där J är uppsättningen av index för icke-grundläggande variabler i (22), s k är en ny (grundläggande) svag variabel och är en obestämd (tillfälligt) positiv konstant.

Observera att om vi sätter = a vs, kommer cutoff (23) att ha två viktiga egenskaper. För det första,

Detta innebär att tabellens direkta giltighet bevaras om vi använder cutoff (23) som ledande rad. För det andra, dvs. ledande element är 1 (om klipp används som ledande sträng). Det är lätt att verifiera (genom att undersöka formlerna för att ändra de grundläggande variablerna) att transformationen av en simplextabell med ett enda ledande element bevarar integeriteten för elementen i simplextabellen.

Dessa idéer fungerade som grunden för den direkta algoritmen i heltalsprogrammering:

Steg 0. Börja med en kolumntabell där a i 0 0 (i 1) och alla element a 0 j , a ij och a i 0 är heltal.

Steg 1. Kontrollera att villkoren a 0 j 0 (j 1); om de är nöjda, då är slutet, den nuvarande grundläggande lösningen optimal; om inte, gå till steg 2.

Steg 2. Välj den inledande kolumnen s med 0 s 0. Denna rad fungerar som generator för Gomori-snittet.

Steg 3. Skaffa Gomori-snittet från genereringslinjen och lägg till det längst ner i tabellen, d.v.s. lägg till ekvation (23) till problembegränsningarna, där .

Steg 4. Konvertera tabellen med cut (23) som första rad. Den svaga variabeln s k in (23) blir icke-grundläggande. Gå tillbaka till steg 1.

För bevis på algoritmens ändlighet, se s. 346-353.

Eftersom att välja en genererande sträng inte är en trivial uppgift, verkar det som att det måste finnas flera strängar som kan fungera som genererande strängar. I de preliminära argumenten användes den inledande linjen i simplexmetoden som genereringslinje. Denna linje ger alltid en cutoff som är den ledande linjen med ett ledande element lika med ett. Tydligen finns det andra rader i tabellen från vilka snitt med samma egenskaper kan erhållas. Låt oss anta att cutoff erhålls enligt formeln:

var bestäms av tillståndet

Låt oss definiera mängden V(s) som en samling rader som uppfyller villkoret (25).

Följande två regler är exempel på giltiga genereringsregler för strängval:

Regel 1.

1. Sammanställ en sekventiell ändlig lista med radindex så att indexet för varje rad visas i den minst en gång. Gå till 2.

2. Om listan är tom eller inte innehåller något index från V(s), återgå till 1.; annars, hitta det första indexet v V(s) i listan. Välj rad v som producerande. Utdataindex v och alla föregående index från listan. Gå till 3.

3. Välj konsekvent strängen v som tas i 2. som genererande tills v V(s). När v V(s), återgå till 2.

Regel 2.

1. Låt Vt(s) vara den mängd V(s) som motsvarar t-te bordet. Om V t (s) innehåller mer än ett element: V t (s) = (v 1, v 2, ..., v k +2), välj som en generator en rad så att i sekvensen av mängder V 1 (s 1), V 2 (s 2), ..., V t (s) linjen dök upp tidigare (inte senare) än de andra och förblev sedan tills V t (s); gå till 2.

2. Välj konsekvent strängen v som tas i 1. tills . En gång, gå tillbaka till 1.

2.2.3. TEKNIK FÖR ATT FÅ DEN URSPRUNGLIGA TILLÅTNA GRUNDEN

Var och en av ovanstående metoder kan endast lösas om det linjära programmeringsproblemet är antingen direkt eller dubbelt genomförbart. Sådan tillåtlighet innebär förekomsten av en initial godtagbar grund i det ursprungliga problemet. Om problemet är genomförbart både direkt och dubbelt så är den resulterande lösningen optimal. I de flesta fall, efter att ha ställt ett problem, visar det sig att det inte är tillåtet varken direkt eller dubbelt. Därför presenterar vi en algoritm för att erhålla en initial godtagbar grund.

Låt det linjära programmeringsproblemet skrivas i kanonisk form:

minimera

under förhållanden

Alla b i kan göras icke-negativa genom att vid behov multiplicera motsvarande ekvation med –1. Sedan kan du lägga till en artificiell variabel till varje ekvation (de artificiella variablerna måste vara icke-negativa) på ett sådant sätt att de bildar en initial bas från de artificiella variablerna:

Artificiella variabler kan härledas från svaga variabler som används för att förvandla ojämlikheter till ekvationer. Faktum är att om de initiala begränsningarna för ett linjärt programmeringsproblem ges i form av ojämlikheter:

sedan lägger vi till en svag variabel till varje olikhet får vi:

Om b i 0 kan s i användas som initiala grundvariabler.

Skillnaden mellan artificiella variabler och svaga variabler s i är följande. I den optimala lösningen på problemet måste alla artificiella variabler vara lika med noll, eftersom det inte finns några sådana variabler i det ursprungliga problemet. Å andra sidan är det mycket möjligt att i den optimala lösningen kommer de svaga variablerna att ha positiva värden. För att de artificiella variablerna ska bli noll kan objektivfunktionen representeras på följande sätt:

där M i är tillräckligt stora positiva tal. Idén med metoden motsvarar det faktum att artificiella variabler ges uppenbart höga priser. Denna metod leder till nollvärden av artificiella variabler i den optimala lösningen.

Det finns ett annat sätt att få den ursprungliga tillåtna grunden. I denna metod, liksom i den första, används artificiella variabler som initiala basvariabler. En ny objektiv funktion övervägs, som är summan av artificiella variabler. Det krävs att minimera användningen av z-ekvationen som en av begränsningarna. Om det ursprungliga ekvationssystemet har en genomförbar lösning, måste alla artificiella variabler bli lika med noll. Därför måste minimivärdet bli noll. Om , då har det ursprungliga ekvationssystemet inga tillåtna lösningar. Om , då kan vi utelämna objektivfunktionen och använda den optimala basformen som den initiala möjliga grunden för att minimera z. I litteraturen kallas denna metod för den tvåfasiga simplexmetoden. I den första fasen av metoden hittas en godtagbar grund genom att minimera , i den andra minimeras z och en optimal bas erhålls.

Betrakta följande linjära programmeringsproblem som ett exempel:

minimera

under förhållanden

där alla b i är icke-negativa.

Om vi ​​introducerar artificiella variabler och en ny objektiv funktion får vi följande problem:

minimera

,

under förhållanden

Om vi ​​subtraherar alla ekvationer som innehåller b i från -formen får vi:

-z

där System (26) är diagonalt med avseende på Den första fasen av simplexmetoden består av minimering under förhållanden (26). Det finns inga begränsningar för tecknet z. I beräkningsprocessen, så snart en artificiell variabel blir icke-grundläggande och dess koefficient i -form är positiv, exkluderas själva variabeln och motsvarande kolumnvektor från ytterligare beräkningar.

2.3. FUNKTIONER FÖR DET PRAKTISKA IMPLEMENTERINGEN AV SYSTEMET

I praktiken är det inte särskilt bekvämt att arbeta med information i den form som den definieras i en matematisk modell. Låt oss därför först av allt bestämma oss för ett sätt att organisera data eller en datamodell.

2.3.1. MODELLVAL

En datamodell är en uppsättning överenskommelser om metoder och medel för att formalisera beskrivningen av objekt och deras relationer relaterade till automatisering av systemprocesser. Typen av modell och de typer av datastrukturer som används i den återspeglar konceptet att organisera och bearbeta data som används i DBMS som stöder modellen, eller i det programmeringssystemspråk som databskapas på.

Som en del av att lösa detta problem är det nödvändigt att skapa en datamodell där volymen av extra information skulle vara minimal, det skulle finnas en grundläggande möjlighet för flera användares åtkomst till data och skulle säkerställas hög nivå dataskydd.

För närvarande finns det tre huvudsakliga tillvägagångssätt för att bilda en datamodell: hierarkisk, nätverk och relationell.

HIERARKISK ORGANISATIONSMETOD

En hierarkisk databas består av en ordnad uppsättning träd; mer exakt, från en ordnad uppsättning av flera instanser av samma typ av träd. En trädtyp består av en "rot"-posttyp och en ordnad uppsättning av noll eller fler underträdstyper (som var och en är en trädtyp). En trädtyp i allmänhet är en hierarkiskt organiserad samling av posttyper.

Integriteten hos länkarna mellan förfäder och ättlingar upprätthålls automatiskt. Grundregel: inget barn kan existera utan sin förälder. Observera att liknande underhåll av referensintegritet mellan poster som inte ingår i samma hierarki inte stöds.

NÄTVERKSMETOD FÖR ORGANISATION

Nätverksstrategin för dataorganisation är en förlängning av den hierarkiska. I hierarkiska strukturer måste en underordnad post ha exakt en förfader; i en nätverksdatastruktur kan ett barn ha hur många förfäder som helst.

En nätverksdatabas består av en uppsättning poster och en uppsättning kopplingar mellan dessa poster, och mer exakt, en uppsättning instanser av varje typ från en uppsättning posttyper som anges i databasschemat och en uppsättning instanser av varje typ från en given uppsättning anslutningstyper.

Relationstypen definieras för två typer av poster: förfader och avkomling. En instans av relationstyp består av en instans av en förfaderposttyp och en ordnad uppsättning instanser av en underordnad posttyp. För en given länktyp L med en förfaderposttyp P och en underordnad posttyp C måste följande två villkor vara uppfyllda:

1. Varje instans av typ P är en förfader till endast en instans av L;

2. Varje instans av C är ett barn till högst en instans av L.

RELATIONELLT SÄTT ATT ORGANISERA

De största nackdelarna med hierarkiska och nätverkstyper av datamodeller är:

1. För svår att använda;

2. Kunskap om fysisk organisation krävs faktiskt;

3. Applikationssystem är beroende av denna organisation;

4. Deras logik är överbelastad med detaljer om hur man organiserar åtkomsten till databasen.

Den vanligaste tolkningen av den relationella datamodellen tycks vara den av Data, som återger den (med olika förfinningar) i nästan alla sina böcker. Enligt Date består den relationella modellen av tre delar som beskriver olika aspekter av det relationella förhållningssättet: den strukturella delen, manipulationsdelen och den holistiska delen.

Den strukturella delen av modellen säger att den enda datastruktur som används i relationsdatabaser är den normaliserade n-ära relationen.

Manipulationsdelen av modellen bekräftar två grundläggande mekanismer för att manipulera relationsdatabaser - relationalgebra och relationskalkyl. Den första mekanismen bygger huvudsakligen på klassisk mängdteori (med vissa förfinningar), och den andra är baserad på den klassiska logiska apparaten av första ordningens predikatkalkyl. Huvudfunktionen för manipulationsdelen av relationsmodellen är att ge ett mått på relationaliteten hos något specifikt relationsdatabasspråk: ett språk kallas relationellt om det inte är mindre uttrycksfullt och kraftfullt än relationalgebra eller relationskalkyl.

Slutligen fixar den integrerade delen av relationsdatamodellen två grundläggande integritetskrav som måste stödjas i alla relationella DBMS. Det första kravet kallas kravet på entitetsintegritet. Det andra kravet kallas kravet på referensintegritet.

Efter en preliminär analys av den matematiska modellen av systemet och metoderna för att organisera data, såväl som programvara som finns tillgänglig på marknaden (hierarkiska och nätverksmetoder för organisation föreslår ett objektorienterat tillvägagångssätt för att organisera data, och idag finns det sådana DBMS:er (för till exempel Jasmin eller Informix Dynamic Server), men på Vid utvecklingstillfället fanns det ingen möjlighet att använda dem, samtidigt finns det mycket "kraftfulla" relations-DBMS (till exempel Oracle 8i)) valet gjordes till förmån för den relationella metoden att organisera datalagring.

2.3.2. BESKRIVNING AV INGÅNGSINFORMATION

All information som behövs för att lösa problemet specificeras innan iterationer av metoder för att lösa schemaläggningsproblemet påbörjas. För enkelhetens skull antas att den angivna informationen är konstant under hela den period som schemat utarbetas för.

Utan att förlora en viss grad av generalitet i uppgiften är det möjligt att bestämma en viss uppsättning indata som är nödvändiga för bildandet av begränsningar och lösning av problemet, och samtidigt gemensamt för alla varianter av praktiska implementeringar av systemet. På grund av uppgiftens särdrag (möjligheten till relativt enkel anpassning av den matematiska modellen för fallet med praktisk implementering inom ett visst universitet) utvecklades inte former av ingående informationsdokument. Detaljer om ingångsinformationen beskrivs i tabell 2.

Tabell 2. Beskrivning av information om indata

Namn på detaljer	Kännetecken för detaljer
inmatningsdokument	Typ	Max. längd	Noggrannhet
Efternamn, förnamn, patronym för läraren; Lärarens kontaktnummer; Akademisk examen; Akademisk titel; Grupp namn; Antal medlemmar i gruppen; Titel på kursen som undervisas; Antal klassrumstimmar; Publiksiffror; Publikinformation; Namnet på ämnet som läraren undervisar i; Nummer på gruppen där ämnet läses; Information om publiken där ämnet läses.

Utöver dessa data kräver den matematiska modellen närvaron av ytterligare data, som kan erhållas efter att ha analyserat ingångsinformationen programmatiskt.

2.3.3. UTVECKLING AV INFORMATIONSSTÖD FÖR UPPGIFTET

Vi kommer att analysera källinformationen för att bestämma sammansättningen och strukturen av information för efterföljande formalisering och konstruktion av en informations- och logisk datamodell (ILM). Ovanstående matematiska modell, såväl som ytterligare information från beskrivningen av ämnesområdet, gör det möjligt för oss att bestämma rollen för detaljer i den sammanhängande informationen i dokumentet. Baserat på denna analys kommer vi att fastställa detaljernas funktionella beroenden i enlighet med rekommendationerna och kraven för datanormalisering, varefter vi kommer att utföra själva normaliseringen. Syftet med normalisering är att minska (men inte nödvändigtvis eliminera) dataredundans. Men ibland skapas viss dataredundans avsiktligt för att förbättra programmets effektivitet. Låt oss definiera tre former av databasnormalisering.

Tabellen är i första normal form(1NF) om den har en primärnyckel är alla attribut enkla datatyper och det finns inga dubbletter av attribut. För att följa 1NF måste attributdomäner vara atomära värden och det får inte finnas några dubbletter av attributgrupper. Alla dubbletter av attributgrupper måste flyttas till den nya tabellen.

En tabell är i den andra normala formen (2NF) när den är i den första normala formen och varje icke-nyckelattribut är fullt funktionellt beroende av primärnyckeln (dvs. i 2NF måste varje icke-nyckelattribut helt bero på fälten i den primära nyckeln nyckel).

En tabell är i tredje normalform (3NF) om den är i 2NF och inte har några transitiva beroenden. Transitiva beroenden är funktionella beroenden mellan icke-nyckelattribut. Alla icke-nyckelattribut som är funktionellt beroende av ett annat icke-nyckelattribut i samma tabell skapar ett transitivt beroende och måste flyttas till en annan tabell.

De resulterande funktionella beroendena är ganska triviala och följer uppenbarligen från den matematiska modellen, så in ytterligare beskrivning de är inte givna. I den följande presentationen utelämnas också mellanliggande grader av normalisering. Därför presenterar vi endast den slutliga infologiska modellen av databasen (se fig. 1.).

Figur 1. Infologisk modell av databasen för uppgiften att schemalägga klasser

2.3.4. FUNKTIONER FÖR FORMATIONSBEGRÄNSNINGAR HOS DEN MATEMATISKA MODELLEN FÖR SCHEMAPROBLEMET

Att rita upp begränsningar (1) – (7) för den matematiska modellen för schemaläggningsproblemet är en ganska trivial uppgift som kan lösas med enkla SQL-frågor och kräver ingen preliminär analys av ingångsinformationen. Därför kommer vi bara att uppehålla oss mer i detalj vid begränsningar av formuläret (8).

Observera att i den matematiska modellen av systemet är ämnet som läses inte "bundet" till en specifik publik, utan till en viss uppsättning publik. Placeringen av specifika publiksiffror görs efter att uppgiften är löst. Begränsningar av formen (8) är meningsfulla endast när uppsättningarna av publiken skär varandra. I den matematiska modellen av systemet föreslås att man tar hänsyn till alla unika korsande par i form av restriktioner. Antalet av dessa korsningar kan vara stort, vilket kan leda till ett stort antal ytterligare restriktioner som negativt påverkar hastigheten på optimeringsalgoritmer. Antalet ytterligare restriktioner kan dock minskas avsevärt.

Låt oss betrakta fallet med ett linjärt arrangemang av korsande mängder (se fig. 2).

Fig.2. Linjärt korsande mängder

I fallet med ett sådant arrangemang av klassrumsuppsättningar för att genomföra klasser kommer det totala antalet begränsningar av formuläret (8) att vara n-1, där n är antalet uppsättningar. Arrangemanget av korsande uppsättningar som beskrivs ovan kan kallas linjärt, eftersom i detta fall n korsande uppsättningar är arrangerade som i en linje. Vi kan betrakta fallet när mängderna skär varandra på ett godtyckligt sätt (se fig. 3.).

Fig.3. Godtyckligt korsande mängder

Antalet begränsningar av formen (8) i detta fall kan reduceras genom att utforma dessa begränsningar analogt med fallet med ett linjärt arrangemang av mängder. För att göra detta är det nödvändigt att anta att till exempel uppsättningar B och D som skär A är en uppsättning, bestämma skärningsområdet för en sådan uppsättning med uppsättning A och utför sedan samma åtgärder med den resulterande skärningsområdet.

För mer information om detta, se sidan 210.

2.4. Programresultat

Under den praktiska implementeringen av systemet ägnades särskild uppmärksamhet åt uppgiften att skriva "kärnan" i systemet - metoder för att lösa problemet och förfaranden för att bilda begränsningar. Eftersom målet inte var att skriva en fullfjädrad kommersiell produkt, skrevs gränssnittsdelen i syfte att testa kärnan och bestämma gränserna för tillämpligheten av algoritmer, därför inkluderar den ett minimum av funktionalitet och innehåller inte indata förbearbetningsmoduler .

Systemkärnan och gränssnittet skrevs i Delphi 6.0. Metoder för att lösa och algoritmer för att bilda begränsningar skrivs med hjälp av objektorienterade tekniker, vilket kommer att göra det möjligt i framtiden att enkelt kapsla in dem i ytterligare modifieringar av systemet utan att bryta mot integriteten för interaktionen mellan olika algoritmer. Texten till objektmetoderna för att lösa problemet finns i bilaga 2. Databasen implementerades på Oracle 8i DBMS, förfrågningar till den utförs i PL/SQL-språket.

De initiala uppgiftsdata skrivs in i databastabeller med hjälp av begärandeformulär. En av dessa former visas i fig. 3.

Fig.3. Formulär för inmatning av initiala uppgifter

Data som erhålls som ett resultat av att lösa problemet räcker inte för att visa klassschemat direkt efter att problemet lösts, så en dataefterbehandlingsmodul skrevs. Det slutliga klassschemat visas i form av en tabell, vars exempel visas i fig. 4.

Ris. 4. Exempel på ett klassschema

Algoritmer för att lösa problemet testades på olika urval av källdata. Testning utfördes på en dator med en Intel Pentium 350 MHz-processor, Oracle 8i DBMS installerades på en server med dubbla processorer: 2 CPU Intel Pentium II 350 MHz, RAM 384 MB; LAN med en bandbredd på upp till 100 Mbit/s användes som kommunikationskanal. Som testkälldata använde vi riktiga data om grupper, lärare och läsämnen i kvällsutbildningen vid ChSU för 1999/2000 akademiska år, och slumpmässigt genererade initiala data (läsbara ämnen tilldelades slumpmässigt publik för klasser). I genomsnitt utfördes från 5 till 10 tester för varje testad dimension av källdata. Som ett resultat fick vi data som visas i tabell 2. Figur 5 visar en graf över beroendet av den genomsnittliga tiden för att lösa ett problem på antalet lästa ämnen och antalet grupper.

2.5. Analys av de erhållna resultaten

Genom att analysera erhållna data kan vi dra några slutsatser om funktionaliteten hos lösningsalgoritmerna och den matematiska modellen, deras brister och användningsområden.

För det första innehåller den använda matematiska modellen "extra" restriktioner, vars existens beror på den linjära heltalsmodellen; dessutom tilldelas varje ämne som läses på strömmen (strömmen kan bestå av en grupp) 12 (för kvällselever) variabler, som var och en är en boolesk variabel. För det andra ökar tiden som krävs för att lösa problemet kraftigt när indata ökar. Detta sker på grund av en kraftig ökning av antalet variabler och begränsningar i modellen, som ett resultat av vilket dimensionen av arrayerna ökar och följaktligen den tid som krävs för att lösa problemet. För det tredje omfattar det matematiskt formaliserade problemet endast uppgiften att skapa ett schema för kvällselever utan att ta hänsyn till övergångar mellan byggnader. Bokföring ytterligare krav kommer att öka antalet begränsningar av problemet, vilket kommer att negativt påverka hastigheten på lösningsalgoritmerna.

Låt oss vara uppmärksamma på den ökande skillnaden mellan minimi- och medelvärdet av tiden för att lösa problemet när problemets dimension ökar. Denna skillnad motsvarar hur "framgångsrikt" (närmast optimalt) den initiala genomförbara grundläggande lösningen av problemet hittades. Därför kan tiden som krävs för att lösa problemet reduceras avsevärt genom att "framgångsrikt" hitta den initiala grundläggande genomförbara lösningen. För att hitta en sådan lösning är det bäst att använda heuristiska och nedbrytningsalgoritmer.

Slutsatser Under arbetets gång byggdes en matematisk modell av universitetets schema för fallet med kvällsundervisning utan övergångar mellan byggnader, metoder för att lösa problemet valdes och en modell för lagring av initialdata för problemet utvecklades. Källdatalagringsmodellen, algoritmen för den matematiska formaliseringen av modellen och lösningsmetoderna implementerades i form av mjukvarumoduler. Algoritmernas hastighet testades på heterogena uppsättningar av initiala data, som ett resultat av vilket algoritmernas kapacitet och tillämpningsområde bestämdes.

Baserat på testresultaten fann man att driftshastigheten för problemlösningsalgoritmer starkt beror på mängden inmatad information och den initiala tillåtna grundläggande lösningen och därför är betydligt sämre än heuristiska och nedbrytningsalgoritmer. Men i fallet med en heuristisk lösning kan dess (lösnings)optimalitet (eller uppnående av ett globalt maximum) endast bevisas genom en fullständig sökning av alla möjliga alternativ (det är klart att i det här fallet kommer algoritmens körtid att vara mycket långa), därför upphör iterationer av heuristiska algoritmer när ett visst maximum (det är omöjligt att säga om det är lokalt eller globalt) av betydelse. Lösningen av en sådan algoritm kan vara nära optimal, men inte optimal. I det här fallet, för att uppnå ett globalt maximum, kan du använda lösningsmetoden som beaktas i arbetet, eftersom det optimala kan uppnås i flera iterationer av de beskrivna lösningsmetoderna.

LITTERATUR

1. Lagosha B.A., Petropavlovskaya A.V. En uppsättning modeller och metoder för att optimera klassscheman vid ett universitet // Ekonomi och matematik. metoder. 1993. T. 29. Nummer. 4.

2. Hu T. Heltalsprogrammering och flöden i nätverk. M.: Mir, 1979.

3. Lebedev S.S. Modifiering av Benders metod för linjär programmering med partiell heltal // Economics and Math. metoder. 1994. T. 30. Nummer. 2.

4. Lebedev S.S., Zaslavsky A.A. Användande speciell metod grenar och gränser för att lösa ett heltalsgeneraliserat transportproblem // Ekonomi och matematik. metoder. 1995. T. 31. Nummer. 2.

5. Zaslavsky A.A. Använda den variabla stratifieringsstrategin i allmänna problem med heltalslinjär programmering // Ekonomi och matematik. metoder. 1997. T. 33. Nummer. 2.

6. Lebedev S.S. Om metoden att beställa indexering av heltals linjär programmering // Economics and Math. metoder. 1997. T. 33. Nummer. 2.

7. Lebedev S.S., Zaslavsky A.A. Modifierad märkningsmetod för booleska programmeringsproblem // Ekonomi och matematik. metoder. 1998. T. 34. Nummer. 4.

8. Zaslavsky A.A. Kombinerad metod för att lösa ryggsäcksproblem // Ekonomi och matematik. metoder. 1999. T. 35. Nummer. 1.

Bilaga 1. Mjukvaruprodukters funktioner för schemaläggningssystem.

MED AUTOR-2+-systemet är designat för att snabbt och bekvämt skapa klassscheman och underhålla dem under hela läsåret.
A VTOR-2+ är ett universellt system. Det finns flera versioner av programmet utformade för alla utbildningsinstitutioner:

Gymnasium och specialiserade (matematik, språk, etc.) skolor, lyceum, gymnastiksalar;

Tekniska skolor, skolor och högskolor;

Universitet med en akademisk byggnad;

Universitet med flera akademiska byggnader (inklusive överföringar mellan byggnader).

A VTOR-2+ gör det möjligt att förenkla och automatisera det komplexa arbetet för schemaläggare så mycket som möjligt. Systemet hjälper dig enkelt att bygga, redigera och skriva ut i form av praktiska och visuella dokument:

Schema för klasser (studiegrupper);

Lärarnas scheman;

Schema för klassrum (kontor);

Utbildningsplaner;

Tariffering.

A VTOR-2+ har en snygg design och vänlig service. Programmet är ganska lätt att lära sig. Det finns en detaljerad manual som beskriver alla funktioner och metoder för att arbeta med programmet.
P Programmet körs på vilken IBM-kompatibel dator som helst, från och med 486DX med 4 Mb RAM (och högre), tar upp cirka 1 Mb på hårddisken. Operativsystem: MS DOS eller WINDOWS 95/98.
I driftstiden beror på storleken läroanstalt och datorkraft. En fullständig beräkning och optimering av schemat för en medelstor skola (30 klasser, 60 lärare, två skift) tar cirka 15 minuter på en Celeron-400-dator.

P Programmet kännetecknas av en unik och mycket kraftfull algoritm för att konstruera och optimera schemat. Det resulterande automatiska schemat kräver praktiskt taget ingen manuell modifiering, det vill säga även med mycket komplexa och strikta begränsningar placeras alla möjliga klasser automatiskt. Om det finns olösliga motsägelser i källdata kan de upptäckas och elimineras med hjälp av en speciell analysenhet.

A VTOR-2+ låter dig:

Optimera "fönster" i schemat;

Tänk på vilket antal dagar/timmar som krävs för både klasser och lärare;

Det är optimalt att placera klasser i klassrum (auditorier), med hänsyn till egenskaperna hos klasser, ämnen, lärare och klassrumskapacitet;

Ta hänsyn till arbetets karaktär och önskemål från såväl heltidsanställda som deltidsanställda timanställda;

Det är lätt att koppla ihop (”para ihop”) flera klasser (studiegrupper) till strömmar när man genomför några klasser;

Dela upp klasserna när du håller lektioner i ett främmande språk, fysisk utbildning, arbete, datavetenskap (och alla andra ämnen) i valfritt antal undergrupper (upp till tio!);

Införa (utöver huvudämnena) specialkurser och valfria;

Optimera schemats enhetlighet och arbetsintensitet.

2. "Schedule"-system ver 4.0 Moskva – LinTech

Det bör genast noteras att programmet "Schema" är inriktat på att upprätta ett skolschema; användning på universitet och högskolor är endast möjlig med vissa reservationer. Schemaläggningen görs inom ramen för en uppsättning villkor som bestäms vid stegen att mata in initiala data. En fullständig lista över möjliga villkor ges nedan:

- HANDLA OM det maximala lektionsantalet är begränsat – d.v.s. det maximala antalet tillåtna lektioner per dag;

- R enhetlig fördelning av lärares arbetsbörda mellan dagarna i schemat;

- R enhetlig fördelning av klassbelastning mellan dagarna i schemat;

- TILLövervakningsfönster i lärares scheman;

- P Programmet tar hänsyn till det faktum att klasser godtyckligt kan förenas och delas (klasser kan kombineras i strömmar eller delas upp i mindre undergrupper, och dessa undergrupper kan i sin tur fungera som grund för att slå samman till större grupper. Exempel: i skolan Nej 1859 Det finns 2 seniorklasser, men i var och en av dessa klasser finns två undergrupper för specialisering, lektioner i allmänna ämnen hålls för hela klassen på en gång och ämnen i specialisering - var för sig. Men eftersom undergrupperna för specialisering är för små och det finns inte tillräckligt med lärare, i vissa ämnen kan undergrupperna 11a och 11b också kombineras (till exempel på ett främmande språk) - detta gör det svårt att säkerställa kontinuitet i schemat för klasser (det är nödvändigt att säkerställa kontinuitet i schemat för var och en av undergrupperna);

- N förekomsten av flera skift - i detta fall måste enskilda klasser anlända senare än grupperna i det första skiftet; dessutom blir det svårare att kontrollera fönstren i lärarschemat, om det finns lärare som arbetar båda skiften - i detta i schemat för dessa lärare måste deras klasser "kontrakteras" runt skärningspunkten mellan skift;

- U villkoret att länka lärare till publiken - enskilda lärare har "sin egen" publik där de leder alla sina klasser;

- N närvaron av ett "flytande" skift - när starttiden för den första lektionen inte är exakt bestämd, eftersom det bildas dynamiskt, beroende på frisläppandet av relaterade klasser, lärare och publik;

- TILLövervakning av om schemat för ett objekt (klass, lärare, publik) faller inom det tillåtna arbetsintervallet (i kartan över tidsbegränsningar). Till exempel, för en lärare, indikerar kartan över tidsbegränsningar vanligtvis metodiska dagar, ibland individuella lektionsnummer - med ett ord anges de positioner för vilka det är omöjligt att ställa in klasser med deltagande av ett givet objekt;

- N förekomsten av kombinerade ämnen - såsom "främmande språk/datavetenskap", "datavetenskap/arbetskraft", etc. - när klassen är indelad i undergrupper;

- U villkoret att koppla ämnen till klassrum - att genomföra klasser i enskilda ämnen är endast möjligt i ett strikt definierat klassrum eller lista över klassrum (fysisk utbildning, arbete, etc.);

- MED lämnar schemat med hänsyn till att det i vissa ämnen inte är hela klassen som kommer till klassen, utan en undergrupp till den. För att förhindra att en annan undergrupp vandrar runt i skolan vid denna tidpunkt, kan sådana klasser strikt bara vara de första eller sista klasserna i klassschemat;

- “I upprätthålla paralleller” - för vissa lärare är det nödvändigt att ta hänsyn till det faktum att att genomföra klasser kräver långvariga förberedelser (till exempel kemilektioner), i detta fall försöker man ordna klasser i lärarens dagliga schema i block med paralleller till exempel först 5:e klass, sedan 7:e -y etc. eller vid fördelning mellan dagar fördela klasser i olika paralleller på olika dagar;

- OCH Ibland, när man upprättar ett schema, är det nödvändigt att ta hänsyn till nyansen att för vissa ämnen är schemat känt i förväg - i det här fallet introduceras sådana klasser som icke-rörliga (fasta);

- TILL kontroll av förbjudna kombinationer av ämnen som faller på en dag i klassschemat - det är till exempel inte önskvärt att " Fysisk kultur” och ”arbete” utfördes samma dag;

- I uppfylla villkoret för de erforderliga sekvenserna av ämnen - när det är nödvändigt att säkerställa installationen av grupper av klasser där klasser måste äga rum i en viss sekvens, till exempel fysik-astronomi, etc.;

- N förekomsten av klasser knutna till klassrum - huvuddelen av klasserna för sådana klasser hålls i detta klassrum, med undantag för de klasser som kräver ett specialiserat klassrum;

- N behovet av att ordna klasser i enskilda ämnen i två klasser i rad ("i par", "gnistor"), och detta villkor kan vara strikt (inte i något fall dela upp "gnistor" av klasser), eller kan vara att föredra (om det är inte möjligt att flytta två klasser, "gnistan" kan brytas);

Man tar hänsyn till att placering i vissa ämnen endast är tillåten i enstaka klasser.

3. ”Metodistiskt” system

Finns i två versioner.

Virtuell version.

Tillgänglig utan automatisk schemaläggningsmodul. Funktioner i den virtuella versionen:

Snabbsökning i listor över lärare, klassrum, klasser (grupper), discipliner, byggnader;

Erhålla referensinformation för varje hittat element i listan (publikkapacitet, alla auditoriumbyggnader X, adress och telefonnummer till läraren, förteckning över institutionen, antal timmar i disciplinen, lärarens undervisningsbelastning, etc.);

Kontroll och förmåga att omfördela timmar mellan veckor inom vilken akademisk disciplin som helst. grupper;

Automatisk kontroll av eventuella datainmatningsfel (överensstämmelse mellan det totala antalet timmar och klasstyper, icke-tilldelning av lärare till undergrupper, tidsbudget för studiegruppen och läraren, skillnader mellan timmar i strömgrupper, etc.);

Möjlighet till systematisk lagring (och snabbsökning) ytterligare (krävs inte för schemaläggning) information: foton av lärare, curatorer för studiegrupper ( klasslärare), uppgifter om företrädare för föräldrakommittéer, positioner, akademiska examina och titlar som ansvarar för publiken, ...

Få snabbt fullständig information om en kombination av faktorer (alla grupper i strömmen, alla discipliner för lärare X, angivande av arbetsbelastningen per vecka och typ av klasser, vilka discipliner som får undervisas i datorklassen, personliga önskemål om genomförandet av klasser för alla lärare, en lista över helgdagar i den syriska gruppen och mycket mer etc.);

Möjligheten att se, skriva ut och redigera ett färdigt schema med kontroll av ändringarnas korrekthet (beläggning av klassrum, lärare, grupper/undergrupper, ...);

Du kan när som helst beställa en schemagenereringsmodul för förberedda data;

Schemat genereras på din dator med möjlighet att ändra inställningar, styra, redigera osv. (utan möjlighet att byta timmar, discipliner, lärare, ...);

Om behovet av en mindre (upp till 10 %) förändring i källdata upptäcks (fel, plötsliga tillägg hittas), är det möjligt att beställa om schemagenereringsmodulen mot en liten avgift;

Du kan växla till standardversionen när som helst;

Metodist - standard.

Förutom funktionerna i den virtuella versionen innehåller den:

Automatisk schemaläggningsmodul;

Fördelning och kontroll av undervisningsbelastning;

Strikt efterlevnad av ordningsföljden för disciplinen (föreläsningar - 2 timmar, praktiska - 4 timmar, laborationer...);

Skapa ett schema för alla typer av utbildningsinstitution: veckovis eller termin (från 1 till 23 veckor);

Redovisning för att kombinera grupper (klasser) till strömmar och/eller dela in dem i undergrupper;

Tilldelning av specialklassrum (datorklasser, språklaboratorier, simbassäng, ...);

Redovisning av anställning av lärare och klassrum (deltidsarbete, användning av en gemensam utbildningsbas);

Redovisning av övergångstid mellan byggnader;

Helger och helgdagar - allmänt och för enskilda studiegrupper (nationella, religiösa, allmänna helgdagar);

Angivande av orsakerna till den "misslyckade tilldelningen" av klasser (klassrummet är upptaget, läraren är tilldelad en oönskad veckodag) med möjlighet till deras "manuella" korrigering;

Möjlighet till upprepad automatisk "förbättring" av schemat;

Möjlighet att ändra betydelsen av faktorer som beaktas vid upprättandet av schemat;

Möjligheten att införa lärares prioriteringar - i vilken grad deras individuella önskemål beaktas;

Begränsningar för "Methodist"-funktionen:

Schema för flera skift är begränsade till ett maximalt antal lektioner per dag - 7;

Klasserna börjar alltid med den första lektionen/paret (vid behov är det möjligt att tilldela en "gratis lektion" till det första paret);

Tidpunkten för ändringen beaktas inte (till exempel för att kontrollera möjligheten att flytta mellan byggnader);

Klassernas "svårighetsgrad" tas inte med i beräkningen för deras rationella fördelning under veckan (även om det är möjligt att göra detta indirekt);

Lektionernas längd är konstant (det är omöjligt att skapa ett schema för en 30-minuterslektion på högstadiet och 45-minuterslektioner i gymnasiet).

Bilaga 2. Lista över mjukvarumodulen över metoder för att lösa problemet med automatisk schemaläggning

typ MyArray= array av array av real;

MyArray_X = array av longint;

procedure Step_Dual_simplex(var a:MyArray; m,n,i1,j1:heltal);

(utför ett steg av den dubbla simplexmetoden,

ledande element - a)

var i,j:heltal;

b,b1:array av verkliga;

SetLength(b,m);Setlength(b1,n);

för i:=0 till m-1 gör b[i]:=a;

för i:=0 till n-1 gör bl[i]:=a;

för i:=0 till m-1 do

för j:=0 till n-1 börjar

om (i=i1) och (j=jl) då a:=1/b

om (i=i1) då a:=b1[j]/b

om (j=j1) då a:=-b[i]/b

annars a:=a-b[i]*bl[j]/b;

för i:=0 till n-1 gör a:=0;a:=-1;

Slutför(b); Slutför(b1);

function Lexikogr_few(a:MyArray; m,n:heltal;i,i1:heltal):boolean;

(den första kolumnen är lexikografiskt mindre än den andra)

Lexikogr_få:=falskt;

medan (a=a) och (j

function Find_nu(a:MyArray;m,n:heltal; i,i1:heltal):longint;

(i är indexet för den lexikografiskt minimala kolumnen)

medan (a=a) och (j

if (j 0) then Find_nu:=Round(Int(a/a));

procedure Full_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:heltal);

(Fullständig heltalsalgoritm för det linjära heltalsproblemet

programmering,

se Hu T. "Heltalsprogrammering och flöden i nätverk", s. 300-309,

a är en matris med storleken m+n+2*n+1, analogt:

Vi måste hitta det maximala

z= - 10x1 - 14x2 - 21x3

2x1 + 2x2 + 7x3 >= 14

8x1 + 11x2 + 9x3 >= 12

9x1 + 6x2 + 3x3 >=10,

proceduren returnerar en vektor X, vars första m komponenter är den önskade lösningen,

om den sista komponenten i vektorn = 1, så existerar inte lösningen eller den = oändlighet)

var i,i1:heltal;

medan (i =0) gör Inc(i); (producerar sträng)

medan (j =0) gör Inc(j);

för i1:=1 till n-1 gör om (a

minsta kolumn)

(alfaval)

(Writeln(i," ",j);readln;)

för i1:=1 till n-1 gör om a

j1:=Find_nu(a,m,n,j,i1);

om (j1>0) och (-a/j1>alfa) då alfa:=-a/j1;

(writeln(alfa," ",i," ",j);readln;)

(får Gomori-snittet)

för i1:=0 till n-1 gör om a>0 sedan a:=round(Int(a/alfa))

a:=round(Int(a/alfa));

om Frac(a/alfa)0 då a:=a-1;

Steg_Dual_simplex(a,m,n,m-1,j);

tills (i>=m-1) eller (j>=n);

för i:=0 till m-1 gör x[i]:=runda(a);

om j>=n så x:=1 annars x:=0;

procedure Step_One_Simplex(var a:MyArray; m,n,i:heltal);

var i1,i2:heltal;

(Ett steg i den direkta heltalsmetoden (den producerande raden är den sista

i - genererande kolumn))

för i1:=0 till m-2 gör a:=a/(-a);

för i2:=0 till n-1 do

för i1:=0 till m-2 do

om i2i då a:=a+a*a;

procedur Direct_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:heltal);

(Direkt heltalsalgoritm för heltalslinjärprogrammeringsproblemet,

se Hu T. "Heltalsprogrammering och flöden i nätverk", s. 344-370,

a är en matris med storleken m+n+3*n+1 analogt:

måste maximeras

z = x1 + x2 + x3

4x1 + 5x2 + 2x3

då kommer matris a att se ut:

10 1 1 1 - på den här raden är den första siffran den grova maxsumman av icke-grundläggande variabler

0 0 0 0 - snöre för att klippa av Gomori,

Algoritmen fungerar bara när a>=0

returnerar vektor X - i stället för identitetsmatrisen den önskade lösningen,

om den sista komponenten innehåller en enhet finns det ett fel i beräkningarna)

var i,j,i1,j1:heltal;

b,b1,b2:array av byte;

SetLength(b,m);SetLength(b1,m);

för i:=0 till m-1 gör bl[i]:=0;

(kontrollera optimalitetstillståndet)

för j:=1 till n-1 gör om a

medan bool börjar

(sök efter genereringskolumnen)

bool:=false;j1:=0;

för j:=1 till n-1 börjar

om a>0 då

för i:=0 till m-3 gör a:=a/a;

om inte bool, börja då j1:=j;bool:=true;end else if Lexikogr_few(a,m,n,j,j1)

(sök efter genererande sträng)

för j:=1 till n-1 do

om a>0 då

för i:=0 till m-3 gör a:=a*a;