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.
Current extensive flexible manufacturing systems are characterized by high flexibility and large problem sizes, which present significant challenges to manufacturing efficiency. The integrated process planning and sch...
详细信息
Current extensive flexible manufacturing systems are characterized by high flexibility and large problem sizes, which present significant challenges to manufacturing efficiency. The integrated process planning and scheduling (IPPS) is a significant issue in this context. Due to the complexity of the integration problem, various approximation algorithms have been developed to tackle it, though this often demands considerable designer expertise and parameter tuning. This paper proposes a constraint programming (CP)-based method that can solve the large-scale IPPS problem in extensive flexible manufacturing. Firstly, this paper proposes a CP model which enriches the variable decision-making for flexible processes. Based on this, this paper presents a hybrid layered constraint programming (HLCP) method, which decomposes the complete CP model into multiple models of subproblems and solves these models iteratively to reduce the solution difficulty. It contains multiple sets of model relaxation and repair stages. Experiments on benchmark instances confirm that the proposed method reaches all optimal solutions, and surpasses previous results on 9 instances. Next, the proposed methods are tested on 35 sets of large-scale instances with up to 8000 operations, and the results show that the minimum gap can be obtained compared to the existing methods. Moreover, the proposed HLCP method is able to reduce the gap by an average of 9.03% within a reasonable time compared to the single-model approach.
This article presents a constraint modeling approach to global coverage-path planning for linear-infrastructure inspection using multiple autonomous UAVs. The problem is mathematically formulated as a variant of the M...
详细信息
This article presents a constraint modeling approach to global coverage-path planning for linear-infrastructure inspection using multiple autonomous UAVs. The problem is mathematically formulated as a variant of the Min-Max K-Chinese Postman Problem (MM K-CPP) with multi-weight edges. A high-level constraint programming language is used to model the problem, which enables model execution with different third-party solvers. The optimal solutions are obtained in a reasonable time for most of the tested instances and different numbers of vehicles involved in the inspection. For some graphs with multi-weight edges, a time limit is applied, as the problem is NP-hard and the computation time increases exponentially. Despite that, the final total inspection cost proved to be lower when compared with the solution obtained for the unrestricted MM K-CPP with single-weight edges. This model can be applied to plan coverage paths for linear-infrastructure inspection, resulting in a minimal total inspection time for relatively simple graphs that resemble real transmission networks. For more extensive graphs, it is possible to obtain valid solutions in a reasonable time, but optimality cannot be guaranteed. For future improvements, further optimization could be considered, or different models could be developed, possibly involving artificial neural networks.
Due to the increased demand for efficient recycling systems for end-of-life (EOL) products, the role of disassembly lines in reverse supply chains has become crucial. Parallel disassembly lines can handle multi-type E...
详细信息
Due to the increased demand for efficient recycling systems for end-of-life (EOL) products, the role of disassembly lines in reverse supply chains has become crucial. Parallel disassembly lines can handle multi-type EOL products and consist of two or more lines. However, previous research has primarily focused on two-line disassembly systems and has not fully addressed the optionality of common stations. To address this gap, this study proposes three exact methods for optimizing multi-line parallel disassembly systems with optional common stations, partial disassembly mode, and AND/OR precedence relations. Firstly, a mixed-integer linear programming (MILP) model is formulated that optimizes three objectives: weighted line length, additional profits, and hazard evaluation. Secondly, two constraint programming (CP) models are developed with different solution methodologies to provide more extensive applications and efficient solutions. An illustrative example shows that production mode can significantly reduce line length and workstations, and computational results demonstrate that both CP methods outperform the MILP model in terms of solution quality and computational efficiency. Specifically, the CP-I method demonstrates a higher level of stability and efficiency in most instances, while the CP-II method excels in optimizing line length and station utilization. These results illustrate the potential for optimizing multi-line disassembly systems with optional common stations to enhance production flexibility in remanufacturing processes.& COPY;2023 Elsevier Inc. All rights reserved.
Proper scheduling of jobs is essential for modern production systems to work effectively. The hybrid flow shop scheduling problem is a scheduling problem with many applications in the industry. The problem has also at...
详细信息
Proper scheduling of jobs is essential for modern production systems to work effectively. The hybrid flow shop scheduling problem is a scheduling problem with many applications in the industry. The problem has also attracted much attention from researchers due to its complexity. This study addresses the hybrid flow shop scheduling problem (HFSP), which considers unrelated parallel machines at each stage and the machine eligibility constraints. HFSP is a well-known NP-hard problem with the aim of minimizing the makespan. Owing to the complexity of the problem, this study develops constraint programming (CP) models for the HFSP and its extensions: the no-wait HFSP, the blocking HFSP, the HFSP with sequence-dependent setup times, the no-wait HFSP with sequence-dependent setup times, and the blocking HFSP with sequence-dependent setup times. We also propose two mixed-integer linear programming models (MILP) for no-wait and blocking HSFPs with sequence-dependent setup times. The performances of the CP models were tested against their MILP counterparts using randomly generated instances and benchmark instances from the literature. The computational results indicated that the proposed CP model outperformed the best MILP solutions for benchmark instances. It is also more effective for finding high-quality solutions for larger problem instances.
The integrated process planning and scheduling (IPPS) problem is of critical importance in achieving de-sirable performance for complex manufacturing systems. The IPPS problem is often categorized into two types, i.e....
详细信息
The integrated process planning and scheduling (IPPS) problem is of critical importance in achieving de-sirable performance for complex manufacturing systems. The IPPS problem is often categorized into two types, i.e., Type-I and Type-II, depending on how the process plan is represented. In recent years, sev-eral approaches have been proposed to solve the IPPS problem in the literature. However, due to the complexity of the problem, optimal solutions of some benchmark datasets still cannot be obtained in a reasonable time, and few of them can be used to simultaneously address both types of IPPS problem. To this end, this study constructs a constraint programming (CP) model considering both types of IPPS prob-lem, and proposes two basic logic-based Benders decomposition (LBBD) algorithms: one for each type of IPPS problem. In order to ensure computational efficiency, an enhanced LBBD algorithm is designed for both types of IPPS problem with three effective enhancement strategies. The performance of proposed methods is rigorously evaluated and compared with the existing approaches in the literature based on thirteen datasets. The results show that our methods significantly outperform these approaches. & COPY;2022 Elsevier Ltd. All rights reserved.
Drones are currently seen as a viable way for improving the distribution of parcels in urban and rural environments, while working in coordination with traditional vehicles like trucks. In this paper we consider the p...
详细信息
Drones are currently seen as a viable way for improving the distribution of parcels in urban and rural environments, while working in coordination with traditional vehicles like trucks. In this paper we consider the parallel drone scheduling vehicle routing problem, where the service of a set of customers requiring a delivery is split between a fleet of trucks and a fleet of drones. We consider two variations of the problem. In the first one, the problem is more theoretical, and the target is the minimization of the time required to complete the service and have all the vehicles back to the depot. In the second variant, more realistic constraints involving operating costs, capacity limitation and workload balance, are considered, and the target is to minimize the total operational costs. We propose different constraint programming models to deal with the two problems. An experimental champaign on the instances previously adopted in the literature is presented to validate the new solving methods. The results show that, on top of being a viable way to solve problems to optimality, the models can also be used to derive effective heuristic solutions and high-quality lower bounds for the optimal cost, if the execution is interrupted before its natural end.(c) 2023 The Author(s). Published by Elsevier B.V. on behalf of Association of European Operational Research Societies (EURO). This is an open access article under the CC BY-NC-ND license (http:// creativecommons .org /licenses /by -nc -nd /4 .0/).
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.
This paper presents constraint programming-based solution approaches for the three-dimensional loading capacitated vehicle routing problem (3l-CVRP) that consists of vehicle routing and three-dimensional loading probl...
详细信息
This paper presents constraint programming-based solution approaches for the three-dimensional loading capacitated vehicle routing problem (3l-CVRP) that consists of vehicle routing and three-dimensional loading problems in distribution logistics. Despite the practical benefits in the logistics world, the 3l-CVRP has not been extensively studied in the literature for its high combinatorial complexity. Therefore, we developed integrated and decomposed constraint programming-based solution methods in this study. The decomposed models outperformed the mixed-integer programming model proposed earlier in the literature for small-size problems. Furthermore, we solved the well-known benchmark problems with a decomposed model using constraint programming for the vehicle routing part of the problem and an evolutionary algorithm for the loading part. The computational study results show that the best-known results are improved in 36 of 93 problems.
In fuzzy mathematical programming literature, most of the transformation approaches were mainly focused on integer linear programs (ILPs) with fuzzy parameters/variables. However, ILP-based solution approaches may be ...
详细信息
In fuzzy mathematical programming literature, most of the transformation approaches were mainly focused on integer linear programs (ILPs) with fuzzy parameters/variables. However, ILP-based solution approaches may be inadequate for solving large-scaled combinatorial fuzzy optimization problems, like project scheduling under mixed fuzzy-stochastic environments. Moreover, many real-life project scheduling applications may contain different types of uncertainties such as fuzziness, stochasticity, and dynamism simultaneously. Based on these motivations, this paper presents a novel constraint programming (CP)-based transformation approach for solving a multi-objective and multi-mode, fuzzy-stochastic resource investment project scheduling problem (FS-MRIPSP) which is a well-known NP-complete problem. In fact, the proposed approach mainly depends on a bound and decomposition principle which divides fuzzy components of the problem into the crisp middle, lower, and upper level problems. Thus, it reduces the problem dimension and does not need to use any standard fuzzy arithmetic and ranking operations directly. Furthermore, the stochastic nature of the problem is also taken into account by using a multi-scenario-based stochastic programming technique. Finally, a weighted additive fuzzy goal program is embedded into the proposed CP-based transformation approach to produce compromise fuzzy project schedules that trade-off between expected values of project makespan and total resource usage costs. To show the validity and practicality of the proposed approach, a real-life application is presented for the production-and-operations management module implementation process of an international Enterprise Resource Planning software company. The fuzzy-stochastic project schedules generated by the proposed CP-based approach are also compared to the results of a similar ILP-based method. Computational results have shown that the CP-based approach outperforms the ILP-based method in te
暂无评论