Um estudo sobre problemas de escalonamento de tarefas com atrasos de comunicação de valores extremos

Abstract

Esta dissertação de mestrado apresenta um estudo sobre problemas de escalonamento de tarefas com atrasos de comunicação. Mais precisamente, são abordados problemas de escalonar um conjunto de tarefas em um conjunto de máquinas paralelas de número limitado ou não, e tarefas de tempo de processamento unitário, sujeitas a relações de precedência, e com atrasos de comunicação estabelecidos para cada par de tarefas precedentes, assumindo valores extremos, ou seja, podendo ser desprezíveis ou infinitamente grandes, isto com o objetivo de minimizaro o tempo em que a última tarefa escalonada termina seu processamento - minimização do makespan. Sendo assim, dois problemas são demostrados serem da classe NP-difícil. Para o primeiro, a quantidade de processadores é indicada a cada instância, sendo este resultado válido ainda que as relações de precedência formem um conjunto de cadeias (P|chains; cij ∈ {0, ∞}; pj = 1|Cmax). O segundo problema admite relações de precedência arbitrárias e é válido para qualquer quantidade fixa de processadores diferente de um (P2|prec;cij ∈ {0, ∞}; pj = 1|Cmax). Por outro lado, neste trabalho, dois outros problemas são demonstrados serem solúveis em tempo polinomial, ou seja, estarem na classe P, ambos quando uma quantidade ilimitada de processadores está disponível. É visto que, se a ordem de precedência das tarefas é limitada a uma árvore descendente, o problema é polinomial (P∞|tree; cij ∈ {0, ∞}; pj = 1|Cmax). O outro caso polinomial demonstrado é válido quando é permitido processar a mesma tarefa em mais de um processador (P∞|prec; cij ∈ {0, ∞}; pj = 1|Cmax). Para ambos os casos são apresentados os algoritmos polinomiais. Finalmente, são apresentados resultados para o problema de escalonar tarefas particionadas em conjuntos para os quais todas as tarefas devem ser processadas no mesmo processador. O problema é NP-difícil quando a quantidade de processadores é determinada a cada instância. Esse resultado é válido ainda que a precedência seja restrita a duas cadeias. O problema se torna polinomial quando o conjunto de partições é limitado por constante e as cadeias são restritas em uma das duas formas: pela quantidade delas ou pela quantidade de tarefas em cada uma delas. Como trabalho futuro, este estudo deixa em aberto a NP-Completude do problema de escalonar sob tais atrasos de comunicação de valores extremos, para uma quantidade fixa de processadores, quando a ordem de precedência é de alguma forma restrita, por exemplo, uma árvore descendente (Pm|out-tree;cij ∈ {0, ∞}; pj = 1|Cmax).

This Master’s Thesis presents a study on scheduling problems subject to communication delays. More precisely, this work involves job scheduling problems with a number of parallel machines, limited or not, and where the tasks (or jobs) have unit execution time, and are subject to some precedence relation. Communication delays are imposed at each pair of preceding tasks, taking extreme values, which may be negligible or infinitely large. The objective is minimize the completion time of the latest job to be processed, that is, to get the minimum makespan. Thus, NP-hard results are demonstrated for two cases. For the first, when the number of processors is indicated in the instance of the problem, and this result holds even when the precedence relation is restricted to a set of chains (P|chains; cij ∈ {0, ∞}; pj = 1|Cmax). The second results is valid when arbitrary precedence relations are allowed, and any fixed number of processors (greater than one) is available (P2|prec;cij ∈ {0, ∞}; pj = 1|Cmax). Two other problems are demonstrated to have polynomial time solutions, both when an unlimited number of processors are available. The first result imposes the precedence relation to be an out-tree (P∞|tree; cij ∈ {0, ∞}; pj = 1|Cmax). The second result is valid when the execution of the same job on multiples processors are allowed (P∞|prec; cij ∈ {0, ∞}; pj = 1|Cmax). For both cases, polynomial algorithms are presented. Finally, results are presented for the problem of job scheduling that are partitioned in sets which must be executed on the same processors. The problem is demonstrated to be NP-hard even if the precedence relation consists of two chains. Also, it is shown that the problem becomes solvable in polynomial time if the number of partitions is limited by a constant and the chains are restricted by a constant on either their number, or the number of tasks that each chain may have. As future work, this study leaves open whether is NP-hard the case to schedule tasks subject to such communication delays with extreme values, when a fixed number of processors is available, and the precedence relations are some how restricted, for example, by an out-tree (Pm|out-tree;cij ∈ {0, ∞}; pj = 1|Cmax).