In the storage location assignment problem under a picker-to-parts system (SLAP-FP), we assign warehouse space to products based on customer orders. The distance we have to travel to pick up customer orders and the fr...
详细信息
In the storage location assignment problem under a picker-to-parts system (SLAP-FP), we assign warehouse space to products based on customer orders. The distance we have to travel to pick up customer orders and the frequency of restocking in the warehouse depend on the location of the products and their allocated space. The goal of SLAP-FP is to minimize the costs of restocking the products and picking the orders. This study introduces a novel constraint programming formulation to solve the SLAP-FP. The model uses logical rules and rational expressions to describe the problem concisely. Numerical results with standard solvers show that the proposed model significantly outperforms the previously known integer programming approach. Specifically, the constraint programming model is especially good at finding better solutions in large instances with many different products.
The literature studies assume that resources used to be perform the tasks are certain and homogenous in any assembly line. However, tasks may need to be processed by general resource requirements in real life. These g...
详细信息
The literature studies assume that resources used to be perform the tasks are certain and homogenous in any assembly line. However, tasks may need to be processed by general resource requirements in real life. These general resources could be classified by usage of resources such as simple or multiple, alternative and concurrent. The problem which is related to assignment of the task to any workstation and assignment of resources needed by the task simultaneously is defined as resource-constrained assembly line balancing problems (RCALBPs). In this study, a multiobjective model with minimization of cycle time and resource usage for a given number of stations is modeled to solve the RCALBP for the first time. Alternative and general resource types for tasks and using more than two resource type requirements are also considered. A constraint programming model is developed and solved to find the optimal solutions of these problems. The proposed models are tested with sample scenarios to show the effectiveness of the model.
In this paper, we consider a deadline-constrained MR scheduling problem of minimizing energy consumption in Hadoop's generic resource manager known as yet another resource negotiator. The problem has been modeled ...
详细信息
In this paper, we consider a deadline-constrained MR scheduling problem of minimizing energy consumption in Hadoop's generic resource manager known as yet another resource negotiator. The problem has been modeled as an integer programming (IP) problem using the time-indexed decision variables. We propose two solution approaches to the problem. First, we give a heuristic algorithm that generates sub-optimal schedules in polynomial time. Second, we propose a novel constraint programming (CP) model (as an alternative to the IP model) which always generates optimal schedules when solved by a CP solver. The CP technique is a relatively new and an alternative approach to IP-based branch-and-cut algorithm to exactly solve NP-hard optimization problems. We performed several experiments to compare both proposed solution approaches over real data traces of a wide variety of MR jobs from the HiBench and PUMA benchmark suite. It is noticed that for large-scale big data jobs, the heuristic algorithm provides sub-optimal results in a very small amount of time. On the other hand, the CP approach not only gives optimal results but also takes a small amount of time when compared to IP-based approaches. Therefore, it can be used in non-time-critical situations for getting an optimal schedule. Besides this, a few experiments were also performed to compare the tightest satisfiable deadline under both approaches with the conclusion that the CP technique is able to produce optimal schedules in tighter deadline constraints than the heuristic approach. Moreover, we investigate the sensitivity of total energy consumption of tasks and the execution time of both approaches separately on the number of tasks and deadlines.
Several parallel assembly lines are balanced simultaneously in the parallel assembly line balancing problem (PALBP), which lead to several advantages such as increased capacity and flexibility against the changes in d...
详细信息
Several parallel assembly lines are balanced simultaneously in the parallel assembly line balancing problem (PALBP), which lead to several advantages such as increased capacity and flexibility against the changes in demand. Recently, the parallel robotic assembly line balancing problem (PRALBP) has emerged in the literature, due to the increase in automation of assembly lines. Robotic assembly lines have a significant potential to improve the consistency, efficiency and quality of the assembly processes. In this study, novel constraint programming (CP) models are presented for the PALBP and PRALBP. Comprehensive computational experiments by comparisons with the state-of-the-art algorithms show that the proposed CP models can achieve effective solutions for the PALBP and PRALBP in a short computational time. Particularly, the developed CP model improves the current best-known results for most of the benchmark instances for the PRALBP. Even though the PALBP has been extensively studied in the literature with the productivity-related objectives, the studies on PRALBP regarding the energy-efficiency have been very limited. Therefore, an energy-efficient PRALBP (E-PRALBP) is also addressed in this study, considering both cycle time-oriented and energy consumption-oriented variants of the problem. As an extension of the E-PRALBP, E-PRALBP with zoning constraints and limited number of robots (E-PRALBP-Z) is also considered. Consequently, this study presents novel CP models for the E-PRALBP and E-PRALBP-Z for the first time in the literature. A comprehensive computational study show that the proposed CP models can solve the E-PRALBP and E-PRALBP-Z effectively.
In recent years, the two-sided assembly line (TAL) has become popular since it offers several advantages, such as fewer workstations and movement of fewer workers inside the line. TAL assumes that each mated workstati...
详细信息
In recent years, the two-sided assembly line (TAL) has become popular since it offers several advantages, such as fewer workstations and movement of fewer workers inside the line. TAL assumes that each mated workstation contains two workstations in parallel, and it can process tasks on the left, on the right or on either side. However, in a traditional TAL, only one worker is responsible for completing the task at each workstation. Dealing with large-size products and massive operations may require more than one operator to perform tasks. This study proposes mixed-integer linear programming and constraint programming (CP) models for the two-sided assembly line balancing problem with multi-operator stations for the purpose of solving small- and large-size problems. Computational results indicate that the CP model finds optimal solutions for all instances. It is useful to highlight that the CP model is highly concise and solved by a black-box, commercial solver.
This paper proposes a constraint programming model for computing the finite horizon single-item inventory problem with stochastic demands in discrete time periods with service-level constraints under the non-stationar...
详细信息
This paper proposes a constraint programming model for computing the finite horizon single-item inventory problem with stochastic demands in discrete time periods with service-level constraints under the non-stationary version of the "periodic review, order-up-to-level" policy (i.e., non-stationary (R, S) or, simply (R, S,)). It is observed that the modeling process is more natural and the required number of variables is smaller compared to the MIP formulation of the same problem. The computational tests show that the CP approach is more tractable than the conventional MIP formulation. Two different domain reduction methods are proposed to improve the computational performance of solution algorithms. The numerical experiments confirmed the effectiveness of these methods. (C) 2007 Elsevier B.V. All rights reserved.
We present an overview of the integration of constraint programming (CP) and operations research (OR) to solve combinatorial optimization problems. We interpret CP and OR as relying on a common primal-dual solution ap...
详细信息
We present an overview of the integration of constraint programming (CP) and operations research (OR) to solve combinatorial optimization problems. We interpret CP and OR as relying on a common primal-dual solution approach that provides the basis for integration using four main strategies. The first strategy tightly interweaves propagation from CP and relaxation from OR in a single solver. The second applies OR techniques to domain filtering in CP. The third decomposes the problem into a portion solved by CP and a portion solved by OR, using CP-based column generation or logic-based Benders decomposition. The fourth uses relaxed decision diagrams developed for CP propagation to help solve dynamic programming models in OR. The paper cites a significant fraction of the literature on CP/OR integration and concludes with future perspectives.
Embedded systems are built for specific purposes and are optimized to meet different kind of constraints, such as performance, timing, power and cost. The design process therefore involves different optimization activ...
详细信息
Embedded systems are built for specific purposes and are optimized to meet different kind of constraints, such as performance, timing, power and cost. The design process therefore involves different optimization activities. In this paper, we discuss the use of constraint programming (CP) technology for these optimization problems. The main advantages and disadvantages of applying CP to embedded system design problems are discussed on two examples, scheduling and mapping. Based on these examples modelling capabilities of CP and basic solving methods are discussed. We have identified CP modelling capability as an important factor for problem formalization and their uniform representation. We have also, using several experiments, show efficiency of the models and solving process. Finally, we have also pointed out difficulties with CP technology that are mostly related to search methods that, for more realistic problems, must be carefully selected or even new methods must be developed. (C) 2019 Elsevier B.V. All rights reserved.
We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search meth...
详细信息
We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, whose potential pruning capabilities open the door to more elaborate local moves, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the traveling salesman problem with time windows. These results indicate that it is one order of magnitude faster than the customary constraint programming approach to local search and that it is competitive with a specialized local search algorithm.
The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so-called discretization assumptions allow us to disc...
详细信息
The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so-called discretization assumptions allow us to discretize the search space of DGP instances. In this paper, we focus on a key subclass of DGP, namely the Discretizable Molecular DGP, and study its associated graph vertex ordering problem, the Contiguous Trilateration Ordering Problem (CTOP), which helps solve DGP. We propose the first constraint programming formulations for CTOP, as well as a set of checks for proving infeasibility, domain reduction techniques, symmetry breaking constraints, and valid inequalities. Our computational results on random and pseudo-protein instances indicate that our formulations outperform the state-of-the-art integer programming formulations.
暂无评论