Deadlocks are critical events in Flexible Manufacturing Cells (FMC) that result from circular waits among a set of resources. Circular waits happen when a set of resources with finite capacity are in a permanent hold due to wait state to admit new jobs. Past literature examines the deadlock-free scheduling in FMCs considering many types of resources and techniques. This thesis proposes a new resource-oriented deadlock-free approach using a robot equipped with dual-grippers serving as a material handler in a FMC. The proposed methodology uses Constraint Programming (CP). The system performance is analyzed using different buffer configurations. Many test problems are generated to validate the developed models. The finding demonstrates that the proposed dual-gripper robot (DGR) can outperform the single-gripper robot (SGR) in many settings for FMCs. Likewise, the experience with the CP for the modeling and solving approach proposed in this research consolidates its application to FMC deadlock-free scheduling problems.

The rapid expansion of low-density suburban areas in North America has led to new travel patterns that require transit services to be more flexible. Flex-Route transit service, which combines fixed-route transit service with elements of demand-responsive transit service, has emerged as a viable transit option to address the travel needs of the residents of these areas. Existing literature in this field, however, is limited and lacks any comprehensive analysis of Flex-Route planning, design and scheduling. This research aims at exploring Flex-Route transit service to provide detailed guidelines for the planning and design of the service, as well as developing a new scheduling system for this type of unique service. Accordingly, the objectives of this research are: assessing the practicality of Flex-Route transit service in serving low-density suburban areas; identifying essential Flex-Route planning steps and design parameters; determining the feasibility and cost of replacing fixed-route transit with Flex-Route service; and developing a Flex-Route-specific dynamic scheduling system that relies on recent developments in computer and communication technologies. In this regard, we develop an analytical model that addresses several design parameters and provide a detailed analysis that includes, among other parameters, finding optimal values for Flex-Route service area and slack time. Furthermore, the analytical model includes a feasibility and cost analysis that estimates the cost incurred by several stakeholders if Flex-Route service is chosen to replace fixed-route service. The core of the scheduling system is a new developed algorithm – the Constrained-Insertion Algorithm- that exploits the powerful search techniques of Constraint Programming. The scheduling system can handle the daily operations of Flex-Route transit services; it accepts daily (or dynamic) inputs and, in minimal time, produces very cost-effective and reliable schedules. Moreover, the scheduling system has the ability to be used as simulation tool to allow transit operators to assess the feasibility and performance of proposed Flex-Route transit services before implementation. The applicability of the analytical model as well as the performance of the scheduling system were subsequently evaluated and validated through process that included testing on a case study in the City of Oakville, Canada.

The rapid expansion of low-density suburban areas in North America has led to new travel patterns that require transit services to be more flexible. Flex-Route transit service, which combines fixed-route transit service with elements of demand-responsive transit service, has emerged as a viable transit option to address the travel needs of the residents of these areas. Existing literature in this field, however, is limited and lacks any comprehensive analysis of Flex-Route planning, design and scheduling. This research aims at exploring Flex-Route transit service to provide detailed guidelines for the planning and design of the service, as well as developing a new scheduling system for this type of unique service. Accordingly, the objectives of this research are: assessing the practicality of Flex-Route transit service in serving low-density suburban areas; identifying essential Flex-Route planning steps and design parameters; determining the feasibility and cost of replacing fixed-route transit with Flex-Route service; and developing a Flex-Route-specific dynamic scheduling system that relies on recent developments in computer and communication technologies. In this regard, we develop an analytical model that addresses several design parameters and provide a detailed analysis that includes, among other parameters, finding optimal values for Flex-Route service area and slack time. Furthermore, the analytical model includes a feasibility and cost analysis that estimates the cost incurred by several stakeholders if Flex-Route service is chosen to replace fixed-route service. The core of the scheduling system is a new developed algorithm – the Constrained-Insertion Algorithm- that exploits the powerful search techniques of Constraint Programming. The scheduling system can handle the daily operations of Flex-Route transit services; it accepts daily (or dynamic) inputs and, in minimal time, produces very cost-effective and reliable schedules. Moreover, the scheduling system has the ability to be used as simulation tool to allow transit operators to assess the feasibility and performance of proposed Flex-Route transit services before implementation. The applicability of the analytical model as well as the performance of the scheduling system were subsequently evaluated and validated through process that included testing on a case study in the City of Oakville, Canada.

Deadlocks are critical events in Flexible Manufacturing Cells (FMC) that result from circular waits among a set of resources. Circular waits happen when a set of resources with finite capacity are in a permanent hold due to wait state to admit new jobs. Past literature examines the deadlock-free scheduling in FMCs considering many types of resources and techniques. This thesis proposes a new resource-oriented deadlock-free approach using a robot equipped with dual-grippers serving as a material handler in a FMC. The proposed methodology uses Constraint Programming (CP). The system performance is analyzed using different buffer configurations. Many test problems are generated to validate the developed models. The finding demonstrates that the proposed dual-gripper robot (DGR) can outperform the single-gripper robot (SGR) in many settings for FMCs. Likewise, the experience with the CP for the modeling and solving approach proposed in this research consolidates its application to FMC deadlock-free scheduling problems.

Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1, x2,..., x n and a list of constraints of the form "(x 7, x2,..., x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class. / In recent years, logical and algebraic perspectives have been particularly successful in classifying CSPs. A major weapon in the arsenal of the logical perspective is the database-theory-inspired logic programming language called Datalog. A Datalog program can be used to solve a restricted class of CSPs by either accepting or rejecting a (suitably encoded) set of input constraints. Inspired by Dalmau's work on linear Datalog and Reingold's breakthrough that undirected graph connectivity is in logarithmic space, we use a new restriction of Datalog called symmetric Datalog to identify a class of CSPs solvable in logarithmic space. We establish that expressibility in symmetric Datalog is equivalent to expressibility in a specific restriction of second order logic called Symmetric Restricted Krom Monotone SNP that has already received attention for its close relationship with logarithmic space. / We also give a combinatorial description of a large class of CSPs lying in L by showing that they are definable in symmetric Datalog. The main result of this thesis is that directed st-connectivity and a closely related CSP cannot be defined in symmetric Datalog. Because undirected st-connectivity can be defined in symmetric Datalog, this result also sheds new light on the computational differences between the undirected and directed st-connectivity problems.

In recent years, wireless sensor networks (WSNs) have grown rapidly and have had a substantial impact in many applications. A WSN is a network that consists of interconnected autonomous nodes that monitor physical and environmental conditions, such as temperature, humidity, pollution, etc. If required, nodes in a WSN can perform actions to affect the environment. WSNs present an interesting and challenging field of research due to the distributed nature of the network and the limited resources of the nodes. It is necessary for a node in a WSN to be small to enable easy deployment in an environment and consume as little energy as possible to prolong its battery lifetime. There are many challenges in WSNs, such as programming a large number of nodes, designing communication protocols, achieving energy efficiency, respecting limited bandwidth, and operating with limited memory. WSNs are further constrained due to the deployment of the nodes in indoor and outdoor environments and obstacles in the environment. In this dissertation, we study some of the fundamental optimisation problems related to the programming, coverage, mobility, data collection, and data loss of WSNs, modelled as standalone optimisation problems or as optimisation problems integrated with protocol design. Our proposed solution methods come from various fields of research including constraint programming, integer linear programming, heuristic-based algorithms, and data inference techniques. / ProFuN

Several important compiler optimizations such as instruction scheduling and register allocation are fundamentally hard and are usually solved using heuristics or approximate solutions. In contrast, this thesis examines optimal solutions to three combinatorial problems in compiler optimization. The first problem addresses instruction scheduling for clustered architectures, popular in embedded systems. Given a set of instructions the optimal solution gives the best possible schedule for a given clustered architectural model. The problem is solved using a decomposition technique applied to constraint programming which determines the spatial and temporal schedule using an integrated approach. The experiments show that our solver can tradeoff some compile time efficiency to solve most instances in standard benchmarks giving significant performance improvements. The second problem addresses instruction selection in the compiler code generation phase. Given the intermediate representation of code the optimal solution determines the sequence of equivalent machine instructions as it optimizes for code size. This thesis shows that a large number of benchmark instances can be solved optimally using constraint programming techniques. The third problem addressed is the placement of data in memory for efficient cache utilization. Using the data access patterns of a given program, our algorithm determines a placement to reorganize data in memory which would result in fewer cache misses. By focusing on graph theoretic placement techniques it is shown that there exist, in special cases, efficient and optimal algorithms for data placement that significantly improve cache utilization. We also propose heuristic solutions for solving larger instances for which provably optimal solutions cannot be determined using polynomial time algorithms. We demonstrate that cache hit rates can be significantly improved by using profiling techniques over a wide range of benchmarks and cache configurations.

Workflow is a collection of tasks organized to accomplish some business process. It also defines the order of task invocation or conditions under which task must be invoked, task synchronization, and information flow. Before the execution of the workflow, a correct execution schema, in other words, the schedule of the workflow, must be determined. Workflow scheduling is finding an execution sequence of tasks that obeys the business logic of workflow. Research on specification and scheduling of workflows has concentrated on temporal and causality constraints, which specify existence and order dependencies among tasks. However, another set of constraints that specify resource allocation is also equally important. The resources in a workflow environment are agents such as person, machine, software, etc. that execute the task. Execution of a task has a cost and this may vary depending on the resources allocated in order to execute that task. Resource allocation constraints define restrictions on how to allocate resources, and scheduling under resource allocation constraints provide proper resource allocation to tasks. In this thesis, we present two approaches to specify and schedule workflows under resource allocation constraints as well as temporal and causality constraints. In the first approach, we present an architecture whose core and novel parts are a specifi- cation language with the ability to express resources and resource allocation constraints and a scheduler module that contains a constraint solver in order to find correct resource assignments. In the second approach, we developed a new logical formalism, called Concurrent Constraint Transaction Logic (CCTR) which integrates constraint logic programming (CLP) and Concurrent Transaction Logic, and a logic-based work- flow scheduler that is based on this new formalism. CCTR has the constructs to specify resource allocation constraints as well as workflows and it provides semantics for these specifications so that validity of a schedule can be checked.

Univ., Diss.--Pisa, 2003.

Thesis (M.S. in Computer Science)--Naval Postgraduate School, Sept. 2004. / Thesis advisor(s): George W. Dinolt. Includes bibliographical references (p. 133-136). Also available online.