Arbetsflödet tillfredsställande problem (WSP) är ett problem av praktiskt intresse som uppstår när uppgifter måste utföras av auktoriserade användare, med förbehåll för begränsningar som definieras av affärsregler. Vi är skyldiga att besluta om det finns en plan - en tilldelning av uppgifter till auktoriserade användare - så att alla begränsningar är uppfyllda. Flera skräddarsydda algoritmer har konstruerats för att lösa WSP, optimerade för att hantera begränsningar (affärsregler) av vissa typer. Det är naturligt att se WSP som en underklass tillfredsställande problem (CSP) där variablerna är uppgifter och domänen är uppsättningen användare. Vad som gör WSP distinkt som en CSP är att vi kan anta att antalet uppgifter är mycket liten jämfört med antalet användare. Detta står i skarp kontrast till traditionella CSP-modeller där domänen är liten och antalet variabler är mycket stort. Som sådan, är det lämpligt att fråga för vilka begränsningar språk WSP är fast-parameter dragbar (FPT), parameteriserad av antalet uppgifter. Detta nya tillvägagångssätt till WSP, med hjälp av tekniker för CSP, har gjort det möjligt för oss att generalisera och förena befintliga algoritmer. I stället för att överväga algoritmer för specifika begränsningar utformar vi en generisk algoritm som är en fast parameteralgoritm för flera familjer av arbetsflödesbegränsningar som beaktas i litteraturen. Vi har identifierat ett nytt FPT-begränsningsspråk, användaroberoende begränsning, som inkluderar många av de begränsningar av intresset för affärshanteringssystem. Vi kan också bevisa att unionen av FPT språk förblir FPT om de uppfyller en enkel kompatibilitet villkor. I detta dokument presenterar vi vår generiska algoritm, där planer grupperas i ekvivalensklasser, där varje klass förknippas med ett mönster. Vi visar att vår generiska algoritm har körtid O * (2 k log k ), där k är antalet uppgifter, för språket av användaroberoende begränsningar. Vi visar också att det inte finns någon algoritm för körtid O * (2 o(k log k) ) för användaroberoende begränsningar om inte Exponential Time Hypotesen misslyckas.
Cohen m.fl. REF tillämpar tekniker från CSP till Workflow Satisfiability Problem (WSP)-det vill säga att avgöra om en plan för assing uppgift till auktoriserade användare i en viss affärsprocess.
Iterative Plan Construction for the Workflow Satisfiability Problem
{'venue': 'Journal of Artificial Intelligence Research 51 (2014), pp.555-577', 'journal': None, 'mag_field_of_study': ['Computer Science']}