Stillheten hersket, som ble brutt av Schweik selv og sukket:
– ... Det må være disiplin i militærtjenesten – uten den ville ingen løftet en finger for saken. Vår sjefløytnant Makovets sa alltid: «Disiplin, idioter, er nødvendig. Uten disiplin ville du klatre i trær som aper. Militærtjeneste vil gjøre folk ut av deg, hjerneløse idioter!» Vel, er det ikke slik? Se for deg et torg, for eksempel på Karlsplassen, og på hvert tre sitter det en soldat uten disiplin. Dette skremmer meg fryktelig.
Jaroslav HASHEK DEN GODE SOLDATEN SCHWEIKS EVENTYR

Klasseplanen er kombinasjonen i rom og tid av en disiplin (fag), lærer (lærere), publikum og gruppe (undergruppe, strøm) av elever.

Formulering av problemet

Jeg skal være kort.

Ved gjennomføring av en klasse kan alle deltakere være fraværende, for eksempel på et avdelingsmøte, studenter kommer som regel ikke, eller studenter har gått til militæravdelingen (de har sin egen timeplan), og for den typen klasse er det ingen disiplin, lærer og publikum.
Kontinuitet (ingen vinduer) er som regel et nødvendig krav for elever og gjerne for lærere.
Timeplanen kan settes sammen for et semester/halvsemester for uke, med to uker og teller/nevner (oddetall uke/partall uke). Det er også en månedsplan.
Klasser skal kunne settes i manuell modus (med andre ord i editoren). For eksempel et akademisk råd eller et par av en stor sjef, eller til og med okkupasjonen av bare en god person.
Det skal være et system med forbud for alle deltakere i timen. For eksempel, nå tjener nesten alle lærere penger ved siden av (ellers vil du ikke kunne overleve) eller klasseromsfondet er delt mellom fakultetene og klasser kan ikke holdes i deler av klasserommene etter lunsj.
Tilstedeværelsen av sofistikerte ønsker fra lærere, en får 5 klasser om dagen for å frigjøre andre dager, og den andre får ikke mer enn to klasser om dagen, han blir overtrøtt, og hvis det er en forelesning, så en klasse og definitivt 2. eller 3. klasse.
Klasser i ulike bygg krever mer tid for overgang enn pausetiden mellom timene. Betingelsen for å minimere bevegelser er også naturlig.

Konklusjon. Som det fremgår av uttalelsen, er det mulig å vurdere kvaliteten på timeplanen først etter at den er ferdig utarbeidet. Derfor kan bruk av genetiske algoritmer gjøre det mulig å konstruere en løsning på det ønskede problemet og til og med oppnå, på en måte, en av de gode. Samtidig konvergerer genetiske algoritmer veldig raskt til den optimale i begynnelsen, noe som betyr at det praktisk talt ikke vil være noen begrensninger på mengden inndata.

Bildet er tatt herfra.

Genetisk algoritme

Rent retorisk vil jeg gjenta hovedstadiene i den genetiske algoritmen:

Sett målfunksjonen (fitness) for individer i befolkningen
Lag en innledende populasjon
(Start av syklus)
1. Reproduksjon (kryssning)
2. Mutasjon
3. Beregn verdien av målfunksjonen for alle individer
4. Dannelse av en ny generasjon (utvalg)
5. Hvis stoppbetingelsene er oppfylt, så slutten av sløyfen, ellers (begynnelsen av sløyfen).

Den vanligste feilen ved bruk av genetiske algoritmer er i utvalget av gener. Ofte er genene som velges ganske enkelt løsningen i seg selv. Valget av gener er det mest ikke-trivielle og kreative elementet når man lager en genetisk algoritme. Personlig mener jeg at valg av gener bør tilfredsstille følgende to grunnleggende krav.

Basert på settet av gener, bør løsningen på det ønskede problemet konstrueres raskt og entydig.
Ved kryssing må avkommet arve egenskapene til foreldrene.

En kommentar. Settet med gener skal gi hele settet av (muligens optimale) løsninger på problemet. I prinsippet er det ikke nødvendig å kreve en-til-en, det er nok at kartleggingen av gener på løsningsrommet er på(oversikt).

Planleggingsalgoritme

Jeg vil kun beskrive genene i seg selv, algoritmen for å konstruere en løsning basert på dem, kryssing og mutasjon.

Hvordan en erfaren ekspeditør lager en tidsplan. Ordet erfaren betyr at ekspeditøren allerede har satt opp timeplanen én gang og kjenner til flaskehalsene. For eksempel mangelen på store streamingpublikum eller dataklasser. Det første kurset, siden de har mange strømmeforelesninger og samtidig klasser i undergrupper i datatimer, engelsk/engelsk fra bunnen av/tysk/fransk osv., og myndighetene krever at det første kurset ikke i noe tilfelle skal ha noen vinduer og ingen mer enn to forelesninger per dag og dagene var jevnt belastet. Derfor arrangerer en erfaren ekspeditør de første "smale klasser", klasser av myndighetene på deres forespørsel, og klasser med spesielt irriterende lærere. Deretter, ved å bruke de arrangerte timene som et skjelett, fullfører han raskt timeplanen. La oss prøve å imitere, på en måte, denne prosessen.

Noen av timene er allerede på timeplanen vår, resten vil bli nummerert sekvensielt. Vi vil betrakte utvalget av yrkesnummer som et genom, selv om det i prinsippet kun er rekkefølgen på yrker som er viktig her. For å bygge en timeplan, vil vi sekvensielt trekke ut klassetall og sette den valgte klassen på timeplanen, tilfredsstille de nødvendige kravene og maksimere den objektive funksjonen for studenter, lærere og publikum (de har også ansettelseskriterier).
Hvis de nødvendige kravene ikke kan oppfylles, kan et individ med et slikt genom kasseres som ikke-levedyktig. Hvis det ikke er mulig å lage en tidsplan, kan du erstatte de nødvendige kravene med en straff i objektivfunksjonen.

Kryssing kan organiseres på flere måter. For eksempel en av dem. La oss ha følgende gener

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

Her kan du se at aktivitet 3 forekommer i begge gener opp til posisjon 2 inklusive, og for eksempel fra posisjon 2 til posisjon 5 er det et intervall for 1 aktivitet. La oss lage følgende tegn

_ * * * * _ _ for 1 leksjon
* * * _ _ _ _ for leksjon 2
* * _ _ _ _ _ for leksjon 3
_ _ _ _ _ * _ for leksjon 4
_ _ * * _ _ _ for leksjon 5
_ _ _ _ * * * for leksjon 6
_ _ _ * * * * for leksjon 7

her indikerer stjernene mulige posisjoner for etterkommerens yrkesnummer. Du kan velge mellom en eller flere mulige løsninger som barn eller barn av disse foreldrene. Det finnes alltid en løsning for å velge genene til en etterkommer, for eksempel tilfredsstiller begge foreldrene selv. La oss omskrive tabellen gjennom sett med mulige posisjoner

1 posisjon (2, 3)
2. plassering (1, 2, 3)
3. plassering (1, 2, 5)
4. plassering (1, 5, 7)
5 posisjoner (1, 6, 7)
6. plassering (4, 6, 7)
7 posisjon (6, 7)

For å konstruere løsninger kan du bruke følgende algoritme. Først vil vi legge inn antallet klasser som er mindre vanlige. Hvis vi sorterer dem i stigende rekkefølge, har vi det
1 gang 4
2 ganger 3,5
3 ganger 2, 6
4 ganger 1, 7
Derfor setter vi først leksjon 4 i 6. posisjon, deretter 3 eller 5 i henholdsvis posisjoner (1, 2) eller (3, 4). På hvert trinn kan du kaste en eske med fyrstikker. Som et resultat kan du for eksempel få følgende trinn for kryssingsalgoritmen

* * * * * 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

Siden det er mulig at den riktige sekvensen kanskje ikke er konstruert, er det bedre å organisere algoritmen i form av en enkel rekursjon for å kunne gjenta algoritmen, dvs. organisere litt søk.

Mutasjonen kan organiseres ganske enkelt ved tilfeldig å omorganisere yrkesnumrene.

Konklusjon

Dette er på sett og vis en fortsettelse av innleggene mine Program for timeplanlegging ved et universitet og Beregning av arbeidsmengden for avdelingen.

Jeg foreslår igjen følgende løsning (skisse).

GUI på PyQt eller PySide
PosgreSQL DBMS (jeg har ca. 80% klar her), i tillegg til selve timeplanen, inneholder den også applikasjoner og lærerarbeidsmengder, læreplaner og mye mer (for dette formålet vil jeg publisere ett eller flere emner)
nettgrensesnitt på CherryPy+Cheetah (men dette kan diskuteres)
eksport av eventuelle rapporter (planer, treningsoppdragskort osv.) i OpenDocument-format (GOST R ISO/IEC 26300-2010. Gosstandart of Russia (06/01/2011)) via ODFPY
planleggingsalgoritmer fra meg (dette emnet handler om det)
produksjon fra meg
for de interesserte, arbeid med den felles kjernen
for de interesserte, tilpasning til sitt eget universitet og evnen til å endre alt fleksibelt, livet går videre, og tjenestemenn sover ikke

Takk til alle som har svart, etter å ha diskutert dette emnet vil det være mulig å organisere seg.

Timeplanen regulerer rytmen i skolehverdagen, arbeidet og resten til elever og lærere.
Effektiviteten til hele utdanningsprosessen avhenger i stor grad av kvaliteten.

Berettigelse av undervisning og skoletime

Skolens utdanningsregime skal samsvare med funksjonsevnen til elevene. Volum, innhold og organisering av utdanningsprosessen må sikre en slik tilstand av kroppen der tretthet vil forsvinne fullstendig i hvileperioden.

Hovedkriteriene for å vurdere timene med tanke på elevenes funksjonsevne er vanskeligheter og slitsomhet. Tretthet er preget av endring i ytelse, og vanskelighetsgraden til faget er preget av prestasjonsnivået, det vil si graden av mestring av undervisningsmateriell. Derfor må begge faktorene vurderes likt under planlegging.

I det juridiske aspektet gjenspeiles problemet med å utarbeide en skoleplan i nye hygieniske krav for å utarbeide en timeplan, som er basert på data fra moderne vitenskapelig forskning om biorytmologien til mental ytelse og vanskelighetstabellen til fagene av I.G. Sivkova. Men for nestleder ved skolen, som lager timeplanen, er det viktig ikke bare å vite hvor vanskelig faget er, men også å forestille seg styrken til den slitsomme effekten av leksjoner i et bestemt emne på helsen til elevene . Dessverre er vanskelighetstabellen I.G. Sivkova tar ikke hensyn til en slik del av treningen som kjedelighet av fag, som først og fremst påvirker studentens helse.

Moderne forskning gir innsikt i forholdet mellom kjedelighet og vanskeligheter i faget, selv om disse indikatorene varierer betydelig i noen fag. Disse representasjonene gjør det mulig å kombinere to indikatorer til en - akseptabiliteten av varen. Derfor skal tabell I.G. Sivkov, er det mulig å foreslå et alternativ - en skala for emneakseptabilitet, som vil ta hensyn til komponentene i vanskeligheter og kjedelighet ved læring, så vel som egenskapene til hver utdanningsinstitusjon og læreplanen til hver klasse.

Akseptabilitetsskalaen består av kolonnen "Elementer etter rangering", der elementer legges inn hvis rangeringer ble oppnådd basert på resultatene av diagnostisering av vanskelighetsgraden og kjedelighet ved hjelp av metoden for ekspertvurderinger - deres algoritme er presentert i vedlegg 1. foreslåtte skala er konstant i sin struktur, men variabel i innhold (se tabell 1).

Tabell 1

Omtrentlig vareakseptabilitetsskala

Som det fremgår av tabell 1, består skalaen av fem vanskelighetsgrupper. Hver gruppe har en poengsum - dette er en konstant del av skalaen og er ikke gjenstand for endringer. Innholdet (dvs. sett med elementer) i hver gruppe kan endres avhengig av diagnoseresultatene. Den representerer den variable delen av skalaen.

På ungdomsskolen nr. 618 i St. Petersburg fikk vi følgende skala for emneakseptabilitet (se tabell 2).

tabell 2

Akseptabilitetsskala for varer

Planleggingsalgoritme

Siden hver utdanningsinstitusjon vil ha sin egen aksept av fag, bør leserne ikke kopiere den gitte en-til-en-skalaen. Det er tilrådelig å diagnostisere vanskelighetsgraden og kjedeligheten til fagene på skolen din ved å bruke metoden for ekspertvurderinger.

I tillegg, når du lager en timeplan, er det fornuftig å bli veiledet av en tabell som rangerer prestasjonsnivået til elever i forskjellige klasser i forskjellige leksjoner i løpet av skoleuken (se vedlegg 2).

Vi har laget en algoritme for å lage en fysiologisk basert timeplan som tar hensyn til realistiske hygienekrav. Denne algoritmen kan brukes til å lage en undervisningsplan både på en skole med et stort antall andre og tredje klasseklasser, og i en relativt liten utdanningsinstitusjon. Algoritmen er beregnet på spesialister som lager en tidsplan uten å bruke et dataprogram.

Når du bruker automatiserte programmer, er det tilrådelig å ordne objekter ved hjelp av et automatisert program i trinn basert på den foreslåtte algoritmen. Som praksis viser, kan disse programmene bare brukes som et hjelpeverktøy for:

innledende arrangement av objekter etterfulgt av manuell etterbehandling;
lagre informasjon og skrive den ut.

Etter den automatiserte distribusjonen av objekter (programmet arrangerer som regel fra 40 til 70%), er det nesten umulig å ta hensyn til de hygieniske kravene til timeplanen, siden det ikke bare er nødvendig å levere de gjenværende uarrangerte objektene , men også for å betydelig endre (opptil 60%) det automatiserte arrangementet av objekter i henhold til prinsippet "bare for å ordne det."

Derfor, når du bruker et dataprogram for å lage en rasjonell tidsplan, under hensyntagen til realistisk gjennomførbare hygieniske og pedagogiske krav, og spesifikasjonene til en utdanningsinstitusjon, er det nødvendig å arrangere fag i trinn ved å bruke algoritmen foreslått ovenfor. I dette tilfellet må hvert trinn i å arrangere en gruppe objekter avsluttes med manuell etterbehandling, med fokus på kravene ovenfor. Dette vil tillate deg å lage en mer rasjonell tidsplan og om mulig ta hensyn til alle nødvendige forhold.

Prosedyre for endring av timeplanen

Algoritme for justering av skoleplanen

Hvis du trenger å endre timeplanen i løpet av skoleåret, noe som skjer ganske ofte, må du jobbe med tabelloppsettet. For å endre tidsplanen på den, må du utføre følgende beregninger og omorganiseringer.

Den foreslåtte metoden for å lage en tidsplan tar ikke mer tid enn vanlig, men lar deg lage en tidsplan på riktig måte, dvs.:

lag din egen skala for emneakseptabilitet (vanskeligheter og kjedelighet) for å lage en mer rasjonell skoleplan;
holde en tilstrekkelig stor mengde nødvendig informasjon i synsfeltet til nestleder ved skolen;
fordel leksjonene jevnt for hver dag (unngå et for stort antall syvende leksjoner);
starte alle klasser fra første leksjon, noe som gir mulighet for læring i samme rytme, siden elevene starter skoledagen til samme tid hver dag;
regulere vanskelighetsgraden på skoledagen avhengig av dynamikken i den ukentlige ytelsen til skolebarn;
arrangere leksjoner med praktisk talt ingen "vinduer" eller med et minimum antall av dem, noe som lar deg opprettholde rytmen i lærerens arbeid og skape et gunstig arbeidsmiljø;
rasjonelt alternerende objekter i forskjellige retninger;
rasjonelt arrangere de nødvendige dobbelttimer;
raskt endre og justere tidsplanen på grunn av produksjonsbehov.

I tillegg krever ikke denne metoden en betydelig mengde papiremner (tilleggstabeller, spesielt hvis skolen har mange andre og tredje klasseklasser (30 eller flere).

For å utarbeide en tidsplan av høy kvalitet som svarer til evnene til en bestemt utdanningsinstitusjon, er det nødvendig å utføre din egen diagnose av vanskelighetsgraden og kjedeligheten til fagene i hver parallell. Studentene bør være ekspertene i denne saken, siden ingen kan si bedre enn dem hvilket fag som er vanskelig og kjedelig.

Kriterier for hygienisk vurdering av skoleruta

1. Antall grunnskoleklasser er ______.

2. Antall klasser i grunnskolen og videregående skole er ___________.

3. Totalt antall klasserom brukt til leksjoner – ___________.

4. Tilgjengelighet av en akseptskala for din utdanningsinstitusjon:

5. Ta hensyn til omfanget av emneakseptabelt i skolens læreplan:

6. Fordeling av leksjoner per dag for studenter:

7. Alle klasser begynner studiene med første leksjon:

8. Rasjonell veksling av emner av forskjellige retninger og kompleksitet:

9. Overholdelse av elevprestasjoner i timeplanen (ukentlig dynamikk):

10. Rasjonell tilrettelegging av undervisning for lærere:

11. Maksimalt antall timer per lærer per dag:

a) opptil 4 leksjoner – for____ lærere – ______ (%);

b) 5 og 6 leksjoner - ____ lærere - _____ (%);

c) 7 leksjoner eller mer - ___ lærere - ___ (%).

12. Metodisk dag tilgjengelig (angi antall lærere):

a) med en arbeidsmengde på opptil 24 timer i uken – for____ lærere;

b) med en arbeidsmengde på 25 til 30 timer per uke – for ___ lærere;

c) med en arbeidsmengde på mer enn 30 timer i uken – for___ lærere.

Forbered sett med navn på gjenstander fra 5. til 11. klasse.
Gi elevene sett med emnenavnskort og svarark.
Tilby å velge kort med navnene på de fagene som studeres i denne klassen (ved hjelp av en dagbok).
Tydeliggjør begrepet "vanskelighet" for objekter.
Tilby å uavhengig bestemme vanskelighetsgraden til hvert emne ved rangering, dvs. legge ut kortene i synkende rekkefølge etter emnets vanskelighetsgrad (legg kortene fra topp til bunn, dvs. i første omgang øverst er kortet med det vanskeligste emnet, under er det mindre vanskelig, osv.).
Skriv ned det resulterende arrangementet av elementer på svararket.
Etter dette, analyser og klargjør begrepet "tretthet" av objekter.
Utfør en lignende rangeringsprosedyre og skriv ned den resulterende justeringen på svararket.
Samle inn og behandle svarark (se oppsummeringstabellskjema nedenfor).

– hvor: mk – gjennomsnittlig poengsum i faget i én klasse;

n – antall klasser i parallellen som studeres;

eller med formelen:

– hvor: Mk – summen av poeng i et fag i en klasse;

n – antall studenter fra samme parallell som deltar i studien.

For eksempel, i 7. klasseparallellen er det fem klasser, 130 personer deltok i diagnosen. Summen av poeng i det russiske språket i parallellen var 469. Vi erstatter tallene i formelen:

ons. b. pr. = (469/130) = 3,61 – gjennomsnittlig poengsum i russisk språk i 7. klasse var 3,61, barn oppfatter dette faget som ganske vanskelig.

På samme måte beregnes gjennomsnittlig poengsum for hvert fag i form av trøtthet separat.

Den gjennomsnittlige akseptpoengsummen for hvert fag blir deretter funnet. For å gjøre dette legges to indikatorer sammen: gjennomsnittlig vanskelighetsgrad og gjennomsnittlig kjedelighetspoeng, og deretter deles resultatet på 2. Dette gir den gjennomsnittlige akseptskåren til faget.

Basert på dataene som er innhentet, er det satt sammen en individuell tabell over kvalifikasjoner for fag ved en bestemt utdanningsinstitusjon for hver parallell.

Pivottabellskjema for behandling av svar

Vedlegg 2

Rangering av studietimer i løpet av uken
avhengig av prestasjonsnivået til elevene i ulike klasser

1 - mest gunstige timer; 10 – den mest ugunstige.

6–7 – redusert ytelsesnivå (ugunstige timer for gjennomføring av undervisning).

8–10 – lavt ytelsesnivå (ugunstige timer for gjennomføring av leksjoner).

Lærerens ukentligell

Vedlegg 3

Teknologi for å utføre oppsettet av timeplantabellen

For å fullføre oppsettet må du forberede:

4 ark papp (tykkelse 1–2 mm, høyde – 42 cm, bredde – 22 cm; radhøyde – 0,8 cm, kolonnebredde – 1 cm)*;
4 ark farget papir (helst lyse farger) med en tetthet på 200 g/cm og dimensjoner som ligner på pappark;
bred gjennomsiktig tape;
lederin (papirvinyl) for liming av papp i en mappe (bånd 4–5 cm brede; 49–50 cm lange);
PVA-lim (ganske sterkt, som "silakra").

Algoritme for utførelse av layout

1. Lim pappark til et "muslingskall":

2. Plasser all nødvendig informasjon for å lage en tidsplan på ett ark farget papir (plasser på et ark med papp nr. 1); eksempel: tabell på s. 27.

3. På de neste to arkene med farget papir tegner du et rutenett, tre dager på hvert ark, 7 celler for hver dag (plasser på 2. og 3. pappark).

4. På det fjerde arket tegner du et kontinuerlig rutenett uten å dele opp i dager (cellene har lignende størrelser).

5. Dekk de ferdigforede arkene med tape slik at det ikke er rifter når cellene kuttes.

6. Lag spalter i cellene som varierer i størrelse fra 0,5–0,6 cm.

7. Lim papirarkene langs sidene av papparkene på det ferdige "muslingskallet". Oppsettet er klart.

8. Lag flerfargede tagger separat med klassebokstaven (5. "A", 7. "G", etc.), mengden basert på belastningen på en 5- eller 6-dagers uke + i tillegg for leksjoner der klassene er delt inn i undergrupper. Tagstørrelse: bredde – 8 mm; høyde – 15 mm.

9. Forbered etiketter av hvilken som helst farge uten karakterbokstaver for å beregne den ukentlige arbeidsmengden for hver lærer. Mål: bredde 5 mm; høyde 12–14 mm.

Denne utformingen er praktisk å bruke, siden all nødvendig informasjon alltid er foran nestlederens øyne. Den kan brettes sammen til en mappe, noe som gjør den lett å bære. I dette tilfellet vil taggene holdes i sporene.

Informasjon som trengs for å lage en tidsplan

___________ * Dimensjonene på papparket er individuelle, fordi... Hver skole har ulikt antall lærere, ulik arbeidstid (5- og 6-dagers skoleuke). Vi foreslår timeplanstørrelser basert på en 6-dagers skoleuke og en skole med 50-55 lærere.

Det meste av det du leser her er tull. Likevel, noen steder, etter min mening, er det sunn fornuftstanker; dessverre er det ikke så mange slike steder. L Ikke engang tenk på å ta dette der problemer med planleggingsteori studeres seriøst. For alle som vil skrive noe bedre enn dette, anbefaler jeg på det sterkeste å lese Hus bok. T. "Heltallsprogrammering og flyter i nettverk", i tillegg er det nok verdt å lese forelesningene til VMiK om teorien om optimalisering av N.M. Novikova (jeg husker ikke hvor det er på internett). Nå jobber jeg aktivt med problemer med optimaliseringsteori, så alle som også er interessert i dette emnet er alltid glade for å snakke. Skrive [e-postbeskyttet].

Introduksjon. 8

1. Beskrivelse av det teknologiske området. 10

1.1. Formulering av planleggingsproblemet. 10

1.1.1. Generell formulering av planleggingsproblemet. 10

1.1.2. Formulering av oppgaven med å utarbeide en tidsplan som brukt på timeplanen for treningsøkter. elleve

1.2. Analyse av eksisterende programvare... 12

1.3. Formulering av problemet. 15

2. Utvikling av en matematisk modell og praktisk implementering av et automatisk planleggingssystem. 16

2.1. Matematisk modell av timeplan ved et universitet. 16

2.1.1. Notasjon. 16

2.1.2. Variabler. 18

2.1.3. Begrensninger. 19

2.1.4. Målfunksjon. 21

2.2. Metoder for å løse problemet. 22

2.2.1. Heltallsalgoritme. 23

2.2.2 Direkte heltallsprogrammeringsalgoritme. 28

2.2.3. Teknikk for å oppnå et første akseptabelt grunnlag. 32

2.3. Funksjoner ved den praktiske implementeringen av systemet.. 36

2.3.1. Modellvalg. 36

2.3.2. Beskrivelse av inndatainformasjon. 39

2.3.3. Utvikling av informasjonsstøtte til oppgaven. 41

2.3.4. Funksjoner ved dannelsen av begrensninger i den matematiske modellen av planleggingsproblemet. 44

2.4. Resultater av programmet.. 45

2.5. Analyse av oppnådde resultater. 49

Konklusjoner... 50

Litteratur. 51

Vedlegg 1. Muligheter for programvareprodukter for planleggingssystemer. 52

Vedlegg 2. Liste over programvaremodulen over metoder for å løse problemet med automatisk planlegging. 61

Introduksjon

Kvaliteten på opplæring av spesialister ved universiteter og spesielt effektiviteten av å bruke vitenskapelig og pedagogisk potensial avhenger til en viss grad av organiseringsnivået i utdanningsprosessen.

En av hovedkomponentene i denne prosessen - klasseplanen - regulerer arbeidsrytmen og påvirker lærernes kreative produksjon, derfor kan det betraktes som en faktor for å optimalisere bruken av begrensede arbeidsressurser - lærere. Teknologien for å utvikle en tidsplan bør ikke bare oppfattes som en arbeidskrevende teknisk prosess, et objekt for mekanisering og automatisering ved hjelp av en datamaskin, men også som en handling for optimal ledelse. Dermed er dette problemet med å utvikle optimale timeplaner på universiteter med åpenbare økonomiske fordeler. Siden interessene til deltakerne i utdanningsprosessen er forskjellige, er oppgaven med å lage en tidsplan flere kriterier.

Oppgaven med å lage en timeplan bør ikke bare betraktes som et slags program som implementerer funksjonen til mekanisk fordeling av klasser i begynnelsen av semesteret, hvor bruken av dets (programmets) slutter. Den økonomiske effekten av mer effektiv bruk av arbeidsressursene kan kun oppnås som et resultat av møysommelig arbeid med å forvalte disse arbeidsressursene. Tidsplanen her er bare et verktøy for slik styring, og for dens fulle bruk er det nødvendig at programmet kombinerer ikke bare midler for å lage en optimal tidsplan, men også midler for å opprettholde sin optimalitet i tilfelle endring i enkelte inndata, som på tidspunktet for utarbeidelse av tidsplanen ble ansett som konstante. I tillegg er optimal kontroll av et så komplekst system umulig uten akkumulering av noe statistisk informasjon om prosessene som skjer i systemet. Derfor er selve oppgaven med å lage en optimal tidsplan bare en del av et komplekst pedagogisk prosessstyringssystem.

Multikriterie-naturen til dette problemet og kompleksiteten til objektet som en matematisk modell er bygget for, nødvendiggjør en seriøs matematisk studie av objektet for å øke funksjonaliteten til planleggingsalgoritmer uten å komplisere modellen vesentlig og som en konsekvens øke mengden minne brukt og tiden det tar å løse problemet.

1. BESKRIVELSE AV DET TEKNOLOGISKE OMRÅDET 1.1. Formulering av planleggingsproblemet

Problemet med planleggingsteori i dens generelle formulering anses som svært attraktivt, selv om det å oppnå selv små fremskritt mot en løsning vanligvis er forbundet med enorme vanskeligheter. Til tross for at mange høyt kvalifiserte spesialister har behandlet problemene med planleggingsteori, har ingen så langt vært i stand til å oppnå signifikante resultater. Mislykkede forsøk på å oppnå slike resultater publiseres som regel ikke, og dette skyldes delvis det faktum at problemet fortsetter å tiltrekke seg oppmerksomheten til mange forskere på grunn av dets tilsynelatende enkle formulering.

1.1.1. Generell formulering av planleggingsproblemet

I sin mest generelle formulering er planleggingsoppgaven som følger. Ved hjelp av et visst sett med ressurser eller serveringsenheter må et visst fast system av oppgaver utføres. Målet er å finne en effektiv algoritme for å bestille oppgaver som optimerer eller har en tendens til å optimalisere det nødvendige effektivitetsmålet, gitt egenskapene til oppgaver og ressurser og restriksjonene som er pålagt dem. Hovedmålene for effektivitet er lengden på tidsplanen og gjennomsnittlig oppholdstid for jobber i systemet. Modellene for disse problemene er deterministiske i den forstand at all informasjon som ligger til grunn for bestillingsbeslutninger er kjent på forhånd.

1.1.2. Formulering av oppgaven med å utarbeide en tidsplan som brukt på timeplanen for treningsøkter.

Den generelle teorien om planlegging antar at alle serveringsenheter (eller prosessorer) ikke kan utføre mer enn én oppgave på et gitt tidspunkt, noe som ikke er tilstrekkelig for å planlegge undervisningstimer hvis klasserommet tas som en prosessor når oppgaver distribueres. Så i noen tilfeller kan klasser med mer enn én gruppe samtidig holdes i ett klasserom, for eksempel generelle forelesninger for flere bekker.

Derfor, når du overfører den generelle teorien om tidsplaner til treningsplanen, ble følgende forutsetninger gjort:

Alle prosessorer (dvs. i tilfelle av en pedagogisk timeplan - et klasserom) har en kapasitet - et visst antall C ≥ 1. Kapasiteten til en prosessor bestemmer antall oppgaver som den kan "behandle" samtidig på et gitt tidspunkt (med med tanke på ikke-enheten av prosessorer, ville det være interessant å vurdere alternativet , når prosessoren ikke er publikum, men læreren, og oppgaven er en strøm fra en eller flere utdanningsgrupper han jobber med);

Oppgavesettet for distribusjon inkluderer lærerens opplæringsøkter med studiegrupper;

Tidsmodellen i systemet er diskret; hele fordelingen antas å gjenta seg periodisk over et visst tidsintervall;

Alle oppgaver fullføres på samme tid, som tas som en enhet for diskretisering av tidsintervallet;

Oppgaver tilhører objekter, som er studiegrupper og lærere.

Som et resultat er formuleringen av problemet med å planlegge treningsøkter som følger: "For et gitt sett med klasserom (i dette tilfellet betyr et klasserom et bredt spekter av rom der treningsøkter holdes (fra et datarom til et gym)) og et gitt sett med tidsintervaller (dvs. i hovedsak leksjoner eller treningspar) for å konstruere en slik fordeling av treningsøkter for alle objekter (lærere og treningsgrupper) der det valgte optimalitetskriteriet er det beste."

1.2. Analyse av eksisterende programvare

På dette tidspunktet er programvaremarkedssektoren for klasseplanleggingssystemer representert av et stort antall forskjellige programvareprodukter. Tabell 1 viser bare noen få av de jeg kjenner til.

Av objektive grunner må planleggingssystemet ved et universitet (som betyr et stort statlig universitet) nødvendigvis implementere en rekke grunnleggende funksjoner:

Tar hensyn til lærernes ønsker;

Sikre nødvendige målgrupper;

Spesifisere ønskede målgrupper;

Regnskap for overgangen mellom bygninger;

Kombinere grupper til strømmer for ethvert sett med disipliner;

Inndeling i undergrupper;

Etter å ha utarbeidet timeplanen, bytt eventuelt ut lærere eller endre tidspunktet for timen.

I tillegg er det også spesifikke krav til hvert universitet for funksjonaliteten til programvareproduktet.

Mulighetene til, etter min mening, de mest populære programvareproduktene på det russiske markedet er gitt i vedlegg 1.

Fra listen ovenfor er det kanskje bare "Methodist"-programmet som mer eller mindre tilsvarer den nødvendige funksjonaliteten til et programvareprodukt for planlegging ved et universitet. Denne tilstanden kan lett forklares med det faktum at skoleutdanning i dag er mer "standardisert" (i betydningen å organisere utdanningsprosessen) enn universitetsutdanning. Denne standardiseringen fører til et stort potensielt marked for programvaresalg og tilbakebetaling av utvikling ved å selge et stort antall eksemplarer av produktet til en relativt lav pris.

Når det gjelder universiteter, er etterspørselen etter planleggingssystemer kanskje enda større enn for skoler, men saken kompliseres av den store spesifisiteten i organiseringen av utdanningsprosessen ved hvert enkelt universitet. Det er ikke mulig å lage enhetlig programvare, og kostnadene ved å lage et spesialisert produkt fra tredjepartsutviklere viser seg å være urimelig høy. I tillegg er en forutsetning tilstedeværelsen av en "avgjort" timeplan, som forutsetter muligheten for å erstatte lærere eller endre tidspunktet for undervisningen. Så langt er det ingen programvareprodukter som lar deg gjøre dette ganske enkelt (selv om Methodist har noen muligheter).

1.3. Formulering av problemet.

Hensikten med dette arbeidet var å lage en matematisk modell av en universitetsplan som ville tillate en effektivt (innen en gitt tidsramme og med en gitt grad av optimalitet) å løse problemet med automatisk planlegging og ville ha fleksibiliteten (mindre endringer i ved endringer i inputinformasjon) for å tilpasse systemet innenfor et spesifikt praktisk problem. For å forenkle oppgaven noe, ble det gjort noen forutsetninger i det innledende designstadiet:

Timeplanen er basert på ikke mer enn to par per dag (som er ganske egnet for kveldstimer);

Alle par holdes i en bygning;

Problemet er stilt i form av lineær programmering;

Ingen ytterligere dekomponering av modellen utføres;

Alle modellkoeffisienter og ønskede variabler er heltall;

Problemet som stilles må løses med en av de universelle (uavhengig av heltallsverdiene til koeffisientene) metodene for heltalls lineær programmering.

2. Utvikling av en matematisk modell og praktisk implementering av et automatisk planleggingssystem 2.1. Matematisk modell for universitetsplanlegging

La oss bygge en matematisk modell av en universitetsplan når det gjelder lineær programmering. La oss introdusere notasjon og definere variabler og begrensninger.

2.1.1. Betegnelser

Universitetet har N studiegrupper, kombinert til R-strømmer; r – strømnummer, r = 1, ..., R, k r – studiegruppenummer i strøm r, k r = 1, ..., G r.

Inndelingen i grupper i tråder utføres basert på prinsippene:

1. Bruk av to grupper av samme klasseromsfond for deres forelesninger innebærer automatisk å plassere dem i 1 strøm (det forutsettes at alle forelesninger i studiegruppene holdes samlet).

2. En gruppe (eller en del av den), som en enhet i utdanningsprosessen ved et universitet, kan inkluderes i forskjellige strømmer, men bare én gang i hver av dem.

3. Antall tråder er ikke begrenset.

Klassene holdes på hverdager med halvannen times intervaller, som vi vil kalle par.

La oss betegne:

t – nummer på arbeidsdagen i uken, t Є T kr, hvor

T kr – sett med arbeidsdagstall for gruppe k r;

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

J – totalt antall par.

Med hver studiegruppe k r stream r i løpet av uken gjennomføres det i henhold til læreplanen W kr klasser, hvorav S r forelesninger og Q kr praktiske. La oss betegne:

s r – antall disipliner i listen over forelesningsklasser for strøm r, s r = 1 ,...,S r ;

q kr – disiplinnummer i listen over praktiske timer for gruppe k r, q kr = 1,..., Q kr.

Det forutsettes at det holdes forelesninger for alle grupper i strømmen samtidig og i samme klasserom. Deretter, hvis mer enn én leksjon undervises i en disiplin i løpet av en uke, er denne disiplinen nevnt i listen over forelesninger eller praktiske klasser så mange ganger som de er gitt i pensum for hver strøm eller gruppe.

LÆRERE

La p være tallet (navnet) til læreren, p = 1 ,..., P. La oss introdusere de boolske verdiene og :

Undervisningsbelastningen til lærere planlegges før timeplanen utarbeides, som et resultat av at verdiene på dette stadiet kan anses som gitte. For hver lærer p, p = 1 ,...,P er hans klasseromsbelastning også spesifisert - N p timer per uke.

REVISJONSFOND

Klasser i hver strøm kan bare holdes i visse klasserom (for eksempel kan praktiske klasser i informatikk bare holdes i visningsklasser). La være:

(A 1 r ) – sett med publikum for forelesninger på stream r;

(A 2 r) – sett med klasserom for praktisk opplæring på strøm r;

A 1 r – antall elementer i settet (A 1 r);

A 2 r – antall elementer i settet (A 2 r);

A 1 r + A 2 r – antall publikummere i foreningen av sett (A 1 r )∩(A 2 r ).

Publikumsfondet bestemmes før planleggingen starter, så settene kan anses gitt.

2.1.2. Variabler

Oppgaven med å planlegge er å bestemme for hver forelesning (på strømmen) og praktisk leksjon (i gruppen) ukedagen og paret på denne dagen, under hensyntagen til oppfyllelsen av begrensningene som er konstruert nedenfor og minimering av en en viss objektiv funksjon.

La oss introdusere følgende nødvendige boolske variabler:

Ved opplegg for grupper av kveldstimer, J=2. For en generalisering av modellen til alle former for læring, se side 669.

2.1.3. Begrensninger

For hver gruppe k r må alle typer klasseromsarbeid gjennomføres i løpet av uken:

Hver forelesning s r og praktisk leksjon q kr, henholdsvis for alle strømmer r og alle grupper k r kan ikke holdes mer enn én gang på en dag t:

Hvis variablene kobler alle typer aktiviteter med tidspunktet for implementeringen, så er produktene og assosier tiden med navnet på læreren.

På hver dag t og i hvert par j kan lærer p ikke undervise mer enn én leksjon i én disiplin i én strøm eller i én gruppe:

Til slutt, på hver dag i hver klasse, bør antallet forelesninger og praktiske klasser ikke overstige klasseromsfondet som er tilgjengelig ved universitetet:

I tillegg, for alle sett med kryssende sett (A 1 r) og (A 2 r) må følgende betingelser være oppfylt:

De presenterte relasjonene uttømmer de ubetingede restriksjonene som alltid tas i betraktning når man utarbeider en tidsplan. Det kan imidlertid være spesifikke forhold, først og fremst, å utføre visse typer arbeid i "øvre" eller "nedre" uke (dvs. én akademisk time per uke). Andre spesielle forhold kan ikke utelukkes, men for å forenkle modellen ble de ikke vurdert.

2.1.4. Objektiv funksjon

For å fullføre vitenskapelig, pedagogisk og metodisk arbeid, og forberede seg til undervisning, må en universitetslærer ha fritid. Denne betingelsen er ikke tilstrekkelig, men nødvendig. Det er klart at han ikke skal ha fritid i en "fillete" modus, som for eksempel "vinduer" mellom klasser med studenter, men om mulig på helt frie arbeidsdager. Dette tilsvarer å maksimere lærernes arbeidsmengde i klasserommet de dagene de har det (se (5)). Men samtidig har lærere ulikt krav på fritid, siden de har ulikt kreativt potensial. Derfor er det nødvendig å innføre vektingskoeffisienter som den tilsvarende statusen til læreren skal tas i betraktning - hans akademiske grader og tittel, stilling, vitenskapelig og sosial aktivitet, etc. I noen tilfeller er det ut fra sakkyndige vurderinger mulig å bruke individuelle vektkoeffisienter som tar hensyn til andre forhold.

Så vi vil velge et kriterium for kvaliteten på timeplanlegging i form av å maksimere det vektede antallet dager fri fra klasseromsarbeid for alle lærere, som, gitt en fast lengde på arbeidsuken, tilsvarer den maksimale totale komprimeringen av klasseromsbelastningen.

La oss vurdere uttrykket for verdien av klasseromsbelastningen på dag t til lærer p:

hvor M er et vilkårlig positivt tilstrekkelig stort tall; - ønsket boolsk variabel.

Fra (10) følger det at hvis , så = 1, og hvis , så = 0.

Ved å ta i betraktning ovennevnte materielle betydning av optimaliseringskriteriet i tilleggsbegrensninger (10), samt introdusere vektingskoeffisienter for lærerstatus, oppnår vi det nødvendige optimalitetskriteriet:

Den introduserte objektivfunksjonen er ikke den eneste mulige. Innføringen av andre objektive funksjoner endrer ikke begrensningene til den matematiske modellen og metoder for å løse problemet, men kan i betydelig grad påvirke resultatene av beregninger.

2.2. METODER FOR Å LØSE PROBLEMET

Problemet med å maksimere en lineær objektivfunksjon som ble stilt i forrige avsnitt under et gitt system av begrensninger er et lineært heltalls boolsk programmeringsproblem, siden alle begrensningskoeffisienter er heltall på grunn av den diskrete naturen til de innledende dataene til problemet; I tillegg kan de nødvendige variablene i den matematiske modellen bare ha to verdier. På dette tidspunktet er det flere mulige metoder for å løse denne typen problemer.

B – metoder for ordnet indeksering og modifiserte markeringer er beskrevet, basert på den lagrangiske dekomponeringen av den originale modellen til en rekke problemer med én linje løst, henholdsvis ved hjelp av metodene for å bestille indeksering eller modifiserte markeringer. Dessverre tillater ikke antall operasjoner for hver metode et polynomestimat; I tillegg øker dimensjonen til tabellen over sett (mellomverdier) av metoder kraftig med økende dimensjon av problemet som løses, noe som er uakseptabelt i vårt tilfelle. Kanskje vil endring av dekomponeringsalgoritmen for en spesifikk matematisk modell redusere størrelsen på tabellene, men en slik algoritme eksisterer ikke ennå.

I denne forbindelse ble løsningsmetodene beskrevet i modifikasjonen av simpleksmetoden for tilfellet med et heltalls lineært programmeringsproblem valgt. I det generelle tilfellet tillater ikke antall operasjoner av simpleksmetoden et polynomestimat (det ble til og med vist en klasse med problemer der antallet operasjoner er O(e n)), men for vårt problem, gjennomsnittlig antall operasjoner tillater et polynomestimat: O(n 3 m 1/( n-1)) (n – antall variabler; m – antall restriksjoner).

2.2.1. FULL HELLALGORITME

Denne algoritmen kalles fullstendig heltall fordi hvis den opprinnelige tabellen består av heltallselementer, så inneholder alle tabellene som kommer fra algoritmen bare heltallselementer. I likhet med dual simplex-metoden, starter algoritmen fra en dobbelt tillatt tabell. Hvis a i 0 (i = 1 ,..., n+m; a i 0 er koeffisientene til objektivfunksjonen) er ikke-negative heltall, så er problemet løst. Hvis for en streng a i 0

La et heltalls lineært programmeringsproblem gis:

maksimere

under forhold

Betingelser (12) kan skrives som

Anta at for t=0 (dvs. for den opprinnelige tabellen) er all a ij heltall og kolonner (j = 1 ,..., n) er leksikografisk positive. Da forblir alle kolonnene leksikografisk positive gjennom hele beregningene.

Før vi presenterer en metode for å få en ekstra begrensning fra genereringsstrengen, introduserer vi en ny representasjon av tall. La [x] betegne det største heltall som ikke er større enn x. For et hvilket som helst tall y (positivt eller negativt) og positivt, kan vi skrive:

hvor (r y er en ikke-negativ rest ved å dele y med ). Spesielt, . Derfor, hvis , så er r = 1. Hvis , så er r = 0.

Den innførte ekstra ulikheten må tilfredsstilles for enhver heltallsløsning av problem (12). Tenk på en ligning i t-tabellen (som utelater radindeksen) med en 0

hvor x er den tilsvarende komponenten av vektoren, og er de gjeldende ikke-grunnleggende variablene. Vi kan uttrykke x, a 0 og a j ved å bruke representasjonen (14) introdusert ovenfor:

Ved å erstatte uttrykk (16) og (17) med (15) og omorganisere begrepene, får vi:

Siden , og variablene x og er underlagt kravet om ikke-negativitet, er venstre side av ligning (18) alltid ikke-negativ. Tenk på uttrykket på høyre side, omsluttet av krøllete seler. Koeffisientene i dette uttrykket er heltall, og variablene er underlagt heltallskravet. Derfor må hele uttrykket i parentes være et heltall. La oss betegne det med s, dvs.:

Den heltallssvake variabelen s er ikke-negativ. Faktisk, hvis s var negativ, dvs. ville ta verdiene -1, -2, ..., og deretter multiplisere med ville gjøre hele høyre side av ligning (18) negativ, mens venstre side er ikke-negativ.

La oss vurdere to tilfeller og . For og . Ved å erstatte uttrykket for x fra (15) i ligning (19), får vi:

Ligning (21) må være oppfylt for enhver heltallsløsning på oppgave (12). Merk at hvis en 0 i ligning (21). Derfor kan ligning (21) brukes som en ledende linje i simpleksmetoden. Spesielt kan du alltid velge stort nok slik at det ledende elementet i rad (21) blir lik –1, noe som vil bevare integeriteten til tabellen. Valget av passende vil påvirke hastigheten på konvergensen til algoritmen. Først av alt, la oss beskrive selve algoritmen. Som en innledende løsning er det nødvendig å ta en dobbelt gjennomførbar løsning, som kan oppnås ved å legge til begrensningen x n + m+1 =M – x 1 - - … - x n 0, der M er en tilstrekkelig stor konstant, og bærer ut én iterasjon med den tilføyde raden og med den leksikografisk minimale kolonnen, tatt som ledere. Algoritmen består av følgende trinn:

Trinn 0. Start med en dobbelt tillatt matrise A 0 i ligning (13), hvis elementer er heltall (matrisen A 0 kan også inneholde ikke-heltallselementer, se om dette, side 306).

Trinn 1. Blant radene med a i 0 0 (i=1, ..., n+m), så er problemet løst.)

Trinn 2. Velg (seleksjonsregelen vil bli beskrevet senere) og skriv en ekstra linje nederst i tabellen

Denne linjen er valgt som ledende linje.

Trinn 3. Utfør dual simplex-metoden, kryss ut tilleggslinjen og gå tilbake til trinn 1.

For bevis på algoritmens endelighet, se s. 303-304.

Utvelgelsesregelen er formulert som følger.

Trinn 0. La raden med nummer v generere.

Trinn 1. La være den leksikografisk minimale kolonnen blant kolonnene med en vj

Trinn 2. For hver a vj er det største heltall slik at (leksikografisk mindre).

Trinn 3. La , a (rad v genererer). Deretter

Trinn 4. Sett for en vj

Utvelgelsesregelen beskrevet ovenfor lar deg gjøre det ledende elementet lik -1, mens du opprettholder den doble gyldigheten til tabellen og samtidig vil nullkolonnen reduseres leksikografisk så mye som mulig.

2.2.2 Direkte heltallsprogrammeringsalgoritme

Begrepet "direkte" når det brukes på en heltallsprogrammeringsalgoritme, refererer til en metode som fører til en optimal løsning ved å oppnå suksessive "forbedre" løsninger. Hver av disse løsningene er gyldige i den forstand at den tilfredsstiller både de lineære begrensningene og heltallsbetingelsen. En av de sannsynlige fordelene med algoritmen er muligheten til å avbryte beregningene før den optimale løsningen er oppnådd og bruke den beste løsningen som er oppnådd som en omtrentlig løsning. I tillegg kan den direkte algoritmen brukes sammen med doble algoritmer for å produsere ulike sammensatte algoritmer som kan bevege seg fra en fase som produserer dobbelt gjennomførbare løsninger til en fase som produserer direkte gjennomførbare løsninger.

En naturlig presedens for den direkte algoritmen er Gomori-algoritmen med heltall, siden prosessen med denne algoritmen produserer en sekvens av dobbelt gjennomførbare heltallsløsninger. Det skal huskes at Gomori-algoritmen med heltall er en modifikasjon av dual simplex-metoden. Hovedforskjellen med denne algoritmen er at den ledende strengen er et Gomori-snitt med et ledende element på -1. Dette kuttet er hentet fra genereringsstrengen, som er definert som en av de mulige ledende strengene i dual simplex-metoden. Å bruke et slikt kutt som en ledende rad vil bevare den doble gyldigheten og integriteten til tabellen etter iterasjon.

Det viser seg at du på samme måte kan modifisere simpleksmetoden på en slik måte at du oppnår en algoritme som bevarer direkte tillatelighet og integeritet til tabeller. For å beskrive beregningsprosedyren, vurder følgende heltallsprogrammeringsproblem:

maksimere

Anta at kolonnen er valgt som den ledende og raden v er den ledende raden i iterasjonen av simpleksmetoden, dvs. for alle rader I der a er >0. Før vi utfører den Gaussiske elimineringsprosedyren i simpleksmetoden, legger vi til Gomori-avskjæringen fra raden v til tabellen:

hvor J er settet med indekser av ikke-grunnleggende variabler i (22), er s k en ny (grunnleggende) svak variabel og er en ubestemt (midlertidig) positiv konstant.

Merk at hvis vi setter = a vs, vil cutoff (23) ha to viktige egenskaper. For det første,

Dette betyr at den direkte gyldigheten til tabellen bevares hvis vi bruker cutoff (23) som ledende rad. For det andre, dvs. ledende element er 1 (hvis klipp brukes som ledende streng). Det er lett å verifisere (ved å undersøke formlene for å endre de grunnleggende variablene) at transformasjonen av en simplekstabell med et enkelt ledende element bevarer integeriteten til elementene i simplekstabellen.

Disse ideene fungerte som grunnlaget for den direkte algoritmen i heltallsprogrammering:

Trinn 0. Start med en kolonnetabell der a i 0 0 (i 1) og alle elementene a 0 j , a ij og a i 0 er heltall.

Trinn 1. Sjekk at betingelsene a 0 j 0 (j 1); hvis de er fornøyde, så er slutten, den nåværende grunnleggende løsningen optimal; hvis ikke, gå til trinn 2.

Trinn 2. Velg ledende kolonne s med 0 s 0. Denne raden fungerer som generator for Gomori-kuttet.

Trinn 3. Skaff Gomori-kuttet fra genereringslinjen og legg det til nederst i tabellen, dvs. legg til ligning (23) til problembegrensningene, der .

Trinn 4. Konverter tabellen ved å bruke kutt (23) som ledende rad. Den svake variabelen s k in (23) vil bli ikke-grunnleggende. Gå tilbake til trinn 1.

For bevis på algoritmens endelighet, se s. 346-353.

Siden valg av en genererende streng ikke er en triviell oppgave, ser det ut til at det må være flere strenger som kan tjene som genererende strenger. I de foreløpige argumentene ble den ledende linjen i simpleksmetoden brukt som genereringslinje. Denne linjen produserer alltid en cutoff som er den ledende linjen med et ledende element lik én. Tilsynelatende er det andre rader i tabellen hvorfra kutt med samme egenskaper kan oppnås. La oss anta at cutoff oppnås i henhold til formelen:

hvor bestemmes ut fra tilstanden

La oss definere settet V(er) som en samling av rader som tilfredsstiller betingelsen (25).

Følgende to regler er eksempler på gyldige genereringsregler for strengvalg:

Regel 1.

1. Lag en sekvensiell endelig liste over radindekser slik at indeksen til hver rad vises i den minst én gang. Gå til 2.

2. Hvis listen er tom eller ikke inneholder noen indeks fra V(er), gå tilbake til 1.; Ellers finner du den første indeksen v V(s) i listen. Velg rad v som produserende. Utdataindeks v og alle foregående indekser fra listen. Gå til 3.

3. Velg konsekvent strengen v tatt i 2. som genererende til v V(s). Når v V(s), gå tilbake til 2.

Regel 2.

1. La V t (s) være mengden V(s) som tilsvarer den t-te tabellen. Hvis V t (s) inneholder mer enn ett element: V t (s) = (v 1, v 2, ..., v k +2), så velg som en generator en rad slik at i rekkefølgen av settene V 1 (s 1), V 2 (s 2), ..., V t (s) linjen dukket opp tidligere (ikke senere) enn de andre og ble deretter værende til V t (s); gå til 2.

2. Velg strengen v tatt i 1. til . En gang, gå tilbake til 1.

2.2.3. TEKNIKK FOR Å FÅ DET INNLEDENDE TILLATTE GRUNNLAGSET

Hver av metodene ovenfor kan bare løses hvis det lineære programmeringsproblemet er enten direkte eller dobbelt gjennomførbart. Slik tillatelse betyr tilstedeværelsen av et innledende akseptabelt grunnlag i den opprinnelige problemstillingen. Hvis problemet er gjennomførbart både direkte og dobbelt, så er den resulterende løsningen optimal. I de fleste tilfeller, etter å ha stilt et problem, viser det seg at det ikke er tillatt verken direkte eller dobbelt. Derfor presenterer vi en algoritme for å oppnå et innledende akseptabelt grunnlag.

La det lineære programmeringsproblemet skrives i kanonisk form:

minimere

under forhold

Alle b i kan gjøres ikke-negative ved å multiplisere, om nødvendig, den tilsvarende ligningen med –1. Deretter kan du legge til en kunstig variabel til hver ligning (de kunstige variablene må være ikke-negative) på en slik måte at de danner en initial basis fra de kunstige variablene:

Kunstige variabler kan utledes fra svake variabler som brukes til å gjøre ulikheter om til ligninger. Faktisk, hvis de første begrensningene for et lineært programmeringsproblem er gitt i form av ulikheter:

så, ved å legge til en svak variabel til hver ulikhet, får vi:

Hvis b i 0, kan s i brukes som initiale grunnvariabler.

Forskjellen mellom kunstige variabler og svake variable s i er som følger. I den optimale løsningen på problemet må alle kunstige variabler være lik null, siden det ikke finnes slike variabler i den opprinnelige oppgaven. På den annen side er det godt mulig at i den optimale løsningen vil de svake variablene ha positive verdier. For at de kunstige variablene skal bli null, kan objektivfunksjonen representeres som følger:

hvor M i er tilstrekkelig store positive tall. Ideen med metoden tilsvarer det faktum at kunstige variabler gis åpenbart høye priser. Denne metoden fører til nullverdier av kunstige variabler i den optimale løsningen.

Det er en annen måte å oppnå det opprinnelige akseptable grunnlaget. I denne metoden, som i den første, brukes kunstige variabler som initiale grunnleggende variabler. En ny objektiv funksjon vurderes, som er summen av kunstige variabler. Det er nødvendig å minimere bruken av z-ligningen som en av begrensningene. Hvis det opprinnelige ligningssystemet har en gjennomførbar løsning, må alle kunstige variabler bli lik null. Derfor må minimumsverdien bli null. Hvis , har det opprinnelige ligningssystemet ingen tillatte løsninger. Hvis , så kan vi utelate objektivfunksjonen og bruke den optimale basisformen som det innledende gjennomførbare grunnlaget for å minimere z. I litteraturen kalles denne metoden tofase simpleksmetoden. I den første fasen av metoden finner man et tillatt grunnlag ved å minimere , i den andre minimeres z og man får et optimalt grunnlag.

Tenk på følgende lineære programmeringsproblem som et eksempel:

minimere

under forhold

hvor alle b i er ikke-negative.

Hvis vi introduserer kunstige variabler og en ny objektiv funksjon, får vi følgende problem:

minimere

under forhold

Hvis vi subtraherer alle ligninger som inneholder b i fra -formen, får vi:

-z

hvor System (26) er diagonalt i forhold til Den første fasen av simpleksmetoden består av minimering under forhold (26). Det er ingen begrensninger på tegnet z. I prosessen med beregninger, så snart en kunstig variabel blir ikke-grunnleggende og koeffisienten i -form er positiv, ekskluderes selve variabelen og den tilsvarende kolonnevektoren fra videre beregninger.

2.3. FUNKSJONER I DEN PRAKTISKE IMPLEMENTERINGEN AV SYSTEMET

I praksis er det lite hensiktsmessig å jobbe med informasjon i den formen den er definert i en matematisk modell. La oss derfor først og fremst bestemme oss for en måte å organisere data eller en datamodell på.

2.3.1. MODELLVALG

En datamodell er et sett med avtaler om metoder og midler for å formalisere beskrivelsen av objekter og deres relasjoner knyttet til automatisering av systemprosesser. Typen modell og typene datastrukturer som brukes i den, reflekterer konseptet med å organisere og behandle data som brukes i DBMS som støtter modellen, eller i programmeringssystemspråket som databer opprettet i.

For å løse dette problemet er det nødvendig å lage en datamodell der mengden tilleggsinformasjon vil være minimal, det vil være en grunnleggende mulighet for flerbrukertilgang til data, og et høyt databeskyttelsesnivå vil bli sikret.

For tiden er det tre hovedtilnærminger for å danne en datamodell: hierarkisk, nettverk og relasjonell.

HIERARKISK ORGANISERINGSMETODE

En hierarkisk database består av et ordnet sett med trær; mer presist, fra et ordnet sett med flere forekomster av samme type tre. En tretype består av én "rot"-posttype og et ordnet sett med null eller flere undertretyper (som hver er en tretype). En tretype generelt er en hierarkisk organisert samling av posttyper.

Integriteten til koblinger mellom forfedre og etterkommere opprettholdes automatisk. Grunnregel: intet barn kan eksistere uten sin forelder. Merk at lignende vedlikehold av referanseintegritet mellom poster som ikke er en del av det samme hierarkiet ikke støttes.

NETTVERKSMETODE FOR ORGANISERING

Nettverkstilnærmingen til dataorganisering er en forlengelse av den hierarkiske. I hierarkiske strukturer må en underordnet post ha nøyaktig én stamfar; i en nettverksdatastruktur kan et barn ha et hvilket som helst antall forfedre.

En nettverksdatabase består av et sett med poster og et sett med forbindelser mellom disse postene, og mer presist, et sett med forekomster av hver type fra et sett med posttyper spesifisert i databaseskjemaet og et sett med forekomster av hver type fra en gitt sett med tilkoblingstyper.

Relasjonstypen er definert for to typer poster: stamfar og etterkommer. En relasjonstypeforekomst består av én forekomst av en stamfarposttype og et ordnet sett med forekomster av en underordnet posttype. For en gitt koblingstype L med en stamdataposttype P og en underordnet posttype C må følgende to betingelser være oppfylt:

1. Hver forekomst av type P er en stamfar til bare én forekomst av L;

2. Hver forekomst av C er et barn av maksimalt én forekomst av L.

RELASJONELL MÅTE Å ORGANISERE

De viktigste ulempene med hierarkiske og nettverkstyper av datamodeller er:

1. For vanskelig å bruke;

2. Kunnskap om fysisk organisering er faktisk nødvendig;

3. Applikasjonssystemer avhenger av denne organisasjonen;

4. Logikken deres er overbelastet med detaljer om organisering av tilgang til databasen.

Den vanligste tolkningen av den relasjonelle datamodellen ser ut til å være den til Data, som gjengir den (med forskjellige forbedringer) i nesten alle bøkene hans. I følge Date består relasjonsmodellen av tre deler som beskriver ulike aspekter ved den relasjonelle tilnærmingen: den strukturelle delen, manipulasjonsdelen og den helhetlige delen.

Den strukturelle delen av modellen sier at den eneste datastrukturen som brukes i relasjonsdatabaser er den normaliserte n-ære relasjonen.

Manipulasjonsdelen av modellen bekrefter to grunnleggende mekanismer for å manipulere relasjonsdatabaser - relasjonsalgebra og relasjonskalkulus. Den første mekanismen er hovedsakelig basert på klassisk settteori (med noen forbedringer), og den andre er basert på det klassiske logiske apparatet til førsteordens predikatregning. Hovedfunksjonen til manipulasjonsdelen av relasjonsmodellen er å gi et mål på relasjonaliteten til ethvert spesifikt relasjonsdatabasespråk: et språk kalles relasjonelt hvis det ikke er mindre uttrykksfullt og kraftig enn relasjonsalgebra eller relasjonskalkulus.

Til slutt fikser den integrerte delen av relasjonsdatamodellen to grunnleggende integritetskrav som må støttes i enhver relasjonell DBMS. Det første kravet kalles enhetsintegritetskravet. Det andre kravet kalles det referansemessige integritetskravet.

Etter en foreløpig analyse av den matematiske modellen av systemet og metodene for å organisere data, samt programvare tilgjengelig på markedet (hierarkiske og nettverksmetoder for organisering antyder en objektorientert tilnærming til organisering av data, og i dag er det slike DBMS-er (for for eksempel Jasmin eller Informix Dynamic Server), men på På utviklingstidspunktet var det ingen mulighet for å bruke dem, samtidig er det veldig "kraftige" relasjonelle DBMS-er (for eksempel Oracle 8i)) valget ble tatt til fordel for den relasjonelle metoden for å organisere datalagring.

2.3.2. BESKRIVELSE AV INNGANGSINFORMASJON

All informasjon som er nødvendig for å løse problemet, spesifiseres før start av iterasjoner av metoder for å løse planleggingsproblemet. For enkelhets skyld antas det at den angitte informasjonen er konstant i hele perioden det utarbeides tidsplan.

Uten å miste en viss grad av generalitet av oppgaven, er det mulig å bestemme et visst sett med inngangsdata som er nødvendige for dannelsen av begrensninger og løsning av problemet, og samtidig felles for alle varianter av praktiske implementeringer av systemet. På grunn av oppgavens spesifikasjoner (muligheten for relativt enkel tilpasning av den matematiske modellen for praktisk implementering innen et bestemt universitet), ble det ikke utviklet former for informasjonsdokumenter. Detaljer om inndatainformasjonen er beskrevet i tabell 2.

Tabell 2. Beskrivelse av informasjon om inndata

Navn på detaljer

Kjennetegn på detaljer

inndatadokumenter

Type

Maks. lengde

Nøyaktighet

Etternavn, fornavn, patronym for læreren;

Lærerens kontakttelefonnummer;

Akademisk grad;

Akademisk tittel;

Gruppenavn;

Antall medlemmer av gruppen;

Tittel på emnet som undervises;

Antall klasseromstimer;

Publikumstall;

Publikumsinformasjon;

Navnet på faget læreren underviser;

Nummer på gruppen der emnet leses;

Informasjon om publikum der emnet leses.

I tillegg til disse dataene krever den matematiske modellen tilstedeværelsen av noen tilleggsdata, som kan oppnås etter å ha analysert inndatainformasjonen programmatisk.

2.3.3. UTVIKLING AV INFORMASJONSSTØTTE TIL OPPGAVEN

Vi vil analysere kildeinformasjonen for å bestemme sammensetningen og strukturen av informasjon for påfølgende formalisering og konstruksjon av en informasjons- og logisk datamodell (ILM). Den matematiske modellen ovenfor, samt tilleggsinformasjon fra beskrivelsen av fagområdet, lar oss bestemme rollen til detaljer i den sammenhengende informasjonen i dokumentet. Basert på denne analysen vil vi etablere de funksjonelle avhengighetene til detaljene i henhold til anbefalingene og kravene til datanormalisering, hvoretter vi vil gjennomføre selve normaliseringen. Formålet med normalisering er å redusere (men ikke nødvendigvis eliminere) dataredundans. Noen ganger opprettes imidlertid noe dataredundans med vilje for å forbedre programmets effektivitet. La oss definere tre former for databasenormalisering.

En tabell er i første normalform (1NF) hvis den har en primærnøkkel, alle attributter er enkle datatyper, og det er ingen dupliserte attributter. For å overholde 1NF, må attributtdomener være atomverdier og det må ikke være noen dupliserte attributtgrupper. Alle dupliserte attributtgrupper må flyttes til den nye tabellen.

En tabell er i andre normalform (2NF) når den er i første normalform og hvert ikke-nøkkelattributt er fullt funksjonelt avhengig av primærnøkkelen (dvs. i 2NF må hvert ikke-nøkkelattributt være helt avhengig av feltene til primærnøkkelen nøkkel).

En tabell er i tredje normal form (3NF) hvis den er i 2NF og har ingen transitive avhengigheter. Transitive avhengigheter er funksjonelle avhengigheter mellom ikke-nøkkelattributter. Ethvert ikke-nøkkelattributt som er funksjonelt avhengig av et annet ikke-nøkkelattributt i samme tabell, skaper en transitiv avhengighet og må flyttes til en annen tabell.

De resulterende funksjonelle avhengighetene er ganske trivielle og følger åpenbart av den matematiske modellen, så de er ikke gitt i den videre beskrivelsen. I den følgende presentasjonen er også mellomliggende grader av normalisering utelatt. Derfor presenterer vi bare den endelige infologiske modellen av databasen (se fig. 1.).

Figur 1. Infologisk modell av databasen for oppgaven med å planlegge klasser

2.3.4. FUNKSJONER AV FORMASJONSBEGRENSNINGER I DEN MATEMATISKA MODELLEN FOR TIDSPLANPROBLEMET

Å tegne begrensninger (1) – (7) for den matematiske modellen for planleggingsproblemet er en ganske triviell oppgave som kan løses ved hjelp av enkle SQL-spørringer og krever ikke foreløpig analyse av inndatainformasjonen. Derfor vil vi kun dvele mer detaljert ved begrensninger av skjemaet (8).

Legg merke til at i den matematiske modellen av systemet er emnet som leses "bundet" ikke til et spesifikt publikum, men til et bestemt sett med målgrupper. Plasseringen av spesifikke publikumstall gjøres etter at oppgaven er løst. Begrensninger av formen (8) gir mening bare når settene med publikum krysser hverandre. I den matematiske modellen av systemet foreslås det å ta hensyn til alle unike kryssende par i form av restriksjoner. Antallet av disse kryssene kan være stort, noe som kan føre til et stort antall ekstra begrensninger som negativt påvirker hastigheten på optimaliseringsalgoritmer. Antallet ekstra restriksjoner kan imidlertid reduseres betydelig.

La oss vurdere tilfellet med et lineært arrangement av kryssende sett (se fig. 2).

Fig.2. Lineært kryssende sett

Ved et slikt arrangement av sett med klasserom for gjennomføring av klasser, vil det totale antallet begrensninger av skjemaet (8) være n-1, hvor n er antall sett. Arrangementet av kryssende sett beskrevet ovenfor kan kalles lineært, siden i dette tilfellet er n kryssende sett arrangert som på en linje. Vi kan vurdere tilfellet når mengdene krysser hverandre på en vilkårlig måte (se fig. 3.).

Fig.3. Tilfeldig kryssende sett

Antall restriksjoner av formen (8) i dette tilfellet kan reduseres ved å danne disse restriksjonene analogt med tilfellet med et lineært arrangement av sett. For å gjøre dette er det nødvendig å anta at for eksempel sett B og D som skjærer A er ett sett, bestemme skjæringsområdet for et slikt sett med sett A, og utfør deretter de samme handlingene med den resulterende skjæringsområdet.

For mer informasjon om dette, se side 210.

2.4. Programresultater

Under den praktiske implementeringen av systemet ble det gitt spesiell oppmerksomhet til oppgaven med å skrive "kjernen" i systemet - metoder for å løse problemet og prosedyrer for å danne begrensninger. Siden målet ikke var å skrive et fullt funksjonelt kommersielt produkt, ble grensesnittdelen skrevet med det formål å teste kjernen og bestemme grensene for anvendelighet av algoritmer, derfor inkluderer den et minimum av funksjonalitet og inneholder ikke forhåndsbehandlingsmoduler for inngangsdata.

Systemkjernen og grensesnittet ble skrevet i Delphi 6.0. Metoder for løsning og algoritmer for å danne begrensninger er skrevet ved hjelp av objektorienterte teknologier, noe som vil gjøre det mulig i fremtiden å enkelt innkapsle dem i ytterligere modifikasjoner av systemet uten å krenke integriteten til interaksjonen mellom ulike algoritmer. Teksten til objektmetodene for å løse problemet er gitt i vedlegg 2. Databasen ble implementert på Oracle 8i DBMS, spørringer til den utføres i PL/SQL-språket.

De første oppgavedataene legges inn i databasetabeller ved hjelp av forespørselsskjemaer. En av disse formene er vist i fig. 3.

Fig.3. Skjema for å legge inn startdata

Dataene innhentet som et resultat av å løse problemet er ikke nok til å vise timeplanen umiddelbart etter å ha løst problemet, så det ble skrevet en etterbehandlingsmodul for data. Den endelige timeplanen vises i form av en tabell, et eksempel på dette er vist i fig. 4.

Ris. 4. Eksempel på timeplan

Algoritmer for å løse problemet ble testet på ulike utvalg av kildedata. Testing ble utført på en datamaskin med en Intel Pentium 350 MHz prosessor, Oracle 8i DBMS ble installert på en dobbel prosessor server: 2 CPU Intel Pentium II 350 MHz, RAM 384 MB; LAN med en båndbredde på opptil 100 Mbit/s ble brukt som kommunikasjonskanal. Som testkildedata brukte vi både reelle data om grupper, lærere og lesefag i kveldsundervisningsformen ved ChSU for studieårene 1999/2000, og tilfeldig genererte kildedata (lesbare fag ble tilfeldig tildelt målgrupper for klasser). I gjennomsnitt ble det utført fra 5 til 10 tester for hver testet dimensjon av kildedataene. Som et resultat fikk vi dataene vist i tabell 2. Figur 5 viser en graf over avhengigheten av gjennomsnittlig tid for å løse et problem på antall leste emner og antall grupper.

2.5. Analyse av oppnådde resultater

Ved å analysere innhentede data kan vi trekke noen konklusjoner om funksjonaliteten til løsningsalgoritmene og den matematiske modellen, deres mangler og bruksområder.

For det første inneholder den matematiske modellen som brukes "ekstra" restriksjoner, hvis eksistens skyldes den lineære heltallsmodellen; i tillegg er hvert emne som leses på strømmen (strømmen kan bestå av en gruppe) tildelt 12 (for kveldselever) variabler, som hver er en boolsk variabel. For det andre øker tiden det tar å løse problemet kraftig ettersom inndataene øker. Dette skjer på grunn av en kraftig økning i antall variabler og begrensninger i modellen, som et resultat av at dimensjonen til matrisene øker og følgelig tiden som kreves for å løse problemet. For det tredje dekker det matematisk formaliserte problemet kun oppgaven med å lage en timeplan for kveldselever uten å ta hensyn til overganger mellom bygninger. Å ta hensyn til tilleggskrav vil øke antallet begrensninger av problemet, noe som vil påvirke hastigheten til løsningsalgoritmene negativt.

La oss ta hensyn til den økende forskjellen mellom minimums- og gjennomsnittsverdien av tiden for å løse problemet etter hvert som problemets dimensjon øker. Denne forskjellen tilsvarer hvor "vellykket" (nærmest optimal) den innledende gjennomførbare grunnleggende løsningen av problemet ble funnet. Derfor kan tiden som kreves for å løse problemet reduseres betydelig ved "vellykket" å finne den innledende grunnleggende gjennomførbare løsningen. For å finne en slik løsning er det best å bruke heuristiske og dekomponeringsalgoritmer.

Konklusjoner I løpet av arbeidet ble det bygget en matematisk modell av universitetets timeplan for tilfelle av kveldsundervisning uten overganger mellom bygninger, metoder for å løse problemet ble valgt, og en modell for lagring av de første dataene til problemet ble utviklet. Kildedatalagringsmodellen, algoritmen for matematisk formalisering av modellen og løsningsmetodene ble implementert i form av programvaremoduler. Hastigheten til algoritmene ble testet på heterogene sett med innledende data, som et resultat av hvilke evner og bruksområde for algoritmene ble bestemt.

Basert på testresultatene ble det funnet at driftshastigheten til problemløsningsalgoritmer sterkt avhenger av mengden inputinformasjon og den opprinnelige tillatte grunnleggende løsningen, og derfor er betydelig dårligere enn heuristiske og dekomponeringsalgoritmer. Men i tilfelle av en heuristisk løsning, kan dens (løsnings)optimalitet (eller oppnåelse av et globalt maksimum) bare bevises ved et fullstendig søk av alle mulige alternativer (det er klart at i dette tilfellet vil kjøretiden til algoritmen være svært lang), derfor stopper iterasjoner av heuristiske algoritmer når et visst maksimum (det er umulig å si om det er lokalt eller globalt) av betydning. Løsningen av en slik algoritme kan være nær optimal, men ikke optimal. I dette tilfellet, for å oppnå et globalt maksimum, kan du bruke løsningsmetoden som er vurdert i arbeidet, siden det optimale kan oppnås i flere iterasjoner av de beskrevne løsningsmetodene.

LITTERATUR

1. Lagosha B.A., Petropavlovskaya A.V. Et sett med modeller og metoder for å optimalisere timeplaner ved et universitet // Økonomi og matematikk. metoder. 1993. T. 29. Utgave. 4.

2. Hu T. Heltallsprogrammering og flyter i nettverk. M.: Mir, 1979.

3. Lebedev S.S. Modifikasjon av Benders metode for delvis heltalls lineær programmering // Økonomi og matematikk. metoder. 1994. T. 30. Utgave. 2.

4. Lebedev S.S., Zaslavsky A.A. Bruke en spesiell gren og bundet metode for å løse et heltallsgenerert transportproblem // Økonomi og matematikk. metoder. 1995. T. 31. Utgave. 2.

5. Zaslavsky A.A. Bruk av variabel stratifiseringsstrategi i generelle problemer med heltalls lineær programmering // Økonomi og matematikk. metoder. 1997. T. 33. Utgave. 2.

6. Lebedev S.S. Om metoden for å bestille indeksering av heltalls lineær programmering // Økonomi og matematikk. metoder. 1997. T. 33. Utgave. 2.

7. Lebedev S.S., Zaslavsky A.A. Modifisert merkemetode for boolske programmeringsproblemer // Økonomi og matematikk. metoder. 1998. T. 34. Utgave. 4.

8. Zaslavsky A.A. Kombinert metode for å løse ryggsekkproblemer // Økonomi og matematikk. metoder. 1999. T. 35. Utgave. 1.

Vedlegg 1. Muligheter for programvareprodukter for planleggingssystemer.

MED AUTOR-2+-systemet er designet for raskt og enkelt å lage timeplaner og vedlikeholde dem gjennom hele studieåret.
EN VTOR-2+ er et universelt system. Det er flere versjoner av programmet designet for enhver utdanningsinstitusjon:

Videregående og spesialiserte (matematikk, språk, etc.) skoler, lyceums, gymsaler;

Tekniske skoler, skoler og høyskoler;

Universiteter med ett akademisk bygg;

Universiteter med flere akademiske bygninger (inkludert overføringer mellom bygninger).

EN VTOR-2+ gjør det mulig å forenkle og automatisere det komplekse arbeidet til tidsplanmakere så mye som mulig. Systemet hjelper deg enkelt å bygge, redigere og skrive ut i form av praktiske og visuelle dokumenter:

Timeplaner for klasser (studiegrupper);

Lærernes timeplaner;

Tidsplan for klasserom (kontorer);

Utdanningsplaner;

Tariffering.

EN VTOR-2+ har et fint design og vennlig service. Programmet er ganske enkelt å lære. Det er en detaljert håndbok som beskriver alle funksjonene og metodene for å jobbe med programmet.
P Programmet kjører på hvilken som helst IBM-kompatibel datamaskin, starter med 486DX med 4 Mb RAM (og høyere), tar opp ca. 1 Mb på harddisken. Operativsystem: MS DOS eller WINDOWS 95/98.
I Driftstiden avhenger av størrelsen på utdanningsinstitusjonen og kraften til datamaskinen. En fullstendig beregning og optimalisering av timeplanen for en mellomstor skole (30 klasser, 60 lærere, to skift) tar omtrent 15 minutter på en Celeron-400 datamaskin.

P Programmet kjennetegnes av en unik og veldig kraftig algoritme for å konstruere og optimalisere tidsplanen. Den resulterende automatiske timeplanen krever praktisk talt ingen manuell modifikasjon, det vil si at selv med svært komplekse og strenge begrensninger, blir alle mulige klasser automatisk plassert. Hvis det er uløselige motsetninger i kildedataene, kan de oppdages og elimineres ved hjelp av en spesiell analyseenhet.

EN VTOR-2+ lar deg:

Optimaliser "vinduer" i timeplanen;

Vurder den nødvendige rekkevidden av dager/timer for både klasser og lærere;

Det er optimalt å plassere klasser i klasserom (auditorier), med tanke på egenskapene til klasser, fag, lærere og klasseromskapasitet;

Ta hensyn til arbeidets art og ønsker fra både heltidsansatte og deltidstimearbeidere;

Det er enkelt å koble (“parre”) flere klasser (studiegrupper) til strømmer når du gjennomfører noen klasser;

Del klasser når du gjennomfører klasser i et fremmedspråk, kroppsøving, arbeidskraft, informatikk (og andre fag) i et hvilket som helst antall undergrupper (opptil ti!);

Innføre (i tillegg til hovedfagene) spesialkurs og valgfag;

Optimaliser jevnheten og arbeidsintensiteten til timeplanen.

2. «Schedule»-system ver 4.0 Moskva – LinTech

Det skal bemerkes med en gang at "Schedule"-programmet er fokusert på å utarbeide en skoleplan; bruk på universiteter og høyskoler er kun mulig med noen forbehold. Planleggingen gjøres innenfor rammen av et sett med betingelser som bestemmes ved trinnene med å legge inn innledende data. En fullstendig liste over mulige forhold er gitt nedenfor:

- OM maksimalt antall leksjoner er begrenset – dvs. maksimalt antall leksjoner tillatt per dag;

- R ensartet fordeling av lærernes arbeidsmengde mellom dagene i timeplanen;

- R jevn fordeling av klassebelastning mellom dagene i timeplanen;

- TIL overvåkingsvinduer i lærernes timeplaner;

- P Programmet tar hensyn til at klasser vilkårlig kan forenes og splittes (klasser kan kombineres i bekker eller splittes i mindre undergrupper, og disse undergruppene kan igjen tjene som grunnlag for å slå seg sammen til større grupper Eksempel: på skolen Nei 1859 Det er 2 seniorklasser, men i hver av disse klassene er det to undergrupper for spesialisering, holdes undervisning i allmennfag for hele klassen på en gang, og fag i spesialisering - hver for seg.Men siden undergruppene for spesialisering er for små. og det er ikke nok lærere, i noen fag kan undergruppene 11a og 11b også kombineres (for eksempel på et fremmedspråk) - dette gjør det vanskelig å sikre kontinuitet i timeplanen for klassene (det er nødvendig å sikre kontinuitet i timeplanen for hver av undergruppene);

- N tilstedeværelsen av flere skift - i dette tilfellet må individuelle klasser komme senere enn gruppene i det første skiftet; i tillegg blir det vanskeligere å kontrollere vinduene i lærernes timeplan, hvis det er lærere som jobber begge skift - i dette i tilfelle, i timeplanen til disse lærerne, må klassene deres "kontrakteres" rundt skjæringspunktet mellom skift;

- U betingelsen om å knytte lærere til publikum - individuelle lærere har "sitt eget" publikum der de leder alle klassene sine;

- N tilstedeværelsen av et "flytende" skift - når starttidspunktet for den første leksjonen ikke er nøyaktig bestemt, fordi det dannes dynamisk, avhengig av utgivelsen av relaterte klasser, lærere og publikum;

- TIL overvåke om timeplanen til et objekt (klasse, lærer, publikum) faller innenfor det tillatte arbeidsområdet (i kartet over tidsbegrensninger). For eksempel, for en lærer, indikerer kartet over tidsbegrensninger vanligvis metodiske dager, noen ganger individuelle leksjonstall - med et ord er de posisjonene indikert som det er umulig å sette klasser for med deltakelse av et gitt objekt;

- N tilstedeværelsen av kombinerte fag - som "fremmedspråk/informatikk", "informatikk/arbeid", etc. - når klassen er delt inn i undergrupper;

- U betingelsen om å knytte fag til klasserom - å gjennomføre klasser i individuelle fag er bare mulig i et strengt definert klasserom eller liste over klasserom (kroppsøving, arbeid, etc.);

- MEDå forlate timeplanen med tanke på at det i enkelte fag ikke er hele klassen som kommer til timen, men en undergruppe av den. For å hindre en annen undergruppe fra å vandre rundt på skolen på dette tidspunktet, kan slike klasser strengt tatt bare være de første eller siste timene i timeplanen;

- “I opprettholde paralleller" - for noen lærere er det nødvendig å ta hensyn til det faktum at gjennomføring av klasser krever langsiktig forberedelse (for eksempel kjemitimer), i dette tilfellet er klasser i lærerens daglige timeplan forsøkt arrangert i blokker med paralleller, for eksempel først 5. klasse, deretter 7. -y osv., eller ved fordeling mellom dager, fordele klasser i ulike paralleller på ulike dager;

- OG Noen ganger, når du lager en tidsplan, er det nødvendig å ta hensyn til nyansen at for noen fag er timeplanen kjent på forhånd - i dette tilfellet introduseres slike klasser som ikke-bevegelige (faste);

- TIL kontroll av forbudte kombinasjoner av fag som faller på samme dag i timeplanen - for eksempel er det uønsket at "kroppsøving" og "arbeid" utføres på samme dag;

- I oppfylle betingelsen for de nødvendige sekvensene av fag - når det er nødvendig å sikre installasjon av grupper av klasser der klasser må finne sted i en bestemt sekvens, for eksempel fysikk-astronomi, etc.;

- N tilstedeværelsen av klasser knyttet til klasserom - hoveddelen av klasser for slike klasser holdes i dette klasserommet, med unntak av de klassene som krever et spesialisert klasserom;

- N behovet for å arrangere klasser i individuelle fag i to klasser på rad ("parvis", "gnister"), og denne betingelsen kan være streng (i ingen tilfeller bryte opp "gnister" av klasser), eller kan være å foretrekke (hvis det er ikke mulig å flytte to klasser, "gnisten" kan brytes);

Det tas hensyn til at i enkelte fag er plassering kun tillatt i enkeltklasser.

3. "Metodisk" system

Tilgjengelig i to versjoner.

Virtuell versjon.

Tilgjengelig uten automatisk planleggingsmodul. Funksjoner til den virtuelle versjonen:

Rask søk i lister over lærere, klasserom, klasser (grupper), disipliner, bygninger;

Innhenting av referanseinformasjon for hvert funnet element på listen (publikumskapasitet, alle auditoriumbygninger X, adresse og telefonnummer til læreren, liste over avdelingen, antall timer i faget, lærerens undervisningsmengde, etc.);

Kontroll og evne til å omfordele timer mellom uker i enhver akademisk disiplin. grupper;

Automatisk kontroll av mulige datainntastingsfeil (korrespondanse av totalt antall timer og typer klasser, manglende tildeling av lærere til undergrupper, tidsbudsjett for studiegruppen og læreren, avvik mellom timer i strømgrupper, etc.);

Evnen til systematisk å lagre (og raskt søke etter) ytterligere (ikke nødvendig for planlegging) informasjon: bilder av lærere, kuratorer av studiegrupper (klasselærere), informasjon om representanter for foreldreutvalg, stillinger, akademiske grader og titler som er ansvarlige for publikum, ...

Få raskt fullstendig informasjon om en kombinasjon av faktorer (alle grupper i strømmen, alle disipliner til lærer X, angir arbeidsmengden etter uke og klassetype, hvilke disipliner som er tillatt å undervise i dataklassen, personlige ønsker for gjennomføring av klasser til en hvilken som helst lærer, en liste over ferier i den syriske gruppen, og mye mer osv.);

Evnen til å se, skrive ut og redigere en ferdig timeplan med å kontrollere riktigheten av endringer (belegg av klasserom, lærere, grupper/undergrupper, ...);

Du kan når som helst bestille en tidsplangenereringsmodul for forberedte data;

Tidsplanen genereres på datamaskinen din med mulighet for å endre innstillinger, kontrollere, redigere osv. (uten mulighet for å endre timer, disipliner, lærere, ...);

Hvis behovet for en mindre (opptil 10 %) endring i kildedata oppdages (feil, plutselige tillegg er funnet), er det mulig å ombestille tidsplangenereringsmodulen for en liten avgift;

Du kan bytte til standardversjonen når som helst;

Metodist - standard.

I tillegg til funksjonene til den virtuelle versjonen inkluderer den:

Automatisk planleggingsmodul;

Fordeling og kontroll av undervisningsmengde;

Streng overholdelse av rekkefølgen av disiplinen (forelesninger - 2 timer, praktisk - 4 timer, laboratorium ...);

Opprette en tidsplan for alle typer utdanningsinstitusjoner: ukentlig eller semester (fra 1 til 23 uker);

Regnskap for å kombinere grupper (klasser) til bekker og/eller dele dem inn i undergrupper;

Tildeling av spesialklasserom (datatimer, språklaboratorier, svømmebasseng, ...);

Regnskap for ansettelse av lærere og klasserom (deltidsarbeid, bruk av felles utdanningsbase);

Regnskap for overgangstid mellom bygninger;

Helger og helligdager - generelt og for individuelle studiegrupper (nasjonale, religiøse, helligdager);

Angivelse av årsakene til den "mislykkede tildelingen" av klasser (klasserommet er opptatt, læreren er tildelt en uønsket ukedag) med mulighet for deres "manuelle" korreksjon;

Mulighet for gjentatt automatisk "forbedring" av tidsplanen;

Mulighet for å endre betydningen av faktorer som tas i betraktning ved utarbeidelse av tidsplanen;

Muligheten for å innføre lærernes prioriteringer - i hvilken grad det tas hensyn til deres individuelle ønsker;

Begrensninger for "Methodist"-funksjonaliteten:

Flerskiftsplaner er begrenset til et maksimalt antall leksjoner per dag - 7;

Klassene begynner alltid med den første leksjonen/paret (om nødvendig er det mulig å tildele en "gratis leksjon" til det første paret);

Tidspunktet for endring er ikke tatt i betraktning (for eksempel for å sjekke muligheten for å flytte mellom bygninger);

Klassenes "vanskelighetsgrad" tas ikke i betraktning for deres rasjonelle fordeling gjennom uken (selv om det er mulig å gjøre dette indirekte);

Varigheten av klassene er konstant (det er umulig å lage en timeplan for en 30-minutters leksjon på ungdomsskolen og 45-minutters leksjoner på videregående).

Vedlegg 2. Liste over programvaremodulen over metoder for å løse problemet med automatisk planlegging

type MyArray= array of array of real;

MyArray_X = array of longint;

prosedyre Step_Dual_simplex(var a:MyArray; m,n,i1,j1:heltall);

(utfører ett trinn i dual simplex-metoden,

ledende element - a)

var i,j:heltall;

b,b1:array av ekte;

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

for i:=0 til m-1 gjør b[i]:=a;

for i:=0 til n-1 gjør b1[i]:=a;

for i:=0 til m-1 do

for j:=0 til n-1 begynner

hvis (i=i1) og (j=j1) så a:=1/b

hvis (i=i1) så a:=b1[j]/b

hvis (j=j1) så a:=-b[i]/b

ellers a:=a-b[i]*b1[j]/b;

for i:=0 til n-1 gjør a:=0;a:=-1;

Fullfør(b);Fullfør(b1);

funksjon Lexikogr_few(a:MyArray; m,n:heltall;i,i1:heltall):boolsk;

(den første kolonnen er leksikografisk mindre enn den andre)

Lexikogr_få:=false;

mens (a=a) og (j

funksjon Finn_nu(a:MyArray;m,n:heltall; i,i1:heltall):longint;

(i er indeksen til den leksikografisk minimale kolonnen)

mens (a=a) og (j

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

prosedyre Full_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:heltall);

(Fulltallsalgoritme for det lineære heltallsproblemet

programmering,

se Hu T. "Heltallsprogrammering og flyter i nettverk", s. 300-309,

a er en matrise med størrelsen m+n+2*n+1, analogt:

Vi må finne det maksimale

z= - 10x1 - 14x2 - 21x3

2x1 + 2x2 + 7x3 >= 14

8x1 + 11x2 + 9x3 >= 12

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

prosedyren returnerer en vektor X, hvor de første m komponentene er den ønskede løsningen,

hvis den siste komponenten av vektoren = 1, så eksisterer ikke løsningen eller den = uendelig)

var i,i1:heltall;

mens (i =0) gjør Inc(i); (produserer streng)

mens (j =0) gjør Inc(j);

for i1:=1 til n-1 gjør hvis (a

minimum kolonne)

(alfavalg)

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

for i1:=1 til n-1 gjør hvis a

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

hvis (j1>0) og (-a/j1>alfa) så alfa:=-a/j1;

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

(mottar Gomori-kuttet)

for i1:=0 til n-1 gjør hvis a>0 så a:=round(Int(a/alfa))

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

hvis Frac(a/alfa)0 så a:=a-1;

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

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

for i:=0 til m-1 gjør x[i]:=runde(a);

hvis j>=n så x:=1 ellers x:=0;

prosedyre Step_One_Simplex(var a:MyArray; m,n,i:heltall);

var i1,i2:heltall;

(Et trinn i den direkte heltallsmetoden (produserende linjen er den siste

i - genererer kolonne))

for i1:=0 til m-2 gjør a:=a/(-a);

for i2:=0 til n-1 do

for i1:=0 til m-2 do

hvis i2i så a:=a+a*a;

prosedyre Direct_Integer_Simplex(var x:MyArray_X; a:MyArray; m,n:heltall);

(Direkte heltallsalgoritme for det lineære heltallsprogrammeringsproblemet,

se Hu T. "Heltallsprogrammering og flyter i nettverk", s. 344-370,

a er en matrise med størrelsen m+n+3*n+1 analogt:

må maksimeres

z = x1 + x2 + x3

4x1 + 5x2 + 2x3

da vil matrise a se slik ut:

10 1 1 1 - på denne linjen er det første tallet den grove maks summen av ikke-grunnleggende variabler

0 0 0 0 - streng for å kutte av Gomori,

Algoritmen fungerer bare når a>=0

returnerer vektor X - i stedet for identitetsmatrisen den ønskede løsningen,

hvis den siste komponenten inneholder en enhet, er det en feil i beregningene)

var i,j,i1,j1:heltall;

b,b1,b2:array av byte;

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

for i:=0 til m-1 gjør b1[i]:=0;

(sjekker optimalitetstilstanden)

for j:=1 til n-1 gjør hvis a

mens bool begynner

(søk etter genereringskolonnen)

bool:=false;j1:=0;

for j:=1 til n-1 begynner

hvis a>0 da

for i:=0 til m-3 gjør a:=a/a;

hvis ikke bool, begynn j1:=j;bool:=true;end else if Lexikogr_few(a,m,n,j,j1)

(søk etter genererende streng)

for j:=1 til n-1 do

hvis a>0 da

for i:=0 til m-3 gjør a:=a*a;

Anta at det er et sett n identiske prosessorer, utpekte og m uavhengige oppgaver
som må fullføres. Prosessorer kan arbeide samtidig, og enhver oppgave kan utføres på hvilken som helst prosessor. Når en jobb er lastet inn i prosessoren, forblir den der til slutten av behandlingen. Behandlingstid for jobb kjent og likeverdig
Organiser oppgavebehandlingen på en slik måte at hele settet med oppgaver fullføres så raskt som mulig.

Systemet fungerer som følger: den første ledige prosessoren tar neste oppgave fra listen. Hvis to eller flere prosessorer frigjøres samtidig, vil prosessoren med det laveste tallet utføre neste oppgave fra listen.

Eksempel. La det være tre prosessorer og seks jobber, utførelsestiden for hver av dem er lik:

La oss vurdere tidsplanen i det første øyeblikket T=0, prosessor begynner å behandle jobben , prosessor - oppgaver , og prosessoren - oppgaver . prosessor fullfører oppgaven på et tidspunkt
, mens prosessorene Og jobber fortsatt med sine opprinnelige oppgaver. På T=3 prosessor fullfører oppgaven igjen og begynner å behandle oppgaven , som slutter i øyeblikket T=4. Så begynner han å fullføre den siste oppgaven . Prosessorer Og fullføre oppgaver når T=5, men siden listen L tomme, stopper de. prosessor fullfører oppgaven på T=12. Den vurderte tidsplanen er illustrert i fig. 1. tidsdiagram kjent som Gantt-diagram. Tidsplanen er åpenbart ikke optimal. Du kan for eksempel "velge" en tidsplan som lar deg fullføre alle oppgaver i T* = 8 tidsenheter (fig. 2.).

La oss nå se på en annen type planleggingsproblem for multiprosessorsystemer. I stedet for spørsmålet om den raskeste fullføringen av et sett med jobber for et fast antall prosessorer, stiller vi nå spørsmålet om minimum antall prosessorer som kreves for å fullføre et gitt sett med jobber på en fast tid . Selvfølgelig er det på tide vil ikke være mindre enn tiden det tar å fullføre den mest arbeidskrevende oppgaven.

I denne formuleringen tilsvarer planleggingsproblemet følgende pakkeproblem. La hver prosessor tilsvarer boksen størrelse . La hver oppgave samsvarer med varestørrelsen , lik oppgaveutførelsestiden , Hvor
Nå, for å løse planleggingsproblemet, må du bygge en algoritme som lar deg plassere alle elementene i minimum antall bokser. Selvfølgelig kan du ikke fylle bokser utover deres kapasitet. , og objekter kan ikke deles i biter.

Litteratur

1. T. Cormen, C. Leiserson, R. Rivest

Algoritmer: konstruksjon og analyse. M.: MTsNMO, 2000.

2. D. Knuth The Art of Programming, bind 1. Grunnleggende algoritmer. Uch. landsby M.: Ed. Williams House, 2000.

3. Wirth N. Algoritmer og datastrukturer.: Pr. Fra engelsk - M.: Mir, 2001.

4. Khusainov B.S. Strukturer og algoritmer for databehandling. Eksempler på

C språk Lærebok godtgjørelse. M: Finans og statistikk, 2004.

5. A. Aho, J. Hopcroft, J. Ullman, Datastrukturer og algoritmer M: St. Petersburg: Kyiv: Williams, 2001.

Algoritmeplan. Oppgave: Utvikling av en matematisk modell og programvare for planlegging av problemer. Rangering av undervisningstimer i løpet av uken avhengig av prestasjonsnivået til elevene i ulike klasser

Formulering av problemet

Genetisk algoritme

Planleggingsalgoritme

Konklusjon

Timeplanen regulerer rytmen i skolehverdagen, arbeidet og resten til elever og lærere.
Effektiviteten til hele utdanningsprosessen avhenger i stor grad av kvaliteten.

Berettigelse av undervisning og skoletime

Omtrentlig vareakseptabilitetsskala

Akseptabilitetsskala for varer

Planleggingsalgoritme

Prosedyre for endring av timeplanen

Algoritme for justering av skoleplanen

Kriterier for hygienisk vurdering av skoleruta

Pivottabellskjema for behandling av svar

Rangering av studietimer i løpet av uken
avhengig av prestasjonsnivået til elevene i ulike klasser

Lærerens ukentligell

Teknologi for å utføre oppsettet av timeplantabellen

Algoritme for utførelse av layout

Informasjon som trengs for å lage en tidsplan

HIERARKISK ORGANISERINGSMETODE

2.3.4. FUNKSJONER AV FORMASJONSBEGRENSNINGER I DEN MATEMATISKA MODELLEN FOR TIDSPLANPROBLEMET

Litteratur

Formulering av problemet

Genetisk algoritme

Planleggingsalgoritme

Konklusjon

Timeplanen regulerer rytmen i skolehverdagen, arbeidet og resten til elever og lærere. Effektiviteten til hele utdanningsprosessen avhenger i stor grad av kvaliteten.

Berettigelse av undervisning og skoletime

Omtrentlig vareakseptabilitetsskala

Akseptabilitetsskala for varer

Planleggingsalgoritme

Prosedyre for endring av timeplanen

Algoritme for justering av skoleplanen

Kriterier for hygienisk vurdering av skoleruta

Pivottabellskjema for behandling av svar

Rangering av studietimer i løpet av uken avhengig av prestasjonsnivået til elevene i ulike klasser

Lærerens ukentligell

Teknologi for å utføre oppsettet av timeplantabellen

Algoritme for utførelse av layout

Informasjon som trengs for å lage en tidsplan

HIERARKISK ORGANISERINGSMETODE

2.3.4. FUNKSJONER AV FORMASJONSBEGRENSNINGER I DEN MATEMATISKA MODELLEN FOR TIDSPLANPROBLEMET

Litteratur

Timeplanen regulerer rytmen i skolehverdagen, arbeidet og resten til elever og lærere.
Effektiviteten til hele utdanningsprosessen avhenger i stor grad av kvaliteten.

Rangering av studietimer i løpet av uken
avhengig av prestasjonsnivået til elevene i ulike klasser