No description available.

No description available.

Scheduling is concerned with the process of deciding how to commit resources between a variety of possible tasks with the aim of optimizing some performance criterion. Efficient scheduling is a vital tool in successful decision-making. To date, an enormous amount of research has been done on scheduling problems arising from various disciplines. Major attention has so far been dedicated to off-line (usually deterministic) scheduling problems. Off-line deterministic scheduling deals with perfect information. That is, all information with regard to a problem is known prior to any decision. However, this perfect information assumption violates the nature of many realistic issues with uncertainties, for example, a situation where the knowledge of problem instances is revealed over time, or a scenario in which processing tasks are temporarily disrupted or cancelled. To better formulate this sort of problem with high uncertainties, a new concept of on-line scheduling was introduced. On-line approaches have become increasingly important and are frequently encountered when only partial knowledge is available but instant or very fast solution methods are required and should nevertheless result in good outcomes. In on-line scheduling, a decision maker allocates resources between tasks as the information is gradually released. Obviously, given the same scheduling environment and problem instance, the result produced by an on-line scheduler cannot be better than that by the optimal off-line scheduler; but the on-line scheduling technique immunizes schedules from future disruptions and uncertainties. / This thesis extends the study of some scheduling problems derived from various industrial and computing situations to on-line scheduling environments, specifically the on-line-list and the on-line-time paradigms. The six topics studied are classified in two parts in this thesis. Part I consists of three machine scheduling problems taking into account various types of setup considerations. Part II includes the other three scheduling problems which are closely related to issues arising in the management of shipping containers and wind energy. / The effort is focused on constructing effective and efficient (on-line) decision-making strategies with the purpose of optimizing certain objective measures in those uncertain scheduling environments. The performance of the proposed heuristics as well as some existing on-line algorithms is evaluated and compared via competitive analysis. For some cases, empirical studies are also carried out to assess their average performance.

Scheduling is concerned with the process of deciding how to commit resources between a variety of possible tasks with the aim of optimizing some performance criterion. Efficient scheduling is a vital tool in successful decision-making. To date, an enormous amount of research has been done on scheduling problems arising from various disciplines. Major attention has so far been dedicated to off-line (usually deterministic) scheduling problems. Off-line deterministic scheduling deals with perfect information. That is, all information with regard to a problem is known prior to any decision. However, this perfect information assumption violates the nature of many realistic issues with uncertainties, for example, a situation where the knowledge of problem instances is revealed over time, or a scenario in which processing tasks are temporarily disrupted or cancelled. To better formulate this sort of problem with high uncertainties, a new concept of on-line scheduling was introduced. On-line approaches have become increasingly important and are frequently encountered when only partial knowledge is available but instant or very fast solution methods are required and should nevertheless result in good outcomes. In on-line scheduling, a decision maker allocates resources between tasks as the information is gradually released. Obviously, given the same scheduling environment and problem instance, the result produced by an on-line scheduler cannot be better than that by the optimal off-line scheduler; but the on-line scheduling technique immunizes schedules from future disruptions and uncertainties. / This thesis extends the study of some scheduling problems derived from various industrial and computing situations to on-line scheduling environments, specifically the on-line-list and the on-line-time paradigms. The six topics studied are classified in two parts in this thesis. Part I consists of three machine scheduling problems taking into account various types of setup considerations. Part II includes the other three scheduling problems which are closely related to issues arising in the management of shipping containers and wind energy. / The effort is focused on constructing effective and efficient (on-line) decision-making strategies with the purpose of optimizing certain objective measures in those uncertain scheduling environments. The performance of the proposed heuristics as well as some existing on-line algorithms is evaluated and compared via competitive analysis. For some cases, empirical studies are also carried out to assess their average performance.

This work should serve as a source of information on the issue of production scheduling. The work is particularly focused on the relatively new terms in optimization of processing of production batches area, such as flowshop and its modifications in the form of so-called hybrid flowshop. The work is divided into five chapters. The first chapter consists of an introduction. In the second chapter I mention the theory of scheduling, the third part deals with the history of flowshop and in the fourth part I check the functionality of new models on real data. In conclusion I summarize the contents of work, comment resulting calculations and deliver the practical usage of flowshop.

In the present work I compare the search strategies for solving scheduling problems from the view of constraint programming. The thesis is focused on scheduling problems containing alternative activities. An analysis of previously published various ways of modelling the problems is provided, next description and experimental comparison of search strategies targetting these models is provided. The influence of strategies on the speed of the solver is studied primarily. As a sideeffect the work studies the ways how Choco solver, which was utililized for implementation of the experiments, can be used to solve the scheduling problems with alternative activities.

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.

The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound algorithm for the multiprocessor schedulingproblem. We investigate the algorithm by comparing two different lower bounds withtheir computational costs and the size of the pruned tree.Several experiments are made with small set of problems and results are compared indifferent sections.

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-07-01Bitstream added on 2014-06-13T18:30:54Z : No. of bitstreams: 1 carretero_mm_me_sjrp.pdf: 795127 bytes, checksum: 64b07e80db6689945e91fc1c317deb3c (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Em alguns setores, o planejamento da produção envolve dois aspectos: o dimensionamento do tamanho dos lotes e a programação da produção (sequenciamento dos lotes). O primeiro problema consiste em determinar o tamanho dos lotes de produção de cada item a ser produzido em uma ou mais máquinas em cada período ao longo de um horizonte de planejamento finito. O segundo problema consiste em encontrar a ordem em que os lotes devem ser produzidos em um dado conjunto de máquinas. Estes dois aspectos do planejamento da produção podem ser tratados de forma independente: em um estágio é resolvido o problema de dimensionamento dos lotes e no outro, realizado antes ou depois, é resolvido o problema de seqüenciamento. No entanto, uma tendência recente na literatura são trabalhos que apresentam modelos matemáticos que capturam simultaneamente as relações entre os dois problemas. Na literatura pode-se encontrar modelos integrados que incluem restrições de eliminação de subrotas, propostas para o Problema do Caixeiro Viajante (PCV), para formular as restrições de sequenciamento. No entanto, alguns dos modelos propostos usam restrições de ordem polinomial que fornecem uma relaxação linear fraca. O objetivo desse trabalho é avaliar o uso de inequações válidas, propostas na literatura, para obtenção de formulações mais fortes para o problema integrado de dimensionamento e sequenciamento da produção. Resultados computacionais usando exemplares aleatórios e exemplares da literatura mostram que as reformulações propostas são eficientes para cenários em que o modelo original não é eficiente. / Often, the production planning involves the lot sizing and scheduling of items. The first problem is to determine the lot size of each item to be produced in one or more machines in each period over a finite planning horizon. The second problem is to find the order in which the items will be produced. These two aspects of the production planning can be treated independently: in one stage the lot sizing problem is solved, and in the other, that can be executed before or after, the scheduling problem is solved. A recent trend in the literature is to propose mathematical models that capture the relationships between these two problems. In the literature one can find integrated models that include subtour elimination constraints, proposed for the Traveling Salesman Problem, to formulate the scheduling decisions. However, in some of these models, constraints of polynomial order, that provides a weak linear relaxation, are used.The purpose of this study is to evaluate the use of valid inequalities proposed in the literature to obtain stronger formulations to the lot and scheduling problem. Computational results using random instances and instances from the literature show that the proposed formulations have a better performance in scenarios where the original model is not efficient.

Orientador: Maria do Socorro Nogueira Rangel / Banca: Alistair Clark / Banca: Silvio Alexandre de Araujo / Resumo: Em alguns setores, o planejamento da produção envolve dois aspectos: o dimensionamento do tamanho dos lotes e a programação da produção (sequenciamento dos lotes). O primeiro problema consiste em determinar o tamanho dos lotes de produção de cada item a ser produzido em uma ou mais máquinas em cada período ao longo de um horizonte de planejamento finito. O segundo problema consiste em encontrar a ordem em que os lotes devem ser produzidos em um dado conjunto de máquinas. Estes dois aspectos do planejamento da produção podem ser tratados de forma independente: em um estágio é resolvido o problema de dimensionamento dos lotes e no outro, realizado antes ou depois, é resolvido o problema de seqüenciamento. No entanto, uma tendência recente na literatura são trabalhos que apresentam modelos matemáticos que capturam simultaneamente as relações entre os dois problemas. Na literatura pode-se encontrar modelos integrados que incluem restrições de eliminação de subrotas, propostas para o Problema do Caixeiro Viajante (PCV), para formular as restrições de sequenciamento. No entanto, alguns dos modelos propostos usam restrições de ordem polinomial que fornecem uma relaxação linear fraca. O objetivo desse trabalho é avaliar o uso de inequações válidas, propostas na literatura, para obtenção de formulações mais fortes para o problema integrado de dimensionamento e sequenciamento da produção. Resultados computacionais usando exemplares aleatórios e exemplares da literatura mostram que as reformulações propostas são eficientes para cenários em que o modelo original não é eficiente. / Abstract: Often, the production planning involves the lot sizing and scheduling of items. The first problem is to determine the lot size of each item to be produced in one or more machines in each period over a finite planning horizon. The second problem is to find the order in which the items will be produced. These two aspects of the production planning can be treated independently: in one stage the lot sizing problem is solved, and in the other, that can be executed before or after, the scheduling problem is solved. A recent trend in the literature is to propose mathematical models that capture the relationships between these two problems. In the literature one can find integrated models that include subtour elimination constraints, proposed for the Traveling Salesman Problem, to formulate the scheduling decisions. However, in some of these models, constraints of polynomial order, that provides a weak linear relaxation, are used.The purpose of this study is to evaluate the use of valid inequalities proposed in the literature to obtain stronger formulations to the lot and scheduling problem. Computational results using random instances and instances from the literature show that the proposed formulations have a better performance in scenarios where the original model is not efficient. / Mestre