Åpen butikk planlegging - Open-shop scheduling
Open-shop scheduling eller open-shop scheduling problem ( OSSP ) er et optimaliseringsproblem innen informatikk og driftsforskning . Det er en variant av optimal jobbplanlegging . I et generelt jobbplanleggingsproblem får vi n jobber J 1 , J 2 , ..., J n av varierende behandlingstider, som må planlegges på m maskiner med varierende prosessorkraft, mens vi prøver å minimere fabrikken - den totale lengden på timeplanen (det vil si når alle jobbene er ferdigbehandlet). I den spesifikke varianten kjent som åpen butikkplanlegging , består hver jobb av et sett med operasjoner O 1 , O 2 , ..., O n som må behandles i en vilkårlig rekkefølge. Problemet ble først studert av Teofilo F. Gonzalez og Sartaj Sahni i 1976.
I standard trefeltnotasjon for optimale jobbplanleggingsproblemer , er open-shop-varianten betegnet med O i det første feltet. For eksempel er problemet betegnet med " O3 | | " et 3-maskins jobb-butikk-problem med enhetens behandlingstid, hvor målet er å minimere maksimal fullføringstid.
Definisjon
Inndataene til planleggingsproblemet for åpen butikk består av et sett med n jobber, et annet sett med m arbeidsstasjoner og en todimensjonal tabell over hvor lang tid hver jobb skal bruke på hver arbeidsstasjon (muligens null). Hver jobb kan bare behandles på en arbeidsstasjon om gangen, og hver arbeidsstasjon kan bare behandle en jobb om gangen. Imidlertid, i motsetning til job-shop-problemet , kan rekkefølgen behandlingsstrinnene skje variere fritt. Målet er å tildele en tid for hver jobb som skal behandles av hver arbeidsstasjon, slik at ikke to jobber tildeles til samme arbeidsstasjon samtidig, ingen jobb tildeles to arbeidsstasjoner samtidig, og hver jobb tildeles til hver arbeidsstasjon for ønsket tid. Det vanlige målet for kvaliteten på en løsning er dens fabrikant , hvor lang tid det tar fra start av planen (den første tildelingen av en jobb til en arbeidsstasjon) til slutten (sluttidspunktet for den siste jobben på den siste arbeidsstasjonen).
Beregningskompleksitet
Planleggingsproblemet med åpen butikk kan løses i polynomial tid for tilfeller som bare har to arbeidsstasjoner eller bare to jobber. Det kan også løses i polynomisk tid når alle behandlingstider som ikke er null er like: i dette tilfellet blir problemet ekvivalent med kantfarging av en todelt graf som har jobbene og arbeidsstasjonene som sine hjørner, og som har en kant for hvert jobb-arbeidsstasjonspar som ikke har null behandlingstid. Fargen på en kant i fargeleggingen tilsvarer det tidssegmentet der et jobb-arbeidsstasjonspar er planlagt behandlet. Fordi linjegrafene til tosidige grafer er perfekte grafer , kan todelte grafer være kantfarget på polynomisk tid.
For tre eller flere arbeidsstasjoner, eller tre eller flere jobber, med varierende behandlingstider, er åpen butikkplanlegging NP-vanskelig .
Relaterte problemer
- Jobbbutikkplanlegging er et lignende problem, men med en ytterligere begrensning - operasjonene må gjøres i en bestemt rekkefølge.
- Flow-shop planlegging er en jobb-butikk planlegging, men med en ekstra flyt begrensning - hver operasjon må gjøres på en bestemt maskin.