Flow shop aikataulutus on klassinen optimointiongelma, joka syntyy valmistusympäristöissä, joissa joukko työpaikkoja on käsiteltävä sarjassa koneita kiinteässä järjestyksessä. Tavoitteena on määrittää sekvenssi työpaikkojen kautta myymälän lattian minimoida mittarit kuten Makepan (kokonaisvalmistumisaika), kokonais joutokäyntiaika, tai korvanjälkeisyys / viive rangaistusten. Real-world flow shop ongelmia usein kymmeniä työperheitä, koneen hajonta, asennusajat, ja kausittainen kysynnän vaihtelut. Tehdä niistä erittäin vaikea ratkaista perinteisillä optimointimenetelmillä. Rajoittava ohjelmointi (CP) on osoittautunut tehokas tekniikka käsitellä näitä kombinatorisia haasteita.

Flow Shop -aikataulun ymmärtäminen

Klassisessa virtausmyymälässä jokainen työ on käsiteltävä konesarjassa samassa järjestyksessä. Esimerkiksi työ 1 on mentävä koneen A, sitten B, sitten C, ja samoin kaikissa muissa tehtävissä. Koneet eivät voi käsitellä kahta työpaikkaa samanaikaisesti, ja jokainen toimenpide on tunnettu käsittelyaika. Päätös ongelma on löytää permutation työpaikkoja (tai sekvenssi) joka minimoi valitun tavoitteen. Jopa pieni lisäys työpaikkojen tai koneiden johtaa kombinatoriaalinen räjähdys. Permutation virtaus shop ongelma (PFSP) kanssa Makpan minimointi on NP-hard, mikä tarkoittaa, että tarkat algoritmit tulevat epäkäytännöllisiä suuria tapauksia.

Virtauskaupan ongelmat

  • Työt ovat samat joka koneessa.
  • Hybridin virtausmyymälä: [] Useita rinnakkaiskoneita on joka vaiheessa.
  • Lämmitysvirtamyymälä:[ Koneet voidaan käyttää eri toimintoihin lisäämällä reititysjoustavuutta.
  • Ei-odotus virtausmyymälä: [) Työn käsittelyn on oltava jatkuvaa, ilman odotusta koneiden välillä.

Jokainen vaihtoehto sisältää uusia rajoituksia, jotka on täytettävä, jolloin rajoitteista tehtävä mallinnuskehys, koska rajoituksia voidaan lisätä tai poistaa ilman koko lähestymistavan uudelleenjärjestelyä.

Mikä on Contraint-ohjelmointi?

Rajoitusohjelmointi on paradigma ratkaista kombinatorisia ongelmia ilmoittamalla selkeästi rajoitteita, jotka on pidettävä. CP malli koostuu muuttujista (rajallinen tai ääretön verkkotunnukset) ja joukko rajoituksia, jotka rajoittavat mahdollisia arvo yhdistelmiä. Ratkaisija käyttää lisäysalgoritmit vähentää ala-alueita ja etsiä heuristics tutkia ratkaisu tilaa. Toisin kuin perinteinen kokonaisluku ohjelmointi, CP excels kun rajoitteet ovat monimutkaisia tai ei-lineaarisia, kuten kaikki-erilaisia, kumulatiivisia, tai sekvenssi-riippuvainen asetusajat.

Aikataulussa CP-mallit käyttävät tyypillisesti välipäätöksen muuttujia kunkin operaation alku, loppu ja kesto. Ratkaisija soveltaa sitten rajoitteiden lisäys varmistaa, että kaksi toimintaa samassa koneessa päällekkäisiä, että toiminta on työtä ensisijaisesti, ja että resurssikapasiteetti ei ylity.

Rajoituksen ohjelmointi Flow Shop Scheduling

CP:n vahvuus on sen kyky yhdistää heterogeenisiä rajoitteita. Virtausliikettä mallinnettaessa määritellään seuraavat komponentit:

Muuttujat ja verkkoalueet

  • Job sekvenssimuuttujat: Päätä suhteellinen järjestys työpaikkoja (usein edustaa kokonaisluku muuttujia position tai permutation).
  • Toimintavälit:[ Jokainen toimenpide on aikavälimuuttuja, jonka alku, loppu ja pituus (käsittelyaika).
  • Magine resources:[ Yksipuolinen resurssi (tai kumulatiivinen rinnakkaiskoneiden osalta), joka ei takaa päällekkäisyyttä.

Ydinrajoitteet

  • Edelläolorajoitukset:[] Jokaisessa työssä on tehtävä kaikki toiminnot ennen i+1:n käyttöönottoa.
  • Matkakapasiteettirajoitukset: Ei kahta toimintoa voida käsitellä samalla koneella samanaikaisesti.
  • Kaikki eri rajoitteet:[] Permutaatiovirtausmyymälöissä kunkin koneen tilausmuuttujan on oltava 1...n permutaatio.
  • Lisärajoitukset:[] Julkaisupäivät, eräpäivät, asennusajat ja huoltoikkunat voidaan helposti lisätä.

Objektiivinen toiminto

Yleisin tavoite on maskanin minimointi (Cmax). CP voi kuitenkin optimoida kokonaispainotetun viivyttelyn, joutokäynnin tai minkä tahansa mukautetun metrisen. Ratkaisija tukee erilaisia hakustrategioita: haara- ja-sidonnainen, verkkotunnuksen jakaminen tai suuri naapuruston etsintä (LNS).

Ratkaistaan prosessi CP Solversin kanssa

Nykyaikaisen CP-ratkaisijan (esim. IBM ILOG CP Optimizer, Google OR-Tools tai Choco) käyttöön kuuluu seuraavat vaiheet:

  1. Mallimuoto: Käännä virtausliike päätöksen muuttujiksi ja rajoitteiksi.
  2. Konstruktiolisäys:[] Ratkaisija vähentää automaattisesti verkkotunnuksia päättelemällä rajoitteista.
  3. Etsi:[ Hakustrategia (esim. . . . . . first-fail.) valitsee muuttujan ja määrittää arvon; lisäys toistuu.
  4. Takaisin:[ Jos umpikuja saavutetaan, ratkaisija perääntyy ja kokeilee vaihtoehtoisia arvoja.
  5. Optimointi:[ Kun toteuttamiskelpoinen ratkaisu löytyy, ratkaisija jatkaa etsimistään parempia ratkaisuja kunnes optimaalinen on todistettu.

Tämä lähestymistapa löytää usein hyviä ratkaisuja nopeasti, jopa suurissa tapauksissa, koska lisäys luumut suuria alueita hakutilaa.

Rajoituksen ohjelmasuunnittelun edut

Rajoitettu ohjelmointi tarjoaa useita erillisiä etuja virtausliikkeiden aikatauluttamiseen:

  • Vaikutus:[ Kompleksiset reaalimaailman rajoitteet (esim. sekvenssiriippuvat asetusajat, työvuorosäännöt) voidaan luonnollisesti mallintaa ilman lineaarisoimistemppuja.
  • Incremental releases:[] Kun olosuhteet muuttuvat (kone hajoaa), malli voidaan korjata uusilla rajoitteilla ja ratkaisija voi käyttää aiempia hakutietoja uudelleen.
  • Robustness to scale:[] Vaikka CP ei takaa polynomiaikaa, se suomut paljon paremmin kuin raaka-aine-force-lukumäärä ja usein ylittää MILP voimakkaasti rajoitettuja ongelmia.
  • Monien tavoitteiden käsittely:[ CP pystyy käsittelemään leksikografisia tai painotettuja kokonaistavoitteita, ja Pareto etuetsintä on mahdollista useilla ajoilla.
  • Integraatio heuristisiin menetelmiin:[) Suuri lähiöhaku, jossa CP:tä käytetään tutkimaan heuristiikan luomaa aluetta, tuottaa erinomaisia ratkaisuja hyvin suuriin tapauksiin.

Reaalimaailman sovellukset

Monet toimialat ovat ottaneet onnistuneesti käyttöön CP-pohjaisia aikataulujärjestelmiä:

Autojen kokoonpano

Autojen kokoonpanossa yli 100 työpaikkaa saattaa joutua kulkemaan hitsaus-, maalaus- ja loppukokoonpanoasemien läpi. Rajoituksia ovat värien vaihtokustannukset ja työkalut. CP-malli voi luoda aikataulun, joka lyhentää asennusaikaa 20-30% ja täyttää eräpäivät.

Semiconductor Manufacturing

Kiekkovalmistus käsittää satoja toimintoja kalliilla koneilla. CP käsittelee panostusta, reentranttia ja tiukkoja puhtaan tilan rajoituksia. Tällä alalla käytetään yrityksiä kuten IBM ja ]Google OR-työkaluja[.

Terveydenhuollon aikataulu

Sairaalat aikataulu leikkauksia eri leikkaussaleissa, toipumislaiturit, ja erikoistuneet joukkueet. CP auttaa minimoimaan potilaan odotusajat ja maksimoimaan resurssien käyttöä kunnioittaen kirurgin saatavuus ja instrumentti sterilointi syklit.

Logistiikka ja varastonhoito

Tilauksen keräily, pakkaaminen ja toimitus jakelukeskuksissa voidaan mallintaa virtausmyymäläksi. CP varmistaa, että tilaukset käsitellään järjestyksessä, joka minimoi matka-ajan ja ruuhkat.

Haasteet ja tulevaisuuden linjaukset

Voimastaan huolimatta rajoiteohjelmointi kohtaa haasteita. Hyvin suurissa tapauksissa (satoja työpaikkoja, kymmeniä koneita), CP voi silti vaatia pitkiä ajoaikoja. Hybridilähestymistavat ja sekamuotoinen lineaarinen ohjelmointi (MILP) tai metaheuristics ovat aktiivisen tutkimuksen aloja. Toinen suuntaus on käyttää [ koneoppimista, jotta haku heuristicst, parantaa nopeutta löytää lähes optimaalisia ratkaisuja.

Lisäksi pilvipalvelujen lisääntyminen mahdollistaa CP-mallien ratkaisemisen hajautetuissa järjestelmissä ja lisää niiden skaalaamista reaaliaikaisiin aikatauluvaatimuksiin. IoT- ja digitaalikaksosten integrointi tarkoittaa, että rajoitteet voidaan päivittää dynaamisesti kauppalattiadatavirtana.

Päätelmät

Rajoitettu ohjelmointi on kypsä mutta kehittyvä lähestymistapa virtaus shop aikataulut. Antamalla toimijoille mahdollisuuden keskittyä siihen, mikä on ongelma eikä miten ratkaista se, CP tuottaa vankat, joustavat ja usein optimaaliset aikataulut. Laskuvoimavarojen kasvaessa ja ratkaisija teknologian kehityksen, CP on edelleen kulmakivi operatiivisen huippuosaamisen valmistus ja sen jälkeen. Organisaatiot, jotka ottavat CP voi odottaa lyhennettyjä toimitusaikoja, alhaisemmat kustannukset, ja parantaa on-time toimitus.