Edge-finding algoritmer för kumulativ schemaläggning är kärnan i kommersiella begränsningar-baserade schemaläggare. Detta dokument visar att Nuijten's kant finder för kumulativ schemaläggning, och dess derivat, är ofullständiga och använder en ogiltig dominans regel. I dokumentet presenteras sedan en ny edgefinding-algoritm för kumulativa resurser som körs i tid O(n 2 k), där n är antalet uppgifter och k antalet olika kapacitetskrav för uppgifterna. Den nya algoritmen är organiserad i två faser och använder först dynamisk programmering för att förkompilera den innersta maximeringen i egg-finder specifikationen. Slutligen föreslås i detta dokument också den första utökade edge-finding algoritm som körs i tid O(n 2 k), förbättra körtiden för tillgängliga algoritmer.
I REF föreslås en tvåfasalgoritm för utökad kantsökning, som kör O kn 2 tid och använder O (kn) utrymme.
Edge finding for cumulative scheduling
{'venue': 'INFORMS Journal on Computing', 'journal': None, 'mag_field_of_study': ['Computer Science']}