Tuotantolinjan suunnitteluongelma

Vuokaupan ajoitusongelma tai permutaatiovuokaupan ajoitus [ 1 ] on kombinatorinen ajoitusongelma .

Määritelmä

Vaatimukset ja koneet niiden käsittelyyn on annettu. Seuraavat rajoitukset asetetaan: $n$ $m$

kaikki pyynnöt on käsiteltävä peräkkäin kaikissa koneissa 1. - -th; $m$
mikä tahansa kone voi käsitellä vain yhden pyynnön kerrallaan.
keskeytykset eivät ole sallittuja huoltovaatimuksissa ja siksi ratkaisu määräytyy jonkin vaatimusten permutaatiolla.

Jokaisen asiakkaan huoltoaika kussakin koneessa on annettu matriisin avulla . Matriisin elementti on koneen vaatimuksen huoltoaika . $M_{nm}(\mathbb {R} ^{+})$ $p_{{ij}}$ $i$ $j$

Seuraavat tavoitefunktiot otetaan yleensä huomioon:

${\displaystyle C_{max))$ , viimeisen asiakkaan palvelun päättymisaika koneella tai kokonaispalveluaika; $m$
$\Sigma _{i=1}^{n}c_{i}$ , koneen huoltopyyntöjen päättymisaikojen summa . $m$

Minimointialgoritmit ${\displaystyle C_{max))$

Algoritmi kahdelle koneelle

Ongelman ratkaisemiseksi kahdella koneella löydettiin polynomiaikainen Johnson-algoritmi [2] : vaatimukset on jaettu kahteen joukkoon ja lisäksi: $U=\{i:p_{i1}<p_{i2}\}$ $V=\{i:p_{i1}\geq p_{i2}\}$

vaatimukset on lajiteltu ei-laskevaan järjestykseen , $U$ ${\displaystyle p_{i1))$
vaatimukset on lajiteltu ei-nousevaan järjestykseen , $V$ ${\displaystyle p_{i2))$
optimaalinen järjestys on ketjutus ja järjestys tällä tavalla . $U$ $V$

Algoritmilla on aika monimutkaisuus , koska se käyttää lajittelualgoritmia. $n\log(n)$

Algoritmit kolmelle tai useammalle koneelle

Useamman kuin kahden koneen tapauksessa tämä ongelma on NP-kova , mutta monia heuristisia aikapolynomiapproksimaatioalgoritmeja on kehitetty [3] .

NEH-heuristinen

Yksi tunnetuimmista algoritmeista on Nawazin, Enscoren ja Hamin heuristiikka ( Nawaz , Enscore , Ham ) [4] :

vaatimukset on järjestetty ja numeroitu tämän järjestyksen mukaan, ${\displaystyle \sum _{j=1}^{m}p_{ij))$
kahden ensimmäisen vaatimuksen palvelujärjestys määritetään siten, että niiden palveluaika on mahdollisimman pieni,
enintään : _ $i=3$ $n$
- vaatimus asetetaan kohtaan , joka minimoi ensimmäisten vaatimusten kokonaispalveluajan $i$ $k\in [1,i]$ $i$
(syklin loppu)

Campbellin, Dudekin ja Smithin heuristiikka

Tunnetaan myös Campbellin, Dudekin ja Smithin heuristiikka ( Campbell , Dudek , Smith ), jossa koneiden ongelma on peräkkäin pelkistetty 2 koneen ongelmaksi [5] ja jokainen niistä ratkaistaan Johnson-algoritmilla. $m$ $m-1$

Muistiinpanot

↑ Permutaatio flowshop -ongelma . Haettu 22. huhtikuuta 2013. Arkistoitu alkuperäisestä 6. toukokuuta 2021. (määrätön)
↑ SM Johnson, Optimaaliset kaksi- ja kolmivaiheiset tuotantoaikataulut asennusajat mukaan lukien, Naval Res. Hirsi. Quart. I(1954) 61-68.
↑ Kattava katsaus ja arviointi permutaatiovirtakaupan heuristiikasta
↑ [1] Heuristinen algoritmi m-kone, n-job flow-shop sekvensointiongelmalle
↑ Luku_4, Flow Shop Scheduling (downlink) . Haettu 22. huhtikuuta 2013. Arkistoitu alkuperäisestä 21. lokakuuta 2014. (määrätön)