Skema teori

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. november 2019; checks kræver 10 redigeringer .

Skemateori er en gren af diskret matematik , der beskæftiger sig med bestillingsproblemer. I det generelle tilfælde er problemerne formuleret som følger: Et bestemt sæt job (krav) med et bestemt sæt karakteristika er specificeret: varigheden af behandlingen af kravet (det enkleste tilfælde), omkostningerne ved at behandle kravet, tidspunktet anmodningen ankommer, fristen for at afslutte forkyndelsen af anmodningen. Et bestemt sæt maskiner (enheder) er givet , på hvilke kravene skal betjenes i overensstemmelse med en bestemt rækkefølge. ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\))$ $M=\{M_{1},M_{2},\dots ,M_{m}}\}$

Opgaven med diskret optimering er : at opbygge en tidsplan, der minimerer tiden til at fuldføre arbejdet, omkostningerne ved arbejdet osv. Tidsplanen er en indikation på hvilke maskiner og på hvilket tidspunkt kravene skal serviceres (arbejde udført).

Planlægningsteoriens opgaver kan opdeles i to grupper:

Afbryd opgaver. Servicen af et krav på en maskine kan til enhver tid afbrydes (med mulighed for senere at afslutte den samme eller en anden maskine) for at betjene et andet krav.
uafbrudte opgaver - alle krav på maskinen serviceres fra start til slut uden afbrydelser.

Der er forskellige varianter af skemalægningsteoriproblemer, nogle af dem er NP-komplette , nogle tilhører klassen af polynomielle problemer , for nogle problemer var det ikke muligt at bevise medlemskab i nogen kompleksitetsklasse. Der er en formodning om, at en opgave, der tillader afbrydelser, ikke er sværere end en opgave uden afbrydelser. For de fleste problemer observeres det, bortset fra ét, hvor det for en variant uden afbrydelse er bevist, at det tilhører klassen af polynomielle problemer , mens der for et lignende problem med afbrydelser ikke er bevis for, at det tilhører nogen kompleksitetsklasse.

I henhold til disciplinen at udføre arbejde på maskiner kan der skelnes mellem fire hovedklasser af opgaver:

Åben butik, åben linje - hvert krav har sit eget undersæt af maskiner, på hver af dem skal det serviceres i nogen tid. Servicerækkefølgen på disse maskiner er vilkårlig. Forskellige objektive funktioner er fastsat.
Jobbutik, værksted - hvert krav har sit eget bestilte undersæt af maskiner (rute), hvorpå det skal serviceres i en given rækkefølge. Forskellige objektive funktioner er fastsat.
Flowshop , flowline - alle maskiner er i orden -og hvert krav går igennem alle maskinerne i den rækkefølge. Tidsplanen er fastsat af en permutation af krav. Som regel minimeres den samlede tid til serviceforespørgsler. ${\displaystyle M_{1},M_{2},\dots ,M_{m))$
Opgave med deadlines - for hvert krav angives ankomsttidspunkt, servicetidspunkt og forfaldsdato for ophør af service. Servicerækkefølgen på enhederne er vilkårlig. Du skal finde en tidsplan, der overholder deadlines. Hvis en sådan tidsplan eksisterer, kan problemet med at minimere antallet af afbrydelser indstilles.

Den sidste opgave kaldes single-stage , de første tre kaldes multi-stage , da der for hvert krav er flere trin eller serviceoperationer på forskellige enheder. Forskellige kombinationer af begrænsninger og servicediscipliner er mulige, men algoritmer, der er polynomiske i udførelsestid, kendes kun for de enkleste problemer fra disse klasser.

Især for Flow shop-problemet på to maskiner er der Johnson-algoritmen [1] for tidskompleksitet , som opbygger en tidsplan med den minimale samlede servicetid. $O(n\log(n))$

For en opgave med forfaldsdatoer med et vilkårligt antal enheder og tjenesteafbrydelser er der en tidskompleksitetsalgoritme , som opbygger en tidsplan, der respekterer forfaldsdatoerne [2] . $O(n^{3})$

Løsningen af Open shop- og Jobshop-problemerne med én enhed uden afbrydelser er en vis permutation af kravene, og for en vilkårlig objektiv funktion er disse problemer NP-komplette. Men for nogle specifikke objektive funktioner er der fundet polynomielle algoritmer. [3] [4] [5]

Problemer med skemalægningsteori (skemalægning) skrevet i kontinuerlig tid har som regel et uendeligt sæt af gennemførlige løsninger. Bestillingsmetoden giver os mulighed for at reducere planlægningsproblemer til optimeringsproblemer på endelige sæt af permutationer af job. Der formuleres en generel redegørelse for problemet med skemalægningsteori (skemalægning) i kontinuert tid, hvor løsningskomponenterne beskrives ved hjælp af heltalsfunktioner af tid, og som kan løses ved bestillingsmetoden. [6]

To måder at reducere de oprindelige problemer til ordensproblemer er baseret på begreberne kompakte (aktive) og kvasi-kompakte (semiaktive) løsninger. [7] I ovenstående fortryk af V. V. Shmelev [6] generaliseres begreberne kompakte og kvasi -kompakte løsninger, og på dette grundlag foreslås et nyt koncept for monotone løsninger. Enhver monoton løsning er både kompakt og quasi-kompakt på samme tid, så der er normalt færre sådanne løsninger. Dette forenkler løsningen af bestillingsproblemer.

For at beskrive dynamiske problemer med ressourceallokering med komplekse forsinkelser, inklusive dem med vektor og distribuerede, som inkluderer problemer med planlægningsteori (planlægning), var Shmelev V.V. i 1983 [6] den første til at bruge implicit og kontinuerligt tidspunktet for foldningsoperationen . Efterfølgende brugte han denne operation eksplicit til diskret tid og formulerede den generelle formulering af problemet med planlægningsteori (planlægning) i form af et lineært dynamisk programmeringsproblem med foldninger . [8] [9] Denne erklæring giver dig mulighed for enkelt og kompakt at beskrive et stort antal dynamiske problemer, inklusive dem med heltalsvariabler . Shmelev V. V. udvidede sine resultater om metoden med nøjagtige straffunktioner til denne indstilling.

Noter

↑ SM Johnson , Optimale to- og tre-trins produktionsplaner med opsætningstider inkluderet, Naval Res. log. Quart. I(1954) 61-68.
↑ Tanaev V.S., Gordon V.S., Shafransky Ya.M. Theory of schedules. Et-trins systemer. - M.: Nauka, 1984.
↑ Planlægningszoo . Hentet 27. april 2013. Arkiveret fra originalen 28. april 2013. (ubestemt)
↑ CiteSeerX - Planlægning af en enkelt maskine med forbehold for forrangsforsinkelser . Hentet 27. april 2013. Arkiveret fra originalen 28. april 2013. (ubestemt)
↑ Kompleksitetsresultater for planlægningsproblemer . Hentet 27. april 2013. Arkiveret fra originalen 28. april 2013. (ubestemt)
↑ 1 2 3 V. V. Shmelev. Bestillingsmetode i planlægningsproblemer. Fortryk. Moskva: VNIISI . 1983. Fortrykket er tilgængeligt på webstedet for Scientific Electronic Library eLIBRARY.RU i listen over publikationer af Shmelev V.V.
↑ Conway R. V., Maxwell V. L., Miller L. V. Schedule theory. - M .: "Nauka", 1975, afsnit 6.5.
↑ Shmelev V.V. Dynamiske planlægningsopgaver. Automation and Telemechanics , 1997, nr. 1, 121-125.
↑ Shmelev V.V. Metode til nøjagtige straffunktioner til lineære blandede heltalsoptimeringsproblemer. Afhandling til doktorgraden i fysiske og matematiske videnskaber, M.: ISA RAN, 2000, kapitel 6. Afhandlingen og dens abstract er tilgængelig på webstedet for Scientific Electronic Library eLIBRARY.RU i listen over publikationer af Shmelev V.V.

Litteratur

Richard W. Conway, William L. Maxwell, Louis W. Miller . Teori om planlægning
- Conway R. V., Maxwell V. L., Miller L. V. Skema teori. Moskva: Hovedudgaven af den fysiske og matematiske litteratur fra Nauka-forlaget, 1975.
Tanaev V. S. , Shkurba V. V. Introduktion til planlægningsteori. (Serie "Economics and Mathematics Library"), Moskva: Hovedudgaven af den fysiske og matematiske litteratur fra forlaget "Nauka", 1975.
Levin VI Strukturel-logiske metoder i skemalægningsteori. Penza: Penz Publishing House. stat technol. acad., 2006.
Lazarev A. A. Skema teori. Estimater af absolut fejl og et skema til den omtrentlige løsning af planlægningsproblemer . Tutorial. (IPU RAS, MIPT) - M.: MIPT, 2008. - 222 s. ISBN 978-5-7417-0257-4
Lazarev A. A., Musatova E. G., Gafarov E. R., Kvaratskhelia A. G. Skema teori. Problemer med jernbaneplanlægning . M.: IPU RAN, 2012. 92 s. ISBN 978-5-91450-102-7 .
Brucker P. Planlægningsalgoritmer . Heidelberg, Springer. Femte udg. ISBN 978-3-540-24804-0 (officiel udgivelse på forlagets portal).
Peter Brucker planlægningsalgoritmer . Heidelberg, Springer. Femte udg. ISBN 978-3-540-24804-0 Arkiveret 21. februar 2016 på Wayback Machine

Populærvidenskabelige publikationer

Shkurba V. V. " Problemet med tre maskiner ." — M.: Nauka, 1976. — 96 s., illustration.