Abstrakt. Schemaläggning en sekvens av jobb som släpps över tid när behandlingstiden för ett jobb bara är känd vid dess slutförande är ett klassiskt problem i CPU schemaläggning i time sharing operativsystem. En allmänt använd åtgärd för systemets lyhördhet är den genomsnittliga flödestiden för jobben, dvs. den genomsnittliga tid som arbetstillfällen tillbringar i systemet mellan frigörandet och slutförandet. Riktlinjerna för schemaläggning av operativsystemet Windows NT och Unix baseras på multilevel Response-algoritmen. I den här artikeln visar vi att en randomiserad version av multilevel Feedback algoritm är konkurrenskraftig för enstaka och parallella maskinsystem, enligt vår mening ger en teoretisk validering av godheten i en idé som har visat sig effektiv i praktiken under de senaste två decennierna. Den randomiserade multilevel Feedback algoritm (RMLF) först föreslogs av Kalyanasundaram och Pruhs för en enda maskin som uppnår ett O (log n log n) konkurrenskraftigt förhållande för att minimera den genomsnittliga flödestiden mot on-line adaptive motståndare, där n är antalet jobb som släpps. Vi presenterar en version av RMLF som arbetar för ett antal m parallella maskiner. Vi visar för RMLF en första O(log n log n m ) konkurrenskraft resultat mot den glömska motståndaren på parallella maskiner. Vi visar också att samma RMLF algoritm överraskande uppnår en tight O (log n) konkurrensförhållande mot den glömska motståndaren på en enda maskin, därför matchar den nedre gränsen för detta fall.
Becchetti och Leonardi REF förbättrade konkurrensförhållandet mellan Rmlf och O(log n) när motståndaren är omedveten, vilket motsvarar den nedre gränsen i detta fall.
Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}