In the literature, most of the researchers studying assembly line balancing have only considered task assignments. However, resources are needed to perform the tasks. Therefore, assigning resources related to tasks be...
详细信息
In the literature, most of the researchers studying assembly line balancing have only considered task assignments. However, resources are needed to perform the tasks. Therefore, assigning resources related to tasks becomes more realistic when assigning tasks to stations. In the general case of the problem, the task is performed with a specified amount of resources. If resource types such as a, b, c are required to perform tasks in an assembly line, the combination of tasks required from these resources should also be assigned to the stations. This type of problem is defined as general resources-constrained assembly line balancing problem (GRCALBP). In this study, GRCALBP is addressed to minimize cycle time and resource usage for a given number of stations. New constraint programming (CP) models based on conjunction normal form are proposed. The CP models are tested with generated problem instances from the data set in the literature. The experimental results show that CP is an efficient and effective modeling technique to solve GRCALBP. Finally, suggestions are made regarding alternative objective functions.
In a polydiagonal subspace of the Euclidean space, certain components of the vectors are equal (synchrony) or opposite (anti-synchrony). Polydiagonal subspaces invariant under a matrix have many applications in graph ...
详细信息
In a polydiagonal subspace of the Euclidean space, certain components of the vectors are equal (synchrony) or opposite (anti-synchrony). Polydiagonal subspaces invariant under a matrix have many applications in graph theory and dynamical systems, especially coupled cell networks. We describe invariant polydiagonal subspaces in terms of coloring vectors. This approach gives an easy formulation of a constraint satisfaction problem for finding invariant polydiagonal subspaces. Solving the resulting problem with existing state-of-the-art constraint solvers greatly outperforms the currently known algorithms.
Professional magicians employ the use of interesting properties of a deck of cards to create magical effects. These properties were traditionally discovered through trial and error, the application of heuristics or an...
详细信息
Professional magicians employ the use of interesting properties of a deck of cards to create magical effects. These properties were traditionally discovered through trial and error, the application of heuristics or analytical proofs. Those proofs come from diverse mathematical areas such as the set, number and graph theory. We discuss the limitations of relying on humans for such methods and present how professional magicians can use constraint programming as a computer-aided design tool (CAD) to search for desired properties in a deck of cards. Furthermore, we implement a solution in Python by making use of generative magic to design a new effect, demonstrating how this process broadens the level of freedom a magician can decree to their volunteers while retaining control of the outcomes of the magic. Finally, we demonstrate that the model can be easily adapted to multiple languages by presenting multiple variations of the effect supporting American English and Brazilian Portuguese.
constraint programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time need...
详细信息
constraint programming typically uses the technique of depth-first branch and bound as the method of solving optimization problems. Although this method can give the optimal solution, for large problems, the time needed to find the optimal can be prohibitive. This paper introduces a method for using local search techniques within a constraint programming framework, and applies this technique to vehicle routing problems. We introduce a constraint programming model for vehicle routing, and a system for integrating constraint programming and local search techniques. We then describe how the method can be accelerated by handling core constraints using fast local checks, while other more complex constraints are left to the constraint propagation system. We have coupled our local search method with a meta-heuristic to avoid the search being trapped in local minima. Several meta-heuristics are investigated ranging from a simple Tabu Search method to Guided Local Search. An empirical study over benchmark problems shows the relative merits of these techniques. Investigations indicate that the specific long-term memory technique used by Guided Local Search can be used as a diversification method for Tabu Search, resulting in significant benefit. Several new best solutions on the Solomon problems are found in relatively few iterations of our algorithm.
One of the major strengths of constraint programming is the flexibility and expressiveness of models in that computational paradigm, which make it easy to add problem-dependent constraints without having to modify the...
详细信息
One of the major strengths of constraint programming is the flexibility and expressiveness of models in that computational paradigm, which make it easy to add problem-dependent constraints without having to modify the solution strategy. We show here what needs to be done in order to adapt a constraint programming algorithm for the traveling salesman problem with time windows so that it can handle multiple time windows. Computational results are also presented on a set of instances created for that little-studied problem. (C) 1999 Elsevier Science B.V. All rights reserved.
constraint programming is a classical artificial intelligence paradigm characterised by its flexibility for the modelling of complex problems. In the field of space operations, this approach has been successfully used...
详细信息
constraint programming is a classical artificial intelligence paradigm characterised by its flexibility for the modelling of complex problems. In the field of space operations, this approach has been successfully used for mission planning and scheduling. This manuscript proposes a framework that leverages the strengths of constraint programming for the preliminary analysis of space missions, introducing some modifications to tailor it to the application at hand. Specifically, it uses constraint propagation and search techniques to thoroughly explore the configuration space of a mission in an efficient manner. Consequently, it is able to quantify the performance of precomputed mission choices with respect to the mission requirements, as well as generate new ones that optimise such performance. The proposed methodology has been particularised for two application cases involving active debris removal missions for large constellations in low Earth orbit, namely, a chaser case and a mothership case. The chaser case considers a servicing satellite that rendezvouses with the failed satellites of the constellation and directly transports them to a disposal orbit. The mothership case comprises a servicing satellite that installs deorbiting kits in each of the failed satellites, except for the one removed in the last place. This way, the servicing satellite will only transport this object, while the deorbiting kits will carry out the disposal of the rest of them. This methodology has been successfully used to evaluate a preliminary mission analysis of both application cases developed under ESA's Sunrise project. (c) 2024 COSPAR. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized ...
详细信息
This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances.
This paper discusses a new method to perform propagation over a (two-layer, feed-forward) Neural Network embedded in a constraint programming model. The method is meant to be employed in Empirical Model Learning, a te...
详细信息
This paper discusses a new method to perform propagation over a (two-layer, feed-forward) Neural Network embedded in a constraint programming model. The method is meant to be employed in Empirical Model Learning, a technique designed to enable optimal decision making over systems that cannot be modeled via conventional declarative means. The key step in Empirical Model Learning is to embed a Machine Learning model into a combinatorial model. It has been showed that Neural Networks can be embedded in a constraint programming model by simply encoding each neuron as a global constraint, which is then propagated individually. Unfortunately, this decomposition approach may lead to weak bounds. To overcome such limitation, we propose a new network-level propagator based on a non-linear Lagrangian relaxation that is solved with a subgradient algorithm. The method proved capable of dramatically reducing the search tree size on a thermal-aware dispatching problem on multicore CPUs. The overhead for optimizing the Lagrangian multipliers is kept within a reasonable level via a few simple techniques. This paper is an extended version of [27], featuring an improved structure, a new filtering technique for the network inputs, a set of overhead reduction techniques, and a thorough experimentation.
Since their introduction, local search algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of ...
详细信息
Since their introduction, local search algorithms have consistently represented the state of the art in solution techniques for the classical job-shop scheduling problem. This dominance is despite the availability of powerful search and inference techniques for scheduling problems developed by the constraint programming community. In this paper, we introduce a simple hybrid algorithm for job-shop scheduling that leverages both the fast, broad search capabilities of modern tabu search algorithms and the scheduling-specific inference capabilities of constraint programming. The hybrid algorithm significantly improves the performance of a state-of-the-art tabu search algorithm for the job-shop problem and represents the first instance in which a constraint programming algorithm obtains performance competitive with the best local search algorithms. Furthermore, the variability in solution quality obtained by the hybrid is significantly lower than that of pure local search algorithms. Beyond performance demonstration, we perform a series of experiments that provide insights into the roles of the two component algorithms in the overall performance of the hybrid.
The cyclic hoist scheduling problem (CHSP) is a well-studied optimisation problem due to its importance in industry. Despite the wide range of solving techniques applied to the CHSP and its variants, the models have r...
详细信息
The cyclic hoist scheduling problem (CHSP) is a well-studied optimisation problem due to its importance in industry. Despite the wide range of solving techniques applied to the CHSP and its variants, the models have remained complicated and inflexible, or have failed to scale up with larger problem instances. This article re-examines modelling of the CHSP and proposes a new simple, flexible constraint programming formulation. We compare current state-of-the-art solving technologies on this formulation, and show that modelling in a high-level constraint language, MiniZinc, leads to both a simple, generic model and to computational results that outperform the state of the art. We further demonstrate that combining integer programming and lazy clause generation, using the multiple cores of modern processors, has potential to improve over either solving approach alone.
暂无评论