In this paper we study a scheduling problem with duo-processor tasks, that is tasks simultaneously requiring two dedicated processors for their execution. No precedence constraints exist between tasks and that task preemption is not allowed. The objective is to find a schedule which minimizes the maximum completion time. We show that the instances with up to four processors can be solved in polynomial time. Moreover, we prove that the problem with 2s + 1 (for s = 2, 3, ...) processors is NP-hard. An approximation results for particular cases of the duo-processor tasks scheduling problem with 2s + 1 processors is given.
Dell'Olmo, P., Giordani, S., Speranza, M. (1997). Graph Models for a Duo-Processor Task Scheduling Problem. In Operations Research Proceedings 1996 (pp.186-191). Springer-Verlag.
Graph Models for a Duo-Processor Task Scheduling Problem
GIORDANI, STEFANO;
1997-01-01
Abstract
In this paper we study a scheduling problem with duo-processor tasks, that is tasks simultaneously requiring two dedicated processors for their execution. No precedence constraints exist between tasks and that task preemption is not allowed. The objective is to find a schedule which minimizes the maximum completion time. We show that the instances with up to four processors can be solved in polynomial time. Moreover, we prove that the problem with 2s + 1 (for s = 2, 3, ...) processors is NP-hard. An approximation results for particular cases of the duo-processor tasks scheduling problem with 2s + 1 processors is given.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
