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.
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 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.
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
Taking up the ongoing shift towards green production, this article addresses energy-oriented flexible job shop scheduling. Existing approaches mainly focus on single objectives in terms of energy utilization such as m...
详细信息
Taking up the ongoing shift towards green production, this article addresses energy-oriented flexible job shop scheduling. Existing approaches mainly focus on single objectives in terms of energy utilization such as minimizing energy consumption. However, production control can affect multiple energy-related criteria. Therefore, we propose a flexible job shop scheduling model to minimize real-time pricing-related energy costs, peak demand and energy-related emissions. Motivated by the reported preeminence of constraint programming (CP) for a variety of scheduling problems, we extend a CP formulation for our study. To evaluate potential contradictory between energy objectives, we present nine objective functions by means of different lexicographic orders. In addition, we enhance the proposed scheduling model to account for sequence-dependent setup and due dates. To analyze and compare the effectiveness of the different model formulations, we present computational experiments for 20 small-, medium-and large-sized problem instances. Our study indicates that productivity can be maximized while, on average, energy costs are reduced by 5.3%, peak demand by 11.8%, emissions by 8.3% compared to traditional job scheduling. However, partly conflicting objectives require the decision maker to select the objective function most suitable to the individual needs. Including setup effort and due date compliance into energy-aware scheduling is possible and needed to make the concept of energy-aware scheduling applicable to industrial practice. We show that the additional aspects limit the potential improvement. Hence, it is crucial to understand such complex scheduling systems combining energy awareness, setup and due date compliance.
In this paper, we address a challenging problem faced by a Brazilian oil and gas company regarding the rescheduling of helicopter flights from an onshore airport to maritime units, crucial for transporting company emp...
详细信息
In this paper, we address a challenging problem faced by a Brazilian oil and gas company regarding the rescheduling of helicopter flights from an onshore airport to maritime units, crucial for transporting company employees. The problem arises due to unforeseen events like bad weather or mechanical failures, leading to delays or postponements in the original flight schedules, disrupting the operation of maritime units, and employee shift scheduling. To model and solve the problem, we propose a constraint programming (CP) model aimed at optimizing daily flight scheduling with minimal delay and helicopter usage, considering various constraints like rescheduling priorities and time windows. We also develop a hybrid iterated local search algorithm to handle larger instances of the problem for the case when a general-purpose CP solver may not be available. Our approaches, evaluated using real-world data, demonstrate their effectiveness in solving short-term flight rescheduling problems in the context of the oil and gas industry, in comparison to exact and heuristic approaches from the literature.
This paper studies the multi-resource-constrained unrelated parallel machine scheduling problem under various operational constraints with the objective of minimising maximum completion time among the scheduled jobs. ...
详细信息
This paper studies the multi-resource-constrained unrelated parallel machine scheduling problem under various operational constraints with the objective of minimising maximum completion time among the scheduled jobs. Sequence-dependent setup times, precedence relations, machine eligibility restrictions and release dates are incorporated into the problem as operational constraints to reflect real-world manufacturing environments. The considered problem is in NP-hard class of problems, which cannot be solved in deterministic polynomial time. Our aim in this study is to develop an exact solution approach based on constraint programming (CP), which shows good performance in solving scheduling problems. In this regard, we propose a CP model and enrich this model by adding lower bound restrictions and redundant constraints. Moreover, to achieve a reduction in computation time, we propose two branching strategies for the proposed CP model. The performance of the CP model is tested using randomly generated and benchmark instances from the literature. The computational results indicate that the proposed CP model outperforms the best solutions with an average gap of 15.52%.
For over five decades, researchers have presented various assembly line problems. Recently, assembly lines with multiple workers at each workstation have become very common in the literature. These lines are often fou...
详细信息
For over five decades, researchers have presented various assembly line problems. Recently, assembly lines with multiple workers at each workstation have become very common in the literature. These lines are often found in the manufacturing of large vehicles, where workers at a workstation may perform their assigned tasks at the same time. Most research on multi-manned assembly lines focuses on balancing tasks and workers among workstations and scheduling tasks for workers. This study, however, concentrates on assigning tasks to workers already assigned to a specific workstation, rather than balancing the entire line. The problem was identified through an industrial case study at a large vehicle manufacturing company. The study presents two methods, one using mixed integer linear programming and the other using constraint programming, to minimise the number of workers required on a multi-manned assembly line with sequence-dependent setup times. The results of the computational experiments indicate that the constraint programming method performs better than the mixed integer linear programming method on several modified benchmark instances from the literature. The constraint programming model is also tested on the real-world scenario of our industrial case study and leads to significant improvements in the productivity of the workstations.
暂无评论