Dissertations / Theses on the topic 'Dynamic Constrained Problems'
To see the other types of publications on this topic, follow the link: Dynamic Constrained Problems.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 33 dissertations / theses for your research on the topic 'Dynamic Constrained Problems.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Wang, Alexander C. (Alexander Che-Wei). "Approximate value iteration approaches to constrained dynamic portfolio problems." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/30089.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.Includes bibliographical references (p. 173-176).
This thesis considers a discrete-time, finite-horizon dynamic portfolio problem where an investor makes sequential investment decisions with the goal of maximizing expected terminal wealth. We allow non-standard utility functions and constraints upon the portfolio selections at each time. These problem formulations may be computationally difficult to address through traditional optimal control techniques due to the high dimensionality of the state space and control space. We consider suboptimal solution methods based on approximate value iteration. The primary innovation is the use of mean-variance portfolio selection methods. We present two case studies that employ these approximate value iteration methods. The first case study explores the effect of an insolvency constraint that prohibits further investing when an investor reaches non-positive wealth. When the investor has an exponential utility function, the insolvency constraint leads to more conservative investment policies when there are many investment periods remaining, except when wealth is very low. The second case study explores the effects of dollar position constraints that represent limited liquidity in certain investment strategies. When the investor has a CRRA utility function, we find that these constraints lead to non-myopic policies that are more conservative than the constrained myopic policy.
by Alexander C. Wang.
Ph.D.
2
Loxton, Ryan Christopher. "Optimal control problems involving constrained, switched, and delay systems." Thesis, Curtin University, 2010. http://hdl.handle.net/20.500.11937/1479.
Full textAbstract:
In this thesis, we develop numerical methods for solving five nonstandard optimal control problems. The main idea of each method is to reformulate the optimal control problem as, or approximate it by, a nonlinear programming problem. The decision variables in this nonlinear programming problem influence its cost function (and constraints, if it has any) implicitly through the dynamic system. Hence, deriving the gradient of the cost and the constraint functions is a difficult task. A major focus of this thesis is on developing methods for computing these gradients. These methods can then be used in conjunction with a gradient-based optimization technique to solve the optimal control problem efficiently.The first optimal control problem that we consider has nonlinear inequality constraints that depend on the state at two or more discrete time points. These time points are decision variables that, together with a control function, should be chosen in an optimal manner. To tackle this problem, we first approximate the control by a piecewise constant function whose values and switching times (the times at which it changes value) are decision variables. We then apply a novel time-scaling transformation that maps the switching times to fixed points in a new time horizon. This yields an approximate dynamic optimization problem with a finite number of decision variables. We develop a new algorithm, which involves integrating an auxiliary dynamic system forward in time, for computing the gradient of the cost and constraints in this approximate problem.The second optimal control problem that we consider has nonlinear continuous inequality constraints. These constraints restrict both the state and the control at every point in the time horizon. As with the first problem, we approximate the control by a piecewise constant function and then transform the time variable. This yields an approximate semi-infinite programming problem, which can be solved using a penalty function algorithm. A solution of this problem immediately furnishes a suboptimal control for the original optimal control problem. By repeatedly increasing the number of parameters used in the approximation, we can generate a sequence of suboptimal controls. Our main result shows that the cost of these suboptimal controls converges to the minimum cost.The third optimal control problem that we consider is an applied problem from electrical engineering. Its aim is to determine an optimal operating scheme for a switchedcapacitor DC-DC power converter—an electronic device that transforms one DC voltage into another by periodically switching between several circuit topologies. Specifically, the optimal control problem is to choose the times at which the topology switches occur so that the output voltage ripple is minimized and the load regulation is maximized. This problem is governed by a switched system with linear subsystems (each subsystem models one of the power converter’s topologies). Moreover, its cost function is non-smooth. By introducing an auxiliary dynamic system and transforming the time variable (so that the topology switching times become fixed), we derive an equivalent semi-infinite programming problem. This semi-infinite programming problem, like the one that approximates the continuously-constrained optimal control problem, can be solved using a penalty function algorithm.The fourth optimal control problem that we consider involves a general switched system, which includes the model of a switched-capacitor DC-DC power converter as a special case. This switched system evolves by switching between several subsystems of nonlinear ordinary differential equations. Furthermore, each subsystem switch is accompanied by an instantaneous change in the state. These instantaneous changes—so-called state jumps—are influenced by control variables that, together with the subsystem switching times, should be selected in an optimal manner. As with the previous optimal control problems, we tackle this problem by transforming the time variable to obtain an equivalent problem in which the switching times are fixed. However, the functions governing the state jumps in this new problem are discontinuous. To overcome this difficulty, we introduce an approximate problem whose state jumps are governed by smooth functions. This approximate problem can be solved using a nonlinear programming algorithm. We prove an important convergence result that links the approximate problem’s solution with the original problem’s solution.The final optimal control problem that we consider is a parameter identification problem. The aim of this problem is to use given experimental data to identify unknown state-delays in a nonlinear delay-differential system. More precisely, the optimal control problem involves choosing the state-delays to minimize a cost function measuring the discrepancy between predicted and observed system output. We show that the gradient of this cost function can be computed by solving an auxiliary delay-differential system. On the basis of this result, the optimal control problem can be formulated—and hence solved—as a standard nonlinear programming problem.
3
Kangwalklai, Sasikul. "Time Dynamic Label-Constrained Shortest Path Problems with Application to TRANSIMS: A Transportation Planning System." Thesis, Virginia Tech, 2001. http://hdl.handle.net/10919/31037.
Full textAbstract:
TRANSIMS (Transportation Analysis Simulation System) is part of a multi-track Travel Model Improvement Program sponsored by the U. S. Department of Transportation (DOT), and the Environmental Protection Agency (EPA). The main objective of this thesis is to enhance and implement a principal module in TRANSIMS, called the Route Planner Module. The purpose of the Route Planner Module is to find time-dependent label-constrained shortest paths for transportation activities performed by travelers in the system. There are several variations of shortest path problems and algorithms that vary by application, contexts, complexity, required data, and computer implementation techniques. In general, these variants require some combination of the following inputs: a network consisting of nodes and links, and a travel time function on each link, which could be a time-independent or a time-dependent function, where the time-dependent functions account for time-of-day delays resulting from actual travel conditions such as peak-hour congestion. The problem then seeks a shortest path between one or more origin-destination pairs. A new variant, introduced in the context of TRANSIMS and which is the focus of the present study, also specifies labels for each arc denoting particular modes of travel, along with strings of admissible labels that delineate the permissible travel mode sequences that could be adopted by the user in traveling from the origin to the destination of the trip.
The technique adopted by TRANSIMS to identify a suitable travel route for any user is a variant of Dijkstra's procedure for finding shortest paths, which is suitably modified to accommodate time-dependent travel times and label sequence constraints. The underlying problem is referred to as a Time-Dependent Label-Constrained Shortest Path Problem. The main objective of this research is to improve upon this procedure and study its implementation in order to develop a more effective scheme for determining time-dependent label-constrained shortest paths as a practical routing tool in multimodal transportation networks.
Specifically, we enhance the following features of this procedure:
(a) We recommend a method to work implicitly with a certain composition graph G* that combines the transportation network with the admissible label-sequence graph. This graph G* captures all possible paths for a given single trip starting from the origin node and ending at the destination node, while conforming with the admissible mode string.
(b) We use more modern partitioned shortest path algorithmic schemes to implement the time-dependent label-constrained procedure.
(c) We introduce the notion of curtailing search based on various indicators of progress and projected travel times to complete the trip.
Finally, computer programs in C++ are written to implement the proposed overall algorithm, and are applied to solve some real multimodal transportation network problems. The indicators used to evaluate the performance of the algorithm include (i) time taken for computation on the real network, (ii) quality of solution obtained, (iii) ease of implementation, and (iv) extensibility of the algorithm for solving other variants of the shortest path problem. The results exhibit that the proposed algorithm, even without the approximate curtailing of the search process, exhibits good performance in finding optimal routes for real multimodal transportation networks. Although the various heuristic curtailments result in only approximate solutions, typically, they run much faster than the exact algorithm for the intuitive reason that the shortest path tree developed grows more pointedly in the direction of the destination. Among the different strategies implemented, our results suggest that the scheme based on the geometric structure of the underlying network, using either a constant predictive term, or multiplying this term with a suitable exponential decay function, yields an attractive candidate for heuristically curtailing the search.Master of Science
4
Lokhov, Andrey Y. "Dynamic cavity method and problems on graphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112331/document.
Full textAbstract:
Un grand nombre des problèmes d'optimisation, ainsi que des problèmes inverses, combinatoires ou hors équilibre qui apparaissent en physique statistique des systèmes complexes, peuvent être représentés comme un ensemble des variables en interaction sur un certain réseau. Bien que la recette universelle pour traiter ces problèmes n'existe pas, la compréhension qualitative et quantitative des problèmes complexes sur des graphes a fait des grands progrès au cours de ces dernières années. Un rôle particulier a été joué par des concepts empruntés de la physique des verres de spin et la théorie des champs, qui ont eu beaucoup de succès en ce qui concerne la description des propriétés statistiques des systèmes complexes et le développement d'algorithmes efficaces pour des problèmes concrets.En première partie de cette thèse, nous étudions des problèmes de diffusion sur des réseaux, avec la dynamique hors équilibre. En utilisant la méthode de cavité sur des trajectoires dans le temps, nous montrons comment dériver des équations dynamiques dites "message-passing'' pour une large classe de modèles avec une dynamique unidirectionnelle -- la propriété clef qui permet de résoudre le problème. Ces équations sont asymptotiquement exactes pour des graphes localement en arbre et en général représentent une bonne approximation pour des réseaux réels. Nous illustrons cette approche avec une application des équations dynamiques pour résoudre le problème inverse d'inférence de la source d'épidémie dans le modèle "susceptible-infected-recovered''.Dans la seconde partie du manuscrit, nous considérons un problème d'optimisation d'appariement planaire optimal sur une ligne. En exploitant des techniques de la théorie de champs et des arguments combinatoires, nous caractérisons une transition de phase topologique qui se produit dans un modèle désordonné simple, le modèle de Bernoulli. Visant une application à la physique des structures secondaires de l'ARN, nous discutons la relation entre la transition d'appariement parfait-imparfait et la transition de basse température connue entre les états fondu et vitreux de biopolymère; nous proposons également des modèles généralisés qui suggèrent une correspondance exacte entre la matrice des contacts et la séquence des nucléotides, permettant ainsi de donner un sens à la notion des alphabets effectifs non-entiersA large number of optimization, inverse, combinatorial and out-of-equilibrium problems, arising in the statistical physics of complex systems, allow for a convenient representation in terms of disordered interacting variables defined on a certain network. Although a universal recipe for dealing with these problems does not exist, the recent years have seen a serious progress in understanding and quantifying an important number of hard problems on graphs. A particular role has been played by the concepts borrowed from the physics of spin glasses and field theory, that appeared to be extremely successful in the description of the statistical properties of complex systems and in the development of efficient algorithms for concrete problems.In the first part of the thesis, we study the out-of-equilibrium spreading problems on networks. Using dynamic cavity method on time trajectories, we show how to derive dynamic message-passing equations for a large class of models with unidirectional dynamics -- the key property that makes the problem solvable. These equations are asymptotically exact for locally tree-like graphs and generally provide a good approximation for real-world networks. We illustrate the approach by applying the dynamic message-passing equations for susceptible-infected-recovered model to the inverse problem of inference of epidemic origin. In the second part of the manuscript, we address the optimization problem of finding optimal planar matching configurations on a line. Making use of field-theory techniques and combinatorial arguments, we characterize a topological phase transition that occurs in the simple Bernoulli model of disordered matching. As an application to the physics of the RNA secondary structures, we discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition at low temperatures, and suggest generalized models that incorporate a one-to-one correspondence between the contact matrix and the nucleotide sequence, thus giving sense to the notion of effective non-integer alphabets
5
Van, Der Linden A. S. Janet. "Dynamic meta-constraints : an approach to dealing with non-standard constraint satisfaction problems." Thesis, Oxford Brookes University, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.322242.
Full text
6
Climent, Aunés Laura Isabel. "Robustness and stability in dynamic constraint satisfaction problems." Doctoral thesis, Universitat Politècnica de València, 2014. http://hdl.handle.net/10251/34785.
Full textAbstract:
Constraint programming is a paradigm wherein relations between variables are stated in the form of constraints. It is well-known that many real life problems can be modeled as Constraint Satisfaction Problems (CSPs). Much effort has been spent to increase the efficiency of algorithms for solving CSPs. However, many of these techniques assume that the set of variables, domains and constraints involved in the CSP are known and fixed when the problem is modeled. This is a strong limitation because many problems come from uncertain and dynamic environments, where both the original problem may evolve because of the environment, the user or other agents. In such situations, a solution that holds for the original problem can become invalid after changes.
There are two main approaches for dealing with these situations: reactive and proactive approaches. Using reactive approaches entails re-solving the CSP after each solution loss, which is a time consuming. That is a clear disadvantage, especially when we deal with short-term changes, where solution loss is frequent. In addition, in many applications, such as on-line planning and scheduling, the delivery time of a new solution may be too long for actions to be taken on time, so a solution loss can produce several negative effects in the modeled problem. For a task assignment production system with several machines, it could cause the shutdown of the production system, the breakage of machines, the loss of the material/object in production, etc. In a transport timetabling problem, the solution loss, due to some disruption at a point, may produce a delay that propagates through the entire schedule. In addition, all the negative effects stated above will probably entail an economic loss.
In this thesis we develop several proactive approaches. Proactive approaches use knowledge about possible future changes in order to avoid or minimize their effects. These approaches are applied before the changes occur. Thus, our approaches search for robust solutions, which have a high probability to remain valid after changes. Furthermore, some of our approaches also consider that the solutions can be easily adapted when they did not resist the changes in the original problem. Thus, these approaches search for stable solutions, which have an alternative solution that is similar to the previous one and therefore can be used in case of a value breakage.
In this context, sometimes there exists knowledge about the uncertain and dynamic environment. However in many cases, this information is unknown or hard to obtain. For this reason, for the majority of our approaches (specifically 3 of the 4 developed approaches), the only assumptions made about changes are those inherent in the structure of problems with ordered domains. Given this framework and therefore the existence of a significant order over domain values, it is reasonable to assume that the original bounds of the solution space may undergo restrictive or relaxed modifications. Note that the possibility of solution loss only exists when changes over the original bounds of the solution space are restrictive. Therefore, the main objective for searching robust solutions in this framework is to find solutions located as far away as possible from the bounds of the solution space. In order to meet this criterion, we propose several approaches that can be divided in enumeration-based techniques and a search algorithm.Climent Aunés, LI. (2013). Robustness and stability in dynamic constraint satisfaction problems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/34785
TESIS
7
Vassiliadis, Vassilios. "Computational solution of dynamic optimization problems with general differential-algebraic constraints." Thesis, Imperial College London, 1993. http://hdl.handle.net/10044/1/7567.
Full text
8
Voccia, Stacy Ann. "Stochastic last-mile delivery problems with time constraints." Diss., University of Iowa, 2015. https://ir.uiowa.edu/etd/1924.
Full textAbstract:
When a package is shipped, the customer often requires the delivery to be made within a particular time window or by a deadline. However, meeting such time requirements is difficult, and delivery companies may not always know ahead of time which customers will need a delivery. In this thesis, we present models and solution approaches for two stochastic last-mile delivery problems in which customers have delivery time constraints and customer presence is known in advance only according to a probability distribution. Our solutions can help reduce the operational costs of delivery while improving customer service.
The first problem is the probabilistic traveling salesman problem with time windows (PTSPTW). In the PTSPTW, customers have both a time window and a probability of needing a delivery on any given day. The objective is to find a pre-planned route with an expected minimum cost. We present computational results that characterize the PTSPTW solutions. We provide insights for practitioners on when solving the PTSPTW is beneficial compared to solving the deterministic analogue of the problem.
The second problem is the same-day delivery problem (SDDP). The SDDP is a dynamic and stochastic pick-up and delivery problem. In the SDDP, customers make delivery requests throughout the day and vehicles are dispatched from a warehouse or brick and mortar store to serve the requests. Associated with each request is a request deadline or time window. In order to make better-informed decisions, our solution approach incorporates information about future requests into routing decisions by using a sample scenario planning approach with a consensus function. We also introduce an analytical result that identifies when it is beneficial for vehicles to wait at the depot. We present a wide range of computational experiments that demonstrate the value of our approaches.
9
Mai, Dung Hoang. "A Heuristic for the Constrained One-Sided Two-Layered Crossing Reduction Problem for Dynamic Graph Layout." NSUWorks, 2011. http://nsuworks.nova.edu/gscis_etd/225.
Full textAbstract:
Data in real-world graph drawing applications often change frequently but incrementally. Any drastic change in the graph layout could disrupt a user's "mental map." Furthermore, real-world applications like enterprise process or e-commerce graphing, where data change rapidly in both content and quantity, demand a comprehensive responsiveness when rendering the graph layout in a multi-user environment in real time. Most standard static graph drawing algorithms apply global changes and redraw the entire graph layout whenever the data change. The new layout may be very different from the previous layout and the time taken to redraw the entire graph degrades quickly as the amount of graph data grows. Dynamic behavior and the quantity of data generated by real-world applications pose challenges for existing graph drawing algorithms in terms of incremental stability and scalability.
A constrained hierarchical graph drawing framework and modified Sugiyama heuristic were developed in this research. The goal of this research was to improve the scalability of the constrained graph drawing framework while preserving layout stability. The framework's use of the relational data model shifts the graph application from the traditional desktop to a collaborative and distributed environment by reusing vertex and edge information stored in a relational database. This research was based on the work of North and Woodhull (2001) and the constrained crossing reduction problem proposed by Forster (2004). The result of the constrained hierarchical graph drawing framework and the new Sugiyama heuristic, especially the modified barycenter algorithms, were tested and evaluated against the Graphviz framework and North and Woodhull's (2001) online graph drawing framework.
The performance test results showed that the constrained graph drawing framework run time is comparable with the performance of the Graphviz framework in terms of generating static graph layouts, which is independent of database accesses. Decoupling graph visualization from the graph editing modules improved scalability, enabling the rendering of large graphs in real time. The visualization test also showed that the constrained framework satisfied the aesthetic criteria for constrained graph layouts. Future enhancements for this proposed framework include implementation of (1) the horizontal coordinate assignment algorithm, (2) drawing polylines for multilayer edges in the rendering module, and (3) displaying subgraphs for very large graph layouts.
10
Zhu, Xiaoyan. "The dynamic, resource-constrained shortest path problem on an acyclic graph with application in column generation and literature review on sequence-dependent scheduling." Texas A&M University, 2005. http://hdl.handle.net/1969.1/4996.
Full textAbstract:
This dissertation discusses two independent topics: a resource-constrained shortest-path problem
(RCSP) and a literature review on scheduling problems involving sequence-dependent setup
(SDS) times (costs).
RCSP is often used as a subproblem in column generation because it can be used to
solve many practical problems. This dissertation studies RCSP with multiple resource
constraints on an acyclic graph, because many applications involve this configuration, especially
in column genetation formulations. In particular, this research focuses on a dynamic RCSP
since, as a subproblem in column generation, objective function coefficients are updated using
new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial
solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic
graph with the goal of effectively reoptimizing RCSP in the context of column generation. This
method uses a one-time âÂÂpreliminaryâ phase to transform RCSP into an unconstrained shortest
path problem (SPP) and then solves the resulting SPP after new values of dual variables are used
to update objective function coefficients (i.e., reduced costs) at each iteration. Network
reduction techniques are considered to remove some nodes and/or arcs permanently in the preliminary phase. Specified techniques are explored to reoptimize when only several
coefficients change and for dealing with forbidden and prescribed arcs in the context of a column
generation/branch-and-bound approach. As a benchmark method, a label-setting algorithm is
also proposed. Computational tests are designed to show the effectiveness of the proposed
algorithms and procedures.
This dissertation also gives a literature review related to the class of scheduling
problems that involve SDS times (costs), an important consideration in many practical
applications. It focuses on papers published within the last decade, addressing a variety of
machine configurations - single machine, parallel machine, flow shop, and job shop - reviewing
both optimizing and heuristic solution methods in each category. Since lot-sizing is so
intimately related to scheduling, this dissertation reviews work that integrates these issues in
relationship to each configuration. This dissertation provides a perspective of this line of
research, gives conclusions, and discusses fertile research opportunities posed by this class of
scheduling problems.
since, as a subproblem in column generation, objective function coefficients are updated using
new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial
solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic
graph with the goal of effectively reoptimizing RCSP in the context of column generation. This
method uses a one-time
11
Helbig, Marde. "Solving dynamic multi-objective optimisation problems using vector evaluated particle swarm optimisation." Thesis, University of Pretoria, 2012. http://hdl.handle.net/2263/28161.
Full textAbstract:
Most optimisation problems in everyday life are not static in nature, have multiple objectives and at least two of the objectives are in conflict with one another. However, most research focusses on either static multi-objective optimisation (MOO) or dynamic singleobjective optimisation (DSOO). Furthermore, most research on dynamic multi-objective optimisation (DMOO) focusses on evolutionary algorithms (EAs) and only a few particle swarm optimisation (PSO) algorithms exist. This thesis proposes a multi-swarm PSO algorithm, dynamic Vector Evaluated Particle Swarm Optimisation (DVEPSO), to solve dynamic multi-objective optimisation problems (DMOOPs). In order to determine whether an algorithm solves DMOO efficiently, functions are required that resembles real world DMOOPs, called benchmark functions, as well as functions that quantify the performance of the algorithm, called performance measures. However, one major problem in the field of DMOO is a lack of standard benchmark functions and performance measures. To address this problem, an overview is provided from the current literature and shortcomings of current DMOO benchmark functions and performance measures are discussed. In addition, new DMOOPs are introduced to address the identified shortcomings of current benchmark functions. Guides guide the optimisation process of DVEPSO. Therefore, various guide update approaches are investigated. Furthermore, a sensitivity analysis of DVEPSO is conducted to determine the influence of various parameters on the performance of DVEPSO. The investigated parameters include approaches to manage boundary constraint violations, approaches to share knowledge between the sub-swarms and responses to changes in the environment that are applied to either the particles of the sub-swarms or the non-dominated solutions stored in the archive. From these experiments the best DVEPSO configuration is determined and compared against four state-of-the-art DMOO algorithms.Thesis (PhD)--University of Pretoria, 2012.
Computer Science
unrestricted
12
Karakoc, Erman. "Web Service Composition Under Resource Allocation Constraints." Master's thesis, METU, 2007. http://etd.lib.metu.edu.tr/upload/12608309/index.pdf.
Full textAbstract:
Web service composition is an inevitable aspect of web services technology, which solves complex problems by combining available basic services and ordering them to best suit the problem requirements. Automatic composition gives us flexibility of selecting best candidate services at composition time, this would require the user to define the resource allocation constraints for selecting and composing candidate web services. Resource allocation constraints define restrictions on how to allocate resources, and scheduling under resource allocation constraints to provide proper resource allocation to tasks. In this work, web service composition system named as CWSF (Composite Web Service Framework) constructed for users to define a workflow system in which a rich set of constraints can be defined on web services. On the contrary many technologies and studies, CWSF provides a user-friendly environment for modeling web service composition system. The output of the
framework is the scheduling of web service composition in which how and when web services are executed are defined. With this work, a language, CWSL is defined to describe workflow, resource allocation constraints, selection and discovery rules of web services and associated semantic information. An important property of CWSF system is converting web service composition problem into a constraint satisfaction problem to find the best solution that meet the all criteria defined by user. Furthermore, CWSF has ability to display other possible solutions to provides users flexibility. This study also includes semantic matching and mapping facilities for service discovery.
13
Efthymiou, Charilaos [Verfasser], Amin [Gutachter] Coja-Oghlan, and Alan [Gutachter] Frieze. "Phase transitions and dynamics for random constraint satisfaction problems / Charilaos Efthymiou ; Gutachter: Amin Coja-Oghlan, Alan Frieze." Frankfurt am Main : Universitätsbibliothek Johann Christian Senckenberg, 2018. http://d-nb.info/1175498920/34.
Full text
14
Sahli, Abderrahim. "Problèmes d'ordonnancement avec production et consommation des ressources." Thesis, Compiègne, 2016. http://www.theses.fr/2016COMP2309/document.
Full textAbstract:
La plupart des travaux de recherches sur les problèmes d'ordonnancement traitent le cas des ressources renouvelables, c'est-à-dire des ressources qui sont exigées en début d'exécution de chaque tâche et sont restituées en fin d'exécution. Peu d'entre eux abordent les problèmes à ressources consommables, c'est-à-dire des ressources non restituées en fin d'exécution. Le problème de gestion de projet à contraintes de ressources (RCPSP) est le problème à ressources renouvelables le plus traité dans la littérature. Dans le cadre de cette thèse, nous nous sommes intéressés à une généralisation du problème RCPSP qui correspond au cas où les tâches sont remplacées par des événements liés par des relations de précédence étendues. Chaque événement peut produire ou consommer une quantité de ressources à sa date d'occurrence et la fonction économique reste la durée totale à minimiser. Nous avons nommé cette généralisation ERCPSP (Extended RCPSP). Nous avons élaboré des modèles de programmation linéaire pour résoudre ce problème. Nous avons proposé plusieurs bornes inférieures algorithmiques exploitant les travaux de la littérature sur les problèmes cumulatifs. Ensuite, nous avons élargi la portée des méthodes utilisées pour la mise en place de méthodes de séparation et évaluation. Nous avons traité aussi des cas particuliers par des méthodes basées sur la programmation dynamiqueThis thesis investigates the Extended Resource Constrained Project Scheduling Problem (ERCPSP). ERCPSP is a general scheduling problem where the availability of a resource is depleted and replenished at the occurrence times of a set of events. It is an extension of the Resource Constrained Project Scheduling Problem (RCPSP) where activities are replaced by events, which have to be scheduled subject to generalized precedence relations. We are interested in this thesis in proposing new methodologies and approaches to solve ERCPSP. First, we study some polynomial cases of this problem and we propose a dynamic programming algorithm to solve the parallel chain case. Then, we propose lower bounds, mixed integer programming models, and a branch-and-bound method to solve ERCPSP. Finally, we develop an instance generator dedicated to this problem
15
Lacoursière, Claude. "Ghosts and machines : regularized variational methods for interactive simulations of multibodies with dry frictional contacts." Doctoral thesis, Umeå University, Computing Science, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-1143.
Full textAbstract:
A time-discrete formulation of the variational principle of mechanics is used to provide a consistent theoretical framework for the construction and analysis of low order integration methods. These are applied to mechanical systems subject to mixed constraints and dry frictional contacts and impacts---machines. The framework includes physics motivated constraint regularization and stabilization schemes. This is done by adding potential energy and Rayleigh dissipation terms in the Lagrangian formulation used throughout. These terms explicitly depend on the value of the Lagrange multipliers enforcing constraints. Having finite energy, the multipliers are thus massless ghost particles. The main numerical stepping method produced with the framework is called SPOOK.
Variational integrators preserve physical invariants globally, exactly in some cases, approximately but within fixed global bounds for others. This allows to product realistic physical trajectories even with the low order methods. These are needed in the solution of nonsmooth problems such as dry frictional contacts and in addition, they are computationally inexpensive. The combination of strong stability, low order, and the global preservation of invariants allows for large integration time steps, but without loosing accuracy on the important and visible physical quantities. SPOOK is thus well-suited for interactive simulations, such as those commonly used in virtual environment applications, because it is fast, stable, and faithful to the physics.
New results include a stable discretization of highly oscillatory terms of constraint regularization; a linearly stable constraint stabilization scheme based on ghost potential and Rayleigh dissipation terms; a single-step, strictly dissipative, approximate impact model; a quasi-linear complementarity formulation of dry friction that is isotropic and solvable for any nonnegative value of friction coefficients; an analysis of a splitting scheme to solve frictional contact complementarity problems; a stable, quaternion-based rigid body stepping scheme and a stable linear approximation thereof. SPOOK includes all these elements. It is linearly implicit and linearly stable, it requires the solution of either one linear system of equations of one mixed linear complementarity problem per regular time step, and two of the same when an impact condition is detected. The changes in energy caused by constraints, impacts, and dry friction, are all shown to be strictly dissipative in comparison with the free system. Since all regularization and stabilization parameters are introduced in the physics, they map directly onto physical properties and thus allow modeling of a variety of phenomena, such as constraint compliance, for instance.
Tutorial material is included for continuous and discrete-time analytic mechanics, quaternion algebra, complementarity problems, rigid body dynamics, constraint kinematics, and special topics in numerical linear algebra needed in the solution of the stepping equations of SPOOK.
The qualitative and quantitative aspects of SPOOK are demonstrated by comparison with a variety of standard techniques on well known test cases which are analyzed in details. SPOOK compares favorably for all these examples. In particular, it handles ill-posed and degenerate problems seamlessly and systematically. An implementation suitable for large scale performance and accuracy testing is left for future work.
16
Yoo, Jaewook. "Multi-period optimization of pavement management systems." Diss., Texas A&M University, 2004. http://hdl.handle.net/1969.1/343.
Full textAbstract:
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.
17
Xiong, Jun. "Set-membership state estimation and application on fault detection." Phd thesis, Institut National Polytechnique de Toulouse - INPT, 2013. http://tel.archives-ouvertes.fr/tel-01068054.
Full textAbstract:
La modélisation des systèmes dynamiques requiert la prise en compte d'incertitudes liées à l'existence inévitable de bruits (bruits de mesure, bruits sur la dynamique), à la méconnaissance de certains phénomènes perturbateurs mais également aux incertitudes sur la valeur des paramètres (spécification de tolérances, phénomène de vieillissement). Alors que certaines de ces incertitudes se prêtent bien à une modélisation de type statistique comme par exemple les bruits de mesure, d'autres se caractérisent mieux par des bornes, sans autre attribut. Dans ce travail de thèse, motivés par les observations ci-dessus, nous traitons le problème de l'intégration d'incertitudes statistiques et à erreurs bornées pour les systèmes linéaires à temps discret. Partant du filtre de Kalman Intervalle (noté IKF) développé dans [Chen 1997], nous proposons des améliorations significatives basées sur des techniques récentes de propagation de contraintes et d'inversion ensembliste qui, contrairement aux mécanismes mis en jeu par l'IKF, permettent d'obtenir un résultat garanti tout en contrôlant le pessimisme de l'analyse par intervalles. Cet algorithme est noté iIKF. Le filtre iIKF a la même structure récursive que le filtre de Kalman classique et délivre un encadrement de tous les estimés optimaux et des matrices de covariance possibles. L'algorithme IKF précédent évite quant à lui le problème de l'inversion des matrices intervalles, ce qui lui vaut de perdre des solutions possibles. Pour l'iIKF, nous proposons une méthode originale garantie pour l'inversion des matrices intervalle qui couple l'algorithme SIVIA (Set Inversion via Interval Analysis) et un ensemble de problèmes de propagation de contraintes. Par ailleurs, plusieurs mécanismes basés sur la propagation de contraintes sont également mis en oeuvre pour limiter l'effet de surestimation due à la propagation d'intervalles dans la structure récursive du filtre. Un algorithme de détection de défauts basé sur iIKF est proposé en mettant en oeuvre une stratégie de boucle semi-fermée qui permet de ne pas réalimenter le filtre avec des mesures corrompues par le défaut dès que celui-ci est détecté. A travers différents exemples, les avantages du filtre iIKF sont exposés et l'efficacité de l'algorithme de détection de défauts est démontré.
18
Kharrat, Samah. "Contribution à l'ordonnancement des ateliers de traitement de surface avec deux robots." Phd thesis, Université de Technologie de Belfort-Montbeliard, 2012. http://tel.archives-ouvertes.fr/tel-00864235.
Full textAbstract:
Dans cette thèse, nous nous intéressons principalement à l'étude du fonctionnement cyclique mono-produit des ateliers de traitement de surface. Notre contribution porte sur le problème d'ordonnancement associé connu dans la littérature sous le nom Cyclic Hoist Scheduling Problem (CHSP). L'objet de cette thèse est de proposer des méthodes efficaces pour la résolution des problèmes de traitement de surface dans le cas où les produits à traiter sont du même type. Nous traitons en particulier le cas où le nombre des robots présents sur la ligne est égal à deux, ce qui augmente le nombre des contraintes du problème, sachant que dans le cas mono robot, ce problème a été prouvé NP-Complet. Pour cela, nous proposons une méthode qui combine deux heuristiques et un programme linéaire mixte. Cette méthode permet notamment d'affecter les mouvements de transport à l'un des deux robots tout en gérant les risques de collision entre eux, lorsque la gamme opératoire des produits à traiter suit l'implantation des cuves.Par la suite, nous proposons une extension du modèle au cas de lignes complexes. Enfin, nous étudions le cas d'un fonctionnement mixte, pour lequel il est nécessaire de traiter dans une même installation des produits différents et des rafales de produits identiques. Dans ces conditions, la solution la plus intéressante pour les industriels est de pouvoir alterner des modes de production dynamiques et cycliques. Pour cela, nous proposons une méthode efficace permettant de résoudre le problème d'ordonnancement associé à la phase transitoire relative à ce type de fonctionnement. Elle consiste en particulier à chercher les dates d'entrée au plus tôt des produits. La principale difficulté identifiée consiste ici à passer du mode dynamique au mode cyclique, c'est-à-dire à rejoindre un cycle à partir d'une solution courante donnée, en supposant que ce cycle est connu à priori. Les méthodes élaborées dans les divers cas traités sont validées par des tests sur des benchmarks de la littérature.
19
Restrepo, Lopez Ricardo. "Topics in spatial and dynamical phase transitions of interacting particle systems." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/42729.
Full textAbstract:
In this work we provide several improvements in the study of phase transitions
of interacting particle systems:
- We determine a quantitative relation between non-extremality of the limiting Gibbs measure of a tree-based spin system, and the temporal mixing of
the Glauber Dynamics over its finite projections. We define the concept of 'sensitivity' of a reconstruction scheme to establish such a relation. In particular, we focus on the independent sets model, determining a phase
transition for the mixing time of the Glauber dynamics at the same location of
the extremality threshold of the simple invariant Gibbs version of the model.
- We develop the technical analysis of the so-called spatial mixing conditions for interacting particle systems to account for the connectivity structure of the underlying graph. This analysis leads to improvements regarding the location of the uniqueness/non-uniqueness phase transition for the independent sets model over amenable graphs; among them, the elusive hard-square model in lattice statistics, which has received attention since Baxter's solution of the analogous hard-hexagon in 1980.
- We build on the work of Montanari and Gerschenfeld to determine the existence of correlations for the coloring model in sparse random graphs. In particular, we prove that correlations exist above the 'clustering' threshold of such a model; thus providing further evidence for the conjectural algorithmic 'hardness' occurring at such a point.
20
Changuel, Nesrine. "Régulation de la qualité lors de la transmission de contenus vidéo sur des canaux sans fils." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00659806.
Full textAbstract:
Le développement simultané de terminaux mobiles multimédia (smartphones, tablettes) et de réseaux d'accès offrant des débits élevés conduit à une explosion du trafic liés aux contenus multimédia. Cette croissance nécessite un partage efficace des ressources radio entre fournisseurs de contenus (dans le cas de la diffusion) ou entre récepteurs (dans le cas de services de vidéo à la demande). Cette thèse propose des outils de partage équitable des ressources en termes de qualité des contenus multimédia reçu et de délai de transmission dans les deux contextes précédents. La variété des compromis débit-distorsion des contenus multimédia est exploitée à cet effet. Dans un premier temps, une solution centralisée de contrôle conjoint du débit de codage et de transmission de plusieurs programmes transmis sur un même canal est considérée. L'objectif est de fournir des flux de qualités similaires avec des variations limitées, tout en assurant des délais de transmission comparables. Ce problème est résolu en synthétisant une commande prédictive à l'aide d'outils d'optimisation sous contrainte. Dans un second temps, seule l'allocation de bande est centralisée, le contrôle des caractéristiques de compression de chaque flux est réalisé de manière distribuée. Le contrôleur centralisé ne renvoie que le niveau de remplissage des tampons associés à chaque flux aux fournisseurs de contenus distants. Une stratégie de régulation des débits de codage est alors mise en place par ces fournisseurs, de manière à réguler le niveau en bits ou en image des tampons. La stabilité de ce système de régulation couplé est étudiée en détails. Enfin, l'optimisation inter-couches d'une chaine de transmission de contenus multimédia scalable est considérée. Ce problème est formulé dans le contexte de la programmation dynamique. Lorsque des modèles de complexité raisonnable sont considérés et avec des caractéristiques du système bien connues, des solutions optimales peuvent être obtenues. Des techniques d'apprentissage sont mises en œuvre, lorsque le système n'est que partiellement connu, par exemple, lorsque l'état du canal de transmission parvient avec du retard à l'organe de commande.
21
Trojet, Mariem. "Planification d'une chaîne logistique : approche par satisfaction de contraintes dynamiques." Phd thesis, INSA de Toulouse, 2014. http://tel.archives-ouvertes.fr/tel-00996957.
Full textAbstract:
Le sujet de thèse porte sur la planification tactique et opérationnelle d'une chaîne logistique dans un contexte dynamique. Nous proposons un modèle de planification basé sur une structure décisionnelle à deux niveaux. Adoptant un processus dynamique permettant d'actualiser les données à chaque étape de planification, le premier niveau planifie la production en recherchant le meilleur compromis entre les leviers décisionnels disponibles liés aux aspects capacité et coût de production. Le deuxième niveau établit un ordonnancement agrégé des opérations de fabrication en minimisant les en-cours. Le recours à une structure décisionnelle intégrée nous a conduit à établir une interaction entre les niveaux supérieur et inférieur de décision, mise en oeuvre par des contraintes dites de conservation d'énergie. Notre approche est modélisée sous la forme d'un problème de satisfaction de contraintes (CSP, Constraint Satisfaction Problem) et évaluée par simulation dans un contexte de données incertaines. Nous avons mené différentes expérimentations portant sur la variation de la demande, la variation de la capacité et la re-planification de la demande. Toutes les expérimentations sont réalisées par deux méthodes de résolution différentes : une méthode basée sur un CSP statique et une méthode basée sur un CSP dynamique. La performance d'une solution de planification/ordonnancement est renseignée par l'ensemble des mesures de la stabilité et de la robustesse. Les expérimentations réalisées offrent une démonstration de la performance de la méthode de résolution basée sur un CSP dynamique par rapport à la méthode statique.
22
Wilczynski, Anaëlle. "Interaction entre agents modélisée par un réseau social dans des problématiques de choix social computationnel Strategic Voting in a Social Context: Considerate Equilibria Object Allocation via Swaps along a Social Network Local Envy-Freeness in House Allocation Problems Constrained Swap Dynamics over a Social Network in Distributed Resource Reallocation Poll-Confident Voters in Iterative Voting." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLED073.
Full textAbstract:
Le choix social repose sur l’étude de la prise de décision collective, où un ensemble d’individus doit convenir d’une solution commune en fonction des préférences de ses membres. Le problème revient à déterminer comment agréger les préférences de différents agents en une décision acceptable pour le groupe. Typiquement, les agents interagissent dans des processus de décision collective, notamment en collaborant ou en échangeant des informations. Il est communément supposé que tout agent est capable d’interagir avec n’importe quel autre. Or, cette hypothèse paraît irréaliste pour de nombreuses situations. On propose de relâcher cette hypothèse en considérant que la possibilité d’interaction est déterminée par un réseau social, représenté par un graphe sur les agents. Dans un tel contexte, on étudie deux problèmes de choix social : le vote stratégique et l’allocation de ressources. L’analyse se concentre sur deux types d’interaction : la collaboration entre les agents, et la collecte d’information. On s’intéresse à l’impact du réseau social, modélisant une possibilité de collaboration entre les agents ou une relation de visibilité, sur la résolution et les solutions de problèmes de vote et d’allocation de ressources. Nos travaux s’inscrivent dans le cadre du choix social computationnel, en utilisant pour ces questions des outils provenant de la théorie des jeux algorithmique et de la théorie de la complexitéSocial choice is the study of collective decision making, where a set of agents must make a decision over a set of alternatives, according to their preferences. The question relies on how aggregating the preferences of the agents in order to end up with a decision that is commonly acceptable for the group. Typically, agents can interact by collaborating, or exchanging some information. It is usually assumed in computational social choice that every agent is able to interact with any other agent. However, this assumption looks unrealistic in many concrete situations. We propose to relax this assumption by considering that the possibility of interaction is given by a social network, represented by a graph over the agents.In this context, we study two particular problems of computational social choice: strategic voting and resource allocation of indivisible goods. The focus is on two types of interaction: collaboration and information gathering. We explore how the social network,modelingapossibilityofcollaboration or a visibility relation among the agents, can impact the resolution and the solution of voting and resource allocation problems. These questions are addressed via computational social choice by using tools from algorithmic game theory and computational complexity
23
Hasani, Shoreh Maryam. "Differential Evolution for Dynamic Constrained Continuous Optimisation." Thesis, 2020. http://hdl.handle.net/2440/129596.
Full textAbstract:
In this thesis, we choose the evolutionary dynamic optimisation methodology
to tackle dynamic constrained problems. Dynamic constrained problems
represent a common class of optimisation that occur in many real-world
scenarios. Evolutionary algorithms are often considered very general search
heuristics. Their main advantages (in comparison to problem-specific search
methods) are their robustness, flexibility and extensibility, as well as the fact
that almost no domain knowledge is required for their implementation and
application.
Our research is focused on the following areas. In the first part of the thesis,
we modify common constraint handling techniques from static domains to
suit dynamic environments. We investigate the deficiencies of such techniques
and the potential of each method based on the change characteristics of the environment.
In the second part, we propose a framework to create benchmarks,
since we have observed a lack of benchmarks to evaluate algorithms in dynamic
continuous optimisation. Third, we carry out an exhaustive empirical
study of diversity mechanisms applied to solve dynamic constrained optimisation
problems. Finally, we investigate the integration of a neural network
into the evolution process and analyse it’s effectiveness compared to that of
popular diversity mechanisms. We address the possibility of integrating such
mechanisms with a neural network approach in order to improve the results.Thesis (Ph.D.) -- University of Adelaide, School of Computer Science, 2020
24
LI, YI-ZHONG, and 李一忠. "A new differential dynamic programming algorithm for linearly constrained problems." Thesis, 1989. http://ndltd.ncl.edu.tw/handle/30320600697375739649.
Full text
25
Hildum, David Waldau. "Flexibility in a knowledge-based system for solving dynamic resource-constrained scheduling problems." 1994. https://scholarworks.umass.edu/dissertations/AAI9510483.
Full textAbstract:
The resource-constrained scheduling problem (RCSP) involves the assignment of a limited set of resources to a collection of tasks, with the intent of satisfying some particular qualitative objective, under a variety of technological and temporal constraints. Real-world environments, however, introduce a variety of complications to the standard RCSP. The dynamic resource-constrained scheduling problem describes a class of real-world RCSPs that exist within the context of dynamic and unpredictable environments, where the details of the problem are often incomplete, and subject to change over time, without notice. Previous approaches to solving resource-constrained scheduling problems failed to focus on the dynamic nature of real-world environments. The scheduling process occurs away from the environment in which the resulting schedule is executed. Complete prior knowledge of the order set is assumed, and reaction to changes in the environment, if at all, is limited. We have developed a generic, multi-faceted, knowledge-based approach to solving dynamic resource-constrained scheduling problems, which focuses on issues of flexibility during the solution process to enable effective reaction to dynamic environments. Our approach is characterized by a highly opportunistic control scheme that provides the ability to adapt quickly to changes in the environment, a least-commitment scheduling procedure that preserves maneuverability by explicitly incorporating slack time into the developing schedule, and the systematic consultation of a range of relevant scheduling perspectives at key decision-making points that provides an informed view of the current state of problem-solving at all times. The Dynamic Scheduling System (DSS) is a working implementation of our scheduling approach, capable of representing a wide range of dynamic RCSPs, and producing quality schedules under a variety of real-world conditions. It handles a number of additional domain complexities, such as inter-order tasks and mobile resources with significant travel requirements. We discuss our scheduling approach and its application to two different RCSP domains, and evaluate its effectiveness in each, using special application systems built with DSS.
26
Lin, Wei-Da, and 林緯達. "Solving dynamic facilities location problems with time covering constraint." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/94424073381294076131.
Full textAbstract:
碩士國立高雄第一科技大學
運輸倉儲營運所
93
Most of the conventional facilities location problems used Euclid distance to form the main goal while solving the optimal problem. However, it is not realistic when implementing the real world case. . Since using Euclid distance for transportation cost and covering range is already unable to meet today’s hightime-sensitive customers, the consideration of real network situation is valuable. In this research it primarily uses time as covering measurement. In this research, facilities location problems include maximal covering problem and set covering problem. Moreover, real map data was used to construct the network and an application was developed to verify the optimization model. The main methodology used here is the Lagrangean relaxation method. Two models were proposed in this research. One is the maximal covering location problem with time covering and multi planning period. It mainly discusses the specific number of facilities that try to cover maximal demand during planning periods. The other is the set covering location problem with time covering and multi planning period. It mainly discusses how to cover all demand with specific covering range to pursue minimizing total cost. Additionally, the results obtained from this algorithm model were compared with the results gained from the optimization software –Lingo to verify the performance. Finally it concludes and gives some future research.
27
"A fuzzy constraint satisfaction approach to achieving stability in dynamic constraint satisfaction problems." 2001. http://library.cuhk.edu.hk/record=b5890771.
Full textAbstract:
by Wong, Yin Pong Anthony.Thesis (M.Phil.)--Chinese University of Hong Kong, 2001.
Includes bibliographical references (leaves 101-107).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Constraint Satisfaction Problems --- p.2
Chapter 1.2 --- Solution Stability in Dynamic Constraint Satisfaction Problems --- p.3
Chapter 1.3 --- Motivation of the Research --- p.5
Chapter 1.4 --- Overview of the Thesis --- p.5
Chapter 2 --- Related Work --- p.7
Chapter 2.1 --- Complete Search Algorithms --- p.7
Chapter 2.1.1 --- DnAC-4 --- p.8
Chapter 2.1.2 --- ac --- p.9
Chapter 2.1.3 --- DnAC-6 --- p.9
Chapter 2.2 --- Algorithms for Stability --- p.10
Chapter 2.2.1 --- Bellicha --- p.10
Chapter 2.2.2 --- Dynamic Dynamic Backtracking --- p.11
Chapter 2.2.3 --- Wallace and Freuder --- p.12
Chapter 2.2.4 --- Unimodular Probing --- p.13
Chapter 2.2.5 --- Train Rescheduling --- p.14
Chapter 2.3 --- Constrained Optimization Algorithms --- p.14
Chapter 2.3.1 --- Guided Local Search --- p.14
Chapter 2.3.2 --- Anytime CSA with Iterative Deepening --- p.15
Chapter 2.4 --- A Real-life Application --- p.16
Chapter 3 --- Background --- p.17
Chapter 3.1 --- Fuzzy Constraint Satisfaction Problems --- p.17
Chapter 3.2 --- Fuzzy GENET --- p.19
Chapter 3.2.1 --- Network Architecture --- p.19
Chapter 3.2.2 --- Convergence Procedure --- p.21
Chapter 3.3 --- Deficiency in Fuzzy GENET --- p.24
Chapter 3.4 --- Rectification of Fuzzy GENET --- p.26
Chapter 4 --- Using Fuzzy GENET for Solving Stability Problems --- p.30
Chapter 4.1 --- Modelling Stability Problems as FCSPs --- p.30
Chapter 4.2 --- Extending Fuzzy GENET for Solving Stability Problems --- p.36
Chapter 4.3 --- Experiments --- p.38
Chapter 4.3.1 --- Dynamic CSP Generation --- p.39
Chapter 4.3.2 --- Problems Using Hamming Distance Function --- p.41
Chapter 4.3.2.1 --- Variation in Number of Variables --- p.42
Chapter 4.3.2.2 --- Variation in Domain Size --- p.45
Chapter 4.3.2.3 --- Variation in Density and Tightness --- p.47
Chapter 4.3.3 --- Comparison in Using Different Thresholds --- p.47
Chapter 4.3.4 --- Problems Using Manhattan Distance Function --- p.50
Chapter 5 --- Enhancement of the Modelling Scheme --- p.56
Chapter 5.1 --- Distance Bound --- p.56
Chapter 5.2 --- Enhancement of Convergence Procedure --- p.57
Chapter 5.3 --- Comparison with Optimal Solutions --- p.60
Chapter 5.4 --- Comparison with Fuzzy GENET(dcsp) --- p.64
Chapter 5.4.1 --- Medium-sized Problems --- p.64
Chapter 5.4.2 --- The 150-10-15-15 Problem --- p.67
Chapter 5.4.3 --- Variation in Density and Tightness --- p.73
Chapter 5.4.4 --- Variation in Domain Size --- p.76
Chapter 5.5 --- Analysis of Fuzzy GENET(dcsp2) --- p.94
Chapter 6 --- Conclusion --- p.98
Chapter 6.1 --- Contributions --- p.98
Chapter 6.2 --- Future Work --- p.99
Bibliography --- p.101
28
Lee, Tsung-Yi, and 李宗益. "Dynamic User-Optimal Route Choice Problem with Side Constraint." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/15986657165573325012.
Full textAbstract:
碩士國立中央大學
土木工程研究所
88
This thesis, as follow-up study of Wang (1999), Chou (1999) and Y.J. Chen (1999), attempts to further some important issues based on the dynamic user-optimal route choice model formulated using variational inequality approach by Chen and Hsueh (1998a,b). It includes the dynamic user-optimal route choice model formulated with decision variables of link exit flows, the dynamic exit-capacitated user-optimal route choice model, and comparison of the gradient projection method versus the Evans algorithm in the dynamic user-optimal doubly constrained O-D pair/departure time/route choice model. The non-convergence phenomenon in the dynamic user-optimal route choice model formulated with decision variables of link exit flows is more than with decision variables of link inflows (Chen and Hsueh, 1998a). So the dynamic exit-capacitated user-optimal route choice model is formulated with decision variables of link inflows and solved by transforming variable. Moreover, in the dynamic user-optimal doubly constrained O-D pair/departure time/route choice model, computational experience with three test networks indicates that the gradient projection method are in general superior to the Evans algorithm in terms of execution time.
29
Yu, Hsuan-Hui, and 余宣慧. "A two-machine flowshop dynamic scheduling problem with limit waiting time constraints." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/47304401290046596533.
Full textAbstract:
碩士國立雲林科技大學
工業工程與管理研究所碩士班
92
This research studies the two-machine flowshop scheduling problem with limited waiting time constraints. That is jobs must begin processing on a certain machine within a predefined time constraint after completing processing in a prior machine. The objective is to minimize the total weight tardiness. A two-phase scheduling approach is developed to solve this problem. In the first phase, a initial sequence of jobs by simple dynamic dispatching rule is developed. In second phase, preliminary job sequence developed in phase one is divided into subsequence. Each subsequence is considered as a subproblem which is solved by Integer Programming. In static scheduling scenario, when more jobs have tight due date results from the two phase approach are quite near the optimal one. In dynamic scheduling scenario, the two-phase scheduling method is superior to Apparent Tardiness Cost (ATC) rule and Cost Over Time (COVERT) rule in total tardiness and total flow time.
30
Matsho, Stephens Kgalushi. "The dynamics of the compression of a motor vehicle tyre constrained by the road." Thesis, 2012. http://encore.tut.ac.za/iii/cpro/DigitalItemViewPage.external?sp=1000620.
Full textAbstract:
M. Tech. : Mathematical Technology.Attempts will be made to extend the elementary quarter-mass models (for instance Gillepse, 1992, [5]; Kiecke & Nielsen, 2000, [6] and Singiresu, 2004, [7]) of a motor vehicle suspension system to include the radial vibrations of a rubber tyre in the model. Tangential vibrations of the tyre surface were investigated by Bekker (2009, [8]) and the possible incorporation of such vibrations into a suspension model invites the possibility of future study.
31
Mdletye, Mbongeni Andile. "Exploring the elements and dynamics of transformational change." Thesis, 2013. http://hdl.handle.net/10210/8359.
Full textAbstract:
D.Phil. (Leadership in Performance and Change)The desire for organisational competitiveness as a result of factors such as the changing and increasing needs of customers, deregulation, the globalisation of the economy and work, the increasing competition due to globalisation, the need to control costs and increase efficiency, as well as the fast pace of technological advancement, has compelled organisations to embark on changes that take place at a fast and ever-increasing rate. However, it was noted that organisations are not at all succeeding in implementing and institutionalising change initiatives effectively. There is a high failure rate in the implementation of transformational change efforts, and this is attributed to the fact that managers are not well-equipped to deal with challenges associated with the implementation of transformational changes in organisations. As a result of the high failure rate in change implementation, there had been a number of empirical studies conducted, which investigated reasons behind this low success rate. Unfortunately very few studies have focused on the human side of transformational change. Most of the researches have dwelt more on the technical side of change. This quantitative study was then conducted in order to identify and explore the elements and dynamics of transformational change, which can be regarded as constituting the human dimension of transformational change. Specifically, the main objective of this study was to determine the extent to which the elements and dynamics of transformational change (that is, perceptions, reactions, experiences, personal impact, and organisational impact) relate to the status of the change process. This research adopted a two-pronged approach, which incorporated a literature study first, and thereafter an empirical study. The literature study contextualised the elements and dynamics of transformational change within the Correctional Services environment. An overview of transformational change in the Department of Correctional Services was also provided. Based on the results of the literature study, a theoretical model, which hypothesised the relationships between perceptions and experience on one side, and the status of change on the other, was developed and empirically tested. The empirical data was collected by means of two survey questionnaires – one for correctional officials and the other for offenders, which were administered to 1000 correctional officials and 500 offenders. Methodologically, the study was guided by an exploratory, survey, descriptive, correlational and explanatory research designs, which were underpinned by ontological and epistemological perspectives. All completed and returned questionnaires were computed to analyse the responses of the respondents. The results of the analysis of data showed that the DCS change was characterised by positive perceptions; positive, negative and introspective-anxious experiences; negative responses in terms of emotional reactions and resistance; negative personal impact at intrapersonal and interpersonal levels; and positive organisational impact as the key aspects of the elements and dynamics of transformational change. The discussion in this thesis revolves around the above-named elements and dynamics of transformational change. Through performing exploratory and confirmatory factor analyses, a three-factor measurement model which encompassed perception, experience and the status of change, was identified and confirmed. The structural equation modelling found that both perceptions and experiences were the predictors of the status of change.
32
Terekhov, Daria. "Integrating Combinatorial Scheduling with Inventory Management and Queueing Theory." Thesis, 2013. http://hdl.handle.net/1807/36017.
Full textAbstract:
The central thesis of this dissertation is that by combining classical scheduling methodologies with those of inventory management and queueing theory we can better model, understand and solve complex real-world scheduling problems. In part II of this dissertation, we provide models of a realistic supply chain scheduling problem that capture both its combinatorial nature and its dependence on inventory availability. We present an extensive empirical evaluation of how well implementations of these models in commercially available software solve the problem. We are therefore able to address, within a specific problem, the need for scheduling to take into account related decision-making processes. In order to simultaneously deal with combinatorial and dynamic properties of real scheduling problems, in part III we propose to integrate queueing theory and deterministic scheduling. Firstly, by reviewing the queueing theory literature that deals with dynamic resource allocation and sequencing and outlining numerous future work directions, we build a strong foundation for the investigation of the integration of queueing theory and scheduling. Subsequently, we demonstrate that integration can take place on three levels: conceptual, theoretical and algorithmic. At the conceptual level, we combine concepts, ideas and problem settings from the two areas, showing that such combinations provide insights into the trade-off between long-run and short-run objectives. Next, we show that theoretical integration of queueing and scheduling can lead to long-run performance guarantees for scheduling algorithms that have previously been proved only for queueing policies. In particular, we are the first to prove, in two flow shop environments, the stability of a scheduling method that is based on the traditional scheduling literature and utilizes processing time information to make sequencing decisions. Finally, to address the algorithmic level of integration, we present, in an extensive future work chapter, one general approach for creating hybrid queueing/scheduling algorithms. To our knowledge, this dissertation is the first work that builds a framework for integrating queueing theory and scheduling. Motivated by characteristics of real problems, this dissertation takes a step toward extending scheduling research beyond traditional assumptions and addressing more realistic scheduling problems.
33
Azi, Nabila. "Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules." Thèse, 2010. http://hdl.handle.net/1866/4876.
Full textAbstract:
Cette thèse porte sur les problèmes de tournées de véhicules avec
fenêtres de temps où un gain est associé à chaque client et où l'objectif est
de maximiser la somme des gains recueillis moins les coûts de transport.
De plus, un même véhicule peut effectuer plusieurs tournées durant
l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple,
dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées
complètes de travail. Nous croyons que ce type de
problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries
électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile.
Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la
littérature consacrée aux
problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une
réutilisation des véhicules. Nous présentons les
méthodologies générales adoptées pour les résoudre, soit les méthodes exactes,
les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées
dynamiques où certaines données sur le problème ne sont pas connues à l'avance.
Dans le second chapitre, nous décrivons un algorithme
exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est
de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec
gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court
chemin élémentaire avec contraintes de ressources.
Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise.
Le troisième chapitre propose donc
une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux
hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes).
Dans le quatrième chapitre, qui traite du cas dynamique,
une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des
requêtes à venir. L'approche repose sur la génération de scénarios pour
différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir
une nouvelle
requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête.
Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues
de recherche future.This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.