Vi tar itu med problemet med att schemalägga en uppsättning generiska uppgifter som ska utföras i nitely ofta utan företräde på nästan många parallella processorer. Dessa uppgifter är föremål för en uppsättning enhetliga begränsningar, modellerade av en enhetlig graf G. Problemet är att nd ett periodiskt schema som minimerar cykeltiden. Även om problemet är NPhard, visar vi att specialfallet där G är en krets kan lösas i polynom tid. Vi studerar sedan strukturen av uppsättningen av lösningar i det allmänna fallet och bestämma flera dominerande undergrupper av scheman genom att analysera den periodiska strukturen av tilldelningsfunktionen och de inducerade enhetliga begränsningar på schemat. I synnerhet bevisar vi dominansen av cirkulär scheman, där förekomsten av någon uppgift successivt utförs av alla processorer. Slutligen föreslår vi en girig heurist som ger ett bra cirkulärt schema.
Om antalet processorer inte är begränsat, kan ett periodiskt schema byggas i polynom tid REF.
A Study of the Cyclic Scheduling Problem on Parallel Processors
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}