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).

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).

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).

[pt] Esta dissertação investiga o uso de Algoritmos Genéticos e de Co-Evolução Cooperativa na otimização de problemas de planejamento com restrições de precedência. Neste tipo de problema algumas ou todas as tarefas têm restrições que implicam na necessidade de planejá-las ou executá-las antes ou depois de outras. Por esta razão, o uso de modelos evolucionários convencionais como, por exemplo, os baseados em ordem pode gerar soluções inválidas, não penalizáveis, que precisam ser descartadas, comprometendo assim o desempenho do algoritmo. O objetivo do trabalho foi, portanto, estudar formas de representação de soluções para este tipo de problema capazes de gerar somente soluções válidas, bem como avaliar o desempenho dos modelos propostos. O trabalho consistiu de 3 etapas principais: um estudo sobre problemas de otimização de planejamento com algoritmos genéticos; a definição de novos modelos usando algoritmos genéticos e co-evolução cooperativa para otimização de problemas de planejamento com restrições de precedência e a implementação de uma ferramenta para estudo de caso. O estudo sobre os problemas de otimização de planejamentos com algoritmos genéticos envolveu o levantamento de representações, dificuldades e características deste tipo de problema e, mais especificamente, de representações baseadas em ordem. A modelagem do algoritmo genético consistiu fundamentalmente na definição de uma representação dos cromossomas e da função da avaliação que levasse em conta a existência de restrições de precedência (tarefas que devem ser planejadas/executadas antes de outras). A construção do modelo co-evolucionário por sua vez consistiu em definir uma nova população, com uma outra representação, que se responsabilizasse pela distribuição dos recursos para execução das tarefas, responsabilidade esta que, no modelo com algoritmos genéticos convencionais, era tratada de forma simples por um conjunto de heurísticas. Finalmente, desenvolveu-se uma ferramenta para implementar estes modelos e tratar de um estudo de caso complexo que oferecesse as características necessárias para testar a qualidade das representações e avaliar os resultados. O estudo de caso escolhido foi a otimização do planejamento da descarga, armazenamento e embarque de minério de ferro de modo a minimizar o tempo de estadia dos navios em um porto fictício. Foram realizados vários testes que demonstraram a capacidade dos modelos desenvolvidos em gerar soluções viáveis, sem a necessidade de heurísticas de correção, e os resultados obtidos foram comparados com os de um processo de busca aleatória. Em todos os casos, os resultados obtidos pelos modelos foram sempre superiores aos obtidos pela busca aleatória. No caso do modelo de representação com uma única população obteve-se resultados até 41% melhores do que com os obtidos por uma busca aleatória. No caso do modelo de representação com co-evolução o resultado ficou 33% melhor que a busca aleatória com tratamento de solução idêntico ao da solução co-evolucionária. Os resultados da co-evolução comparados com o algoritmo genético com uma única espécie foram 29% melhores. / [en] This work investigates the use of Genetic Algorithms and Cooperative Co-Evolution in optimization of scheduling problems with precedence constraints. In this kind of problem some or all tasks have constraints that imply planning or executing them before or after others. For this reason, the use of order-based conventional evolutionary models may generate invalid solutions, which cannot be penalized, needing to be discarded and therefore compromising the algorithm performance. The main goal was therefore to study models for this kind of problem that are capable of generating only valid solutions. The work was divided in 3 main steps: a survey on scheduling optimization problems using genetic algorithms; definition of two models based on genetic algorithms and cooperative co-evolution for optimizing scheduling problems with precedence constraints; and the implementation of a tool for a case study. The study on scheduling optimization problems with genetic algorithms consisted in gathering information about representations and characteristics of this kind of problem and, more specifically, about order-based representations. The genetic algorithm modeling consisted basically in defining a chromosome representation and an evaluation function that took into account the existence of precedence constraints (tasks that must be scheduled or executed before others). The co-evolutionary model consisted in defining a new population, with another representation scheme, which was responsible for distributing resources for tasks execution. On the conventional genetic algorithm model, this role was played by a simple set of heuristics. Finally, a tool was developed for implementing those models and treating a complex case study which offered the needed characteristics for testing representation performance and evaluating results. The chosen case study was the optimization of iron ore dumping, stocking and ship loading on a fictitious harbor, targeting minimization of ships waiting time. Tests were done in order to demonstrate the ability of the developed models in generating viable solutions without the need of corrective heuristics and the results were compared to the results obtained through exhaustive search. In all cases, the models` results were better than the exhaustive search ones. In the case where the representation used a single population the results obtained were up to 41% better than the ones with the exhaustive search. The co- evolutionary results outperformed the co-evolutionary search with the same solution representation by 33%. Compared to the single specie genetic algorithm, the co- evolutionary model outperformed it by 29%.

No description available.

No description available.

Esta Tesis doctoral representa una nueva formulación del problema del GRCPSP (Generalized Resource-Constrained Project Scheduling Problem) mediante grafos PDM (Precedence Diagramming Method) con fragmentación en entornos realistas, donde las tareas son diferenciadas entre productivas y no productivas y las dependencias entre ellas no se limitan a los ya clásicos valores de dependencia, sino que se incorpora un nuevo concepto de relación de producción, apareciendo relaciones basadas en un cierto nivel de producción necesario de otra tarea para poder comenzar, o cierta producción que quedará pendiente de finalizar una vez finalizada la tarea precedente. Este nuevo enfoque del problema basado en procesos productivos, no solo elimina las paradojas causadas por las tareas críticas inversas o críticas perversas, sino que nos permite aplicar conceptos tradicionales de la planificación de la producción como es la productividad variable ocasionada por el aprendizaje con las repercusiones que esto produce en las relaciones basadas en producción. Además se analizan las naturalezas de los recursos intervinientes en el proyecto, reformulando los costes asociados a los mismos y su repercusión sobre el nuevo modelo propuesto, permitiendo la aplicación de algoritmos de optimización TCTP (Time Cost Trade-Off Problem) que hasta ahora era inviable. Para finalizar se incorpora la borrosidad a los valores intervinientes en el proyecto presentando la formulación de un modelo robusto de planificación de la producción basada en grafos PDM que sirve de punto de partida a la resolución del GRCPSP en entornos realistas. / Ponz Tienda, JL. (2010). GRCPSP Robusto basado en Producción para Proyectos de Edificación y Construcción [Tesis doctoral]. Editorial Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8540

The purpose of this research is to develop a model and solution methodology for selecting and scheduling timely and cost-effective maintenance, rehabilitation, and reconstruction activities (M & R) for each pavement section in a highway network and allocating the funding levels through a finite multi-period horizon within the constraints imposed by budget availability in each period, frequency availability of activities, and specified minimum pavement quality requirements. M & R is defined as a chronological sequence of reconstruction, rehabilitation, and major/minor maintenance, including a "do nothing" activity. A procedure is developed for selecting an M & R activity for each pavement section in each period of a specified extended planning horizon. Each activity in the sequence consumes a known amount of capital and generates a known amount of effectiveness measured in pavement quality. The effectiveness of an activity is the expected value of the overall gains in pavement quality rating due to the activity performed on a highway network over an analysis period. It is assumed that the unused portion of the budget for one period can be carried over to subsequent periods. Dynamic Programming (DP) and Branch-and-Bound (B-and-B) approaches are combined to produce a hybrid algorithm for solving the problem under consideratioin. The algorithm is essentially a DP approach in the sense that the problem is divided into smaller subproblems corresponding to each single period problem. However, the idea of fathoming partial solutions that could not lead to an optimal solution is incorporated within the algorithm to reduce storage and computational requirements in the DP frame using the B-and-B approach. The imbedded-state approach is used to reduce a multi-dimensional DP to a one-dimensional DP. For bounding at each stage, the problem is relaxed in a Lagrangean fashion so that it separates into longest-path network model subproblems. The values of the Lagrangean multipliers are found by a subgradient optimization method, while the Ford-Bellman network algorithm is employed at each iteration of the subgradient optimization procedure to solve the longest-path network problem as well as to obtain an improved lower and upper bound. If the gap between lower and upper bound is sufficiently small, then we may choose to accept the best known solutions as being sufficiently close to optimal and terminate the algorithm rather than continue to the final stage.

Many cells in the inferior colliculus (IC) are excited by contralateral and inhibited by ipsilateral stimulation and are thought to be important for sound localization. These excitatory-inhibitory (EI) cells comprise a diverse group, even though they exhibit a common binaural response property. Previous extracellular studies proposed specific excitatory and/or inhibitory events that should be evoked by each ear and thereby generate each of the EI discharge properties. The proposals were inferences based on the well established response features of neurons in lower nuclei, the projections of those nuclei, their excitatory or inhibitory neurochemistry, and the changes in response features that occurred when inhibition was blocked. Here we recorded the inputs, the postsynaptic potentials, discharges evoked by monaural and binaural signals in EI cells with in vivo whole cell recordings from the inferior colliculus (IC) of awake bats. We also computed the excitatory and inhibitory synaptic conductances from the recorded sound evoked responses. First, we showed that a minority of EI cells either inherited their binaural property from a lower binaural nucleus or the EI property was created in the IC via inhibitory projections from the ipsilateral ear, features consistent with those observed in extracellular studies. Second, we showed that in a majority of EI cells ipsilateral signals evoked subthreshold EPSPs that behaved paradoxically in that EPSP amplitudes increased with intensity, even though binaural signals with the same ipsilateral intensities generated progressively greater spike suppressions. These ipsilateral EPSPs were unexpected since they could not have been detected with extracellular recordings. These additional responses suggested that the circuitry underlying EI cells was more complex than previously suggested. We also proposed the functional significance of ipsilaterally evoked EPSPs in responding to moving sound sources or multiple sounds. Third, by computing synaptic conductances, we showed the circuitry of the EI cells was even more complicated than those suggested by PSPs, and we also evaluated how the binaural property was produced by the contralateral and ipsilateral synaptic events. / text

The purpose of this research is to develop a model and solution methodology for selecting and scheduling timely and cost-effective maintenance, rehabilitation, and reconstruction activities (M & R) for each pavement section in a highway network and allocating the funding levels through a finite multi-period horizon within the constraints imposed by budget availability in each period, frequency availability of activities, and specified minimum pavement quality requirements. M & R is defined as a chronological sequence of reconstruction, rehabilitation, and major/minor maintenance, including a "do nothing" activity. A procedure is developed for selecting an M & R activity for each pavement section in each period of a specified extended planning horizon. Each activity in the sequence consumes a known amount of capital and generates a known amount of effectiveness measured in pavement quality. The effectiveness of an activity is the expected value of the overall gains in pavement quality rating due to the activity performed on a highway network over an analysis period. It is assumed that the unused portion of the budget for one period can be carried over to subsequent periods. Dynamic Programming (DP) and Branch-and-Bound (B-and-B) approaches are combined to produce a hybrid algorithm for solving the problem under consideratioin. The algorithm is essentially a DP approach in the sense that the problem is divided into smaller subproblems corresponding to each single period problem. However, the idea of fathoming partial solutions that could not lead to an optimal solution is incorporated within the algorithm to reduce storage and computational requirements in the DP frame using the B-and-B approach. The imbedded-state approach is used to reduce a multi-dimensional DP to a one-dimensional DP. For bounding at each stage, the problem is relaxed in a Lagrangean fashion so that it separates into longest-path network model subproblems. The values of the Lagrangean multipliers are found by a subgradient optimization method, while the Ford-Bellman network algorithm is employed at each iteration of the subgradient optimization procedure to solve the longest-path network problem as well as to obtain an improved lower and upper bound. If the gap between lower and upper bound is sufficiently small, then we may choose to accept the best known solutions as being sufficiently close to optimal and terminate the algorithm rather than continue to the final stage.