A single processor must perform a set of jobs on a planning time horizon subdivided into an infinite number of discrete time instants. At each instant of the discrete planning time horizon, each job will require from the processor a quantity of the processing resource represented by one of the translations of a non-negative discrete time periodic function. The objective is the determination of the phases of these periodic functions so that the maximum of the sum of such functions is minimized over the time. This problem is formulated as a minimax integer programming problem, and a set of heuristic algorithms is proposed. An experimental analysis of their performance is also given.
A multiperiod single processor scheduling problem with periodic job requirements
PALETTA, Giuseppe
2006-01-01
Abstract
A single processor must perform a set of jobs on a planning time horizon subdivided into an infinite number of discrete time instants. At each instant of the discrete planning time horizon, each job will require from the processor a quantity of the processing resource represented by one of the translations of a non-negative discrete time periodic function. The objective is the determination of the phases of these periodic functions so that the maximum of the sum of such functions is minimized over the time. This problem is formulated as a minimax integer programming problem, and a set of heuristic algorithms is proposed. An experimental analysis of their performance is also given.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
