Abstrakt. I den här artikeln visar vi hur det klassiska schemaläggningsproblemet kan modelleras som en speciell klass av acyklisk tidsinställd automata. Att hitta ett optimalt schema motsvarar alltså en kortaste (i termer av förfluten tid) väg i tidsinställd automaton. Denna representation ger nya tekniker för att lösa optimeringsproblemet och, ännu viktigare, gör det möjligt att modellera naturligt mer komplexa dynamiska resursfördelningsproblem som inte fångas så lätt i traditionella modeller för drift forskning. Vi presenterar flera algoritmer och heuristiker för nding de kortaste vägarna i tidsinställda automata och testar deras implementering i verktyget Kronos på många referensexempel.
I REF visas att hitta ett optimalt schema för en arbetsplatsoptimering problem motsvarar att hitta en kortaste vägen i en viss typ av acyklisk tidsinställd automata.
Job-Shop Scheduling Using Timed Automata
{'venue': 'CAV', 'journal': None, 'mag_field_of_study': ['Computer Science']}