We consider energy minimization by speed-scaling of an open shop multiprocessor with n jobs and m machines. The paper studies the complexity of a primal-dual solution algorithm of [4], which was an open question in that paper.We prove that in a neighbourhood of the solution the complexity of the algorithm is O(mn log(1/ε) if n and m are not equal and ε is the roundoff error of the computer. The paper demonstrates how linearization can be used to investigate the complexity of an algorithm close to the optimum. An estimate of the size of the neighbourhood where the linearization error is smaller than the computer’s roundoff error is also given.

Pappret undersöker en energiminimiseringsalgoritm för en multiprocessor där processorns hastighet kan lokalt varieras för att minimera energin. För en open shop multiprocessor med n tasks och m maskiner studeras effektiviteten för en nyligen publicerad primal-dual algoritm. Nära optimium är dess komplexitet O(mn log(1/ε)) om n och m inte är lika och ε är datorns avrundningsfel. I pappret demonstreras hur linjarisering kan användas för att undersöka en algoritms komplexitet nära optimum. Vi visare också en uppskattning storleken för det område runt optimum där linjariseringsfelet är mindre än datorns avrundningsfel.