Aikatauluteoria

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14. marraskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Aikatauluteoria on diskreetin matematiikan haara , joka käsittelee järjestysongelmia. Yleisessä tapauksessa ongelmat muotoillaan seuraavasti: Määritetään tietty joukko töitä (vaatimuksia) , joilla on tietyt ominaisuudet: vaatimuksen käsittelyn kesto (yksinkertaisin tapaus), vaatimuksen käsittelykustannukset, hetki pyyntö saapuu, määräaika pyynnön tiedoksiannon suorittamiselle. Tietty joukko koneita (laitteita) annetaan , joille vaatimukset tulee palvella tietyn järjestyksen mukaisesti. ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\))$ $M=\{M_{1},M_{2},\dots ,M_{m}}\}$

Diskreetin optimoinnin tehtävänä on : rakentaa aikataulu, joka minimoi työn valmistumisajan, työn kustannukset jne. Aikataulu on osoitus siitä, mitkä koneet ja milloin vaatimukset tulee huoltaa (työt suoritetaan).

Aikatauluteorian tehtävät voidaan jakaa kahteen ryhmään:

Keskeytä tehtävät. Koneessa olevan vaatimuksen palvelu voidaan milloin tahansa keskeyttää (mahdollisuudella lopettaa myöhemmin samalla tai toisella koneella) toisen vaatimuksen palvelemiseksi.
keskeytyksettä - kaikki koneen vaatimukset huolletaan alusta loppuun ilman keskeytyksiä.

Ajoitusteoriatehtävistä on olemassa erilaisia muunnelmia, osa niistä on NP-täydellisiä , osa kuuluu polynomitehtävien luokkaan , joidenkin tehtävien kuuluvuutta mihinkään kompleksisuusluokkaan ei voitu todistaa. On arveltu, että keskeytyksiä salliva tehtävä ei ole vaikeampi kuin keskeytyksetön tehtävä. Useimmille ongelmille se havaitaan, lukuun ottamatta yhtä, jossa keskeytyksettä muunnelman osalta osoitetaan sen kuuluvan polynomitehtävien luokkaan , kun taas samanlaiselle keskeytysongelmalle ei ole todisteita sen kuulumisesta mihinkään kompleksisuusluokkaan.

Koneilla työskentelyn kurinalaisuuden mukaan voidaan erottaa neljä pääasiallista tehtäväluokkaa:

Avoin myymälä, avoin linja - jokaiselle vaatimukselle on oma osajoukkonsa koneita, joista jokaisessa sitä on huollettava jonkin aikaa. Huoltojärjestys näissä koneissa on mielivaltainen. Erilaisia tavoitefunktioita on asetettu.
Työpaja, työpaja - jokaiselle vaatimukselle on oma tilattu osajoukko koneita (reitti), jolla se on huollettava tietyssä järjestyksessä. Erilaisia tavoitefunktioita on asetettu.
Flow shop , flow line - kaikki koneet ovat kunnossa -ja jokainen vaatimus käy läpi kaikki koneet tässä järjestyksessä. Aikataulu määräytyy vaatimusten permutaatiolla. Pääsääntöisesti huoltopyyntöjen kokonaisaika on minimoitu. ${\displaystyle M_{1},M_{2},\dots ,M_{m))$
Tehtävä määräajoin - jokaiselle vaatimukselle ilmoitetaan saapumishetki, palveluaika ja palvelun päättymisen eräpäivä. Laitteiden palvelujärjestys on mielivaltainen. Sinun on löydettävä aikataulu, joka noudattaa määräaikoja. Jos tällainen aikataulu on olemassa, voidaan asettaa keskeytysten määrän minimointiongelma.

Viimeistä tehtävää kutsutaan yksivaiheiseksi , kolmea ensimmäistä monivaiheiseksi , koska jokaista vaatimusta varten on useita vaiheita tai palvelutoimintoja eri laitteissa. Erilaiset rajoitteiden ja palvelualojen yhdistelmät ovat mahdollisia, mutta suoritusaikaltaan polynomiset algoritmit tunnetaan vain näiden luokkien yksinkertaisimmista ongelmista.

Erityisesti Flow shop -ongelmaa varten kahdessa koneessa on Johnson-algoritmi [1] ajan monimutkaisuus , joka rakentaa aikataulun minimipalveluajalla. $O(n\log(n))$

Tehtävälle, jossa on määräpäivät ja mielivaltainen määrä laitteita ja palvelukatkoksia, on olemassa aikamonimutkaisuusalgoritmi , joka rakentaa aikataulun, joka noudattaa eräpäiviä [2] . $O(n^{3})$

Open shop ja Job shop -ongelmien ratkaisu yhdellä laitteella ilman keskeytyksiä on vaatimusten permutaatio, ja mielivaltaiselle tavoitefunktiolle nämä ongelmat ovat NP-täydellisiä. Mutta joillekin erityisille tavoitefunktioille on löydetty polynomialgoritmeja. [3] [4] [5]

Jatkuvassa ajassa kirjoitetuilla ajoitusteorian (skeduloinnin) ongelmilla on pääsääntöisesti ääretön joukko toteuttamiskelpoisia ratkaisuja. Järjestysmenetelmän avulla voimme vähentää aikataulutusongelmat optimointiongelmiin töiden äärellisissä permutaatiosarjoissa. Jatkuvassa ajassa ajoitusteorian (skeduloinnin) ongelmasta muotoillaan yleinen lausunto, jossa ratkaisukomponentit on kuvattu ajan kokonaislukufunktioilla ja jotka voidaan ratkaista järjestysmenetelmällä. [6]

Kaksi tapaa pelkistää alkuperäiset ongelmat tilausongelmiksi perustuvat kompaktien (aktiivisten) ja kvasikompaktien (puoliaktiivisten) ratkaisujen käsitteisiin. [7] Yllä olevassa V. V. Shmelevin esijulkaisussa [6] kompaktien ja lähes kompaktien ratkaisujen käsitteet on yleistetty ja tältä pohjalta ehdotetaan uutta monotonisten ratkaisujen konseptia. Jokainen monotoninen ratkaisu on samanaikaisesti sekä kompakti että lähes kompakti, joten tällaisia ratkaisuja on yleensä vähemmän. Tämä yksinkertaistaa tilausongelmien ratkaisua.

Shmelev V.V. vuonna 1983 [6] käytti ensimmäisenä implisiittisesti ja jatkuvasti konvoluutiooperaation kuvaillakseen dynaamisia ongelmia resurssien allokoinnissa monimutkaisilla viiveillä, mukaan lukien vektori- ja hajautetut viiveet, jotka sisältävät aikatauluteorian (skeduloinnin) ongelmia. . Myöhemmin hän käytti tätä operaatiota nimenomaisesti diskreetille ajalle ja muotoili aikatauluteorian (aikataulutuksen) ongelman yleisen muotoilun lineaarisen dynaamisen ohjelmointiongelman muodossa konvoluutioineen . [8] [9] Tämän lauseen avulla voit kuvata yksinkertaisesti ja tiiviisti useita dynaamisia ongelmia, mukaan lukien kokonaislukumuuttujia sisältävät ongelmat . Shmelev V. V. laajensi tuloksensa tarkkojen rangaistusfunktioiden menetelmästä tähän asetukseen.

Muistiinpanot

↑ SM Johnson , Optimaaliset kaksi- ja kolmivaiheiset tuotantoaikataulut asennusajat mukaan lukien, Naval Res. Hirsi. Quart. I(1954) 61-68.
↑ Tanaev V.S., Gordon V.S., Shafransky Ya.M. Aikatauluteoria. Yksivaiheiset järjestelmät - M.: Nauka, 1984.
↑ Aikataulutettu eläintarha . Haettu 27. huhtikuuta 2013. Arkistoitu alkuperäisestä 28. huhtikuuta 2013. (määrätön)
↑ CiteSeerX - Single Machine Scheduling Aloittaa ensisijaisia viiveitä . Haettu 27. huhtikuuta 2013. Arkistoitu alkuperäisestä 28. huhtikuuta 2013. (määrätön)
↑ Aikatauluongelmien monimutkaisuustulokset . Haettu 27. huhtikuuta 2013. Arkistoitu alkuperäisestä 28. huhtikuuta 2013. (määrätön)
↑ 1 2 3 V. V. Shmelev. Tilausmenetelmä aikatauluongelmissa. Preprint. Moskova: VNIISI . 1983. Esipainos on saatavilla Scientific Electronic Libraryn eLIBRARY.RU:n verkkosivuilla Shmelev V.V.:n julkaisuluettelossa.
↑ Conway R. V., Maxwell V. L., Miller L. V. Aikatauluteoria. - M .: "Nauka", 1975, osa 6.5.
↑ Shmelev V.V. Aikataulutuksen dynaamiset tehtävät. Automation and Telemechanics , 1997, nro 1, 121-125.
↑ Shmelev V.V. Tarkkojen sakkofunktioiden menetelmä lineaarisille sekakokonaislukuoptimointiongelmille. Väitös fysiikan ja matemaattisten tieteiden tohtorin tutkintoa varten, M.: ISA RAN, 2000, luku 6. Väitöskirja ja sen tiivistelmä ovat saatavilla Scientific Electronic Libraryn eLIBRARY.RU:n verkkosivuilla Shmelev V.V.:n julkaisuluettelossa.

Kirjallisuus

Richard W. Conway, William L. Maxwell, Louis W. Miller . Aikataulutuksen teoria
- Conway R. V., Maxwell V. L., Miller L. V. Aikatauluteoria. Moskova: Nauka-kustantamon fyysisen ja matemaattisen kirjallisuuden pääpainos, 1975.
Tanaev V. S. , Shkurba V. V. Johdatus aikatauluteoriaan. (Sarja "Economics and Mathematics Library"), Moskova: Kustantajan "Nauka" fyysisen ja matemaattisen kirjallisuuden pääpainos, 1975.
Levin VI Rakennelogiset menetelmät aikatauluteoriassa. Penza: Penz Publishing House. osavaltio tekniikka. akat., 2006.
Lazarev A. A. Aikatauluteoria. Absoluuttisen virheen estimaatit ja kaavio ajoitusongelmien likimääräiselle ratkaisulle . Opastus. (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. Aikatauluteoria. Rautatiesuunnittelun ongelmat . M.: IPU RAN, 2012. 92 s. ISBN 978-5-91450-102-7 .
Brucker P. Aikataulutusalgoritmit . Heidelberg, Springer. Viides painos. ISBN 978-3-540-24804-0 (virallinen julkaisu julkaisijan portaalissa).
Peter Bruckerin aikataulutusalgoritmit . Heidelberg, Springer. Viides painos. ISBN 978-3-540-24804-0 Arkistoitu 21. helmikuuta 2016 Wayback Machinessa

Suosituimmat tieteelliset julkaisut

Shkurba V. V. " Kolmen koneen ongelma ." — M.: Nauka, 1976. — 96 s., kuvitus.