Enkeltmaskinsproblemene

Enkeltmaskinsproblemene er en gruppe optimeringsproblemer der et sett av oppgaver skal planlegges og gjennomføres på en enkelt maskin uten avbrudd. Hver oppgave j har behandlingslengden p_j, og oppgavene kan ha release-datoer r_j, utrettede krav som due dates og/eller vekter w_j. Målet er å velge rekkefølgen og starttidene for oppgavene slik at et eller flere ytelsesmål minimeres, for eksempel makespan C_max (tiden til siste ferdige jobb), total sluttid Σ C_j eller totalvektet sluttid Σ w_j C_j. Andre mål inkluderer maksimal latenhet L_max og totalt tardiness Σ T_j.

I klassiske tilfeller uten release-datoer (r_j = 0) finnes det enkle optimale regler for enkelte mål. For 1||Σ C_j er SPT-regelen (Shortest Processing Time) å foretrekke: sortering av oppgavene etter p_j i stigende rekkefølge gir optimal løsning. For 1||Σ w_j C_j er regelen WSPT (Weighted Shortest Processing Time), altså sortering etter p_j / w_j i stigende rekkefølge, som gir optimal løsning når det ikke er release-datoer.

Når release-datoer eller andre krav legges til blir mange av disse problemene NP-hard. Eksakte løsninger er derfor vanligvis begrenset til små instanser eller spesialtilfeller, mens praksisløsnin-ger ofte benytter heuristikker, metaheuristikker eller dynamisk programmering i avgrensede scenarier. Enkeltmaskinsproblemene utgjør et grunnleggende område innen operasjonsforskning og produksjonsplanlegging.