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.
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.
Extracting diverse and frequent closed itemsets from large datasets is a core challenge in pattern mining, with significant implications across domains such as fraud detection, recommendation systems, and machine lear...
详细信息
Extracting diverse and frequent closed itemsets from large datasets is a core challenge in pattern mining, with significant implications across domains such as fraud detection, recommendation systems, and machine learning. Existing approaches often lack flexibility and efficiency, and struggle with initial itemset selection bias and redundancy. This paper addresses these research gaps by introducing a compact and modular constraint programming model that formalizes the search for diverse patterns. Our approach incorporates a novel global constraint derived from a relaxed Overlap diversity measure, using tighter lower and upper bounds to improve filtering capabilities. Unlike traditional methods, we leverage an entropy-based optimization framework that combines joint entropy maximization with top-k pattern mining to identify the maximally k-diverse pattern set. Our approach ensures more comprehensive and informative pattern discovery by minimizing redundancy and promoting pattern diversity. Extensive experiments validate the effectiveness of the proposed method, demonstrating significant performance gains and superior pattern quality compared to state-of-the-art approaches. Implemented in both sequential and parallel versions, the framework offers an efficient and adaptable solution for anytime pattern mining tasks in various domains.
This paper studies the integrated process planning and scheduling with lot streaming (IPPS-LS) problem, which consists of lot splitting, process planning, and shop scheduling. Although the IPPS-LS problem is common in...
详细信息
This paper studies the integrated process planning and scheduling with lot streaming (IPPS-LS) problem, which consists of lot splitting, process planning, and shop scheduling. Although the IPPS-LS problem is common in the manufacturing of flexible process products, it has not been extensively studied due to its high complexity. Hence, this study develops an enhanced particle swarm optimization algorithm based on constraint programming (CP) to minimize makespan. The proposed algorithm employs finite condition and relaxation models for particle reconfiguration and re-optimization. To achieve it, two types of relaxation models are constructed by decomposing the multiple constraints of the CP model. The algorithm dynamically updates particle encoding sequences based on model accuracy, effectively reducing invalid searches and accelerating the search process. The proposed algorithm is compared with models and other metaheuristic algorithms on 120 test instances. The impact of the relaxed CP strategy and particle swarm optimization algorithm on the proposed algorithm performance is also analyzed. Finally, a significance of difference validation is performed. Computational experiments demonstrate the efficiency of the proposed algorithm in solving the IPPS-LS problem of varying scales. In addition, the relaxed CP strategy exhibits a more significant improvement effect for medium-scale problems compared to small and large-scale problems.
Production and distribution are both crucial components of supply chains. Integrated production and distribution scheduling (IPDS) in the context of flexible assembly flow shop scheduling and batch delivery problems i...
详细信息
Production and distribution are both crucial components of supply chains. Integrated production and distribution scheduling (IPDS) in the context of flexible assembly flow shop scheduling and batch delivery problems is often overlooked. A realistic problem inspired by the production and distribution processes of a dishwasher factory can be modeled as a resource-constrained flexible assembly flow shop scheduling problem with batch direct delivery (RCFAFSP-BDD). In this problem, order requirements are decomposed into several production tasks processed at different stages of the workshop, and are then delivered in batches via a third-party logistics provider to regional distributors at various locations. Auxiliary resource restrictions, hierarchical coupling constraints, machine eligibility restrictions and sequence-dependent setup times, are incorporated into the problem as operational constraints. To the best of our knowledge, this is the first attempt to solve this problem. This work formulates a mixed-integer linear programming (MIP) model to minimize total costs, including tardiness, inventory, and delivery costs. Given the problem's strong NP-hard nature, the focus is on developing an efficient solution approach using constraint programming (CP). A CP model is proposed and enhanced with multiple redundant constraints. To reduce runtime, two branching strategies are designed for the CP model. Numerical experiments with varying instance scales reveal that the proposed CP model outperforms the MIP model in accuracy and efficiency within the given time limit. The redundant constraints and search strategy can reduce CP model runtime by up to 263.83%. Compared to manual scheduling at the studied factory, the CP model can cut costs by up to 26.59% for real data, offering viable alternatives for factory planners.
In comparison with traditional subtractive manufacturing techniques, additive manufacturing (AM) enables fabricating complex parts through a layer-by-layer process. AM makes it possible to produce one-piece and lightw...
详细信息
In comparison with traditional subtractive manufacturing techniques, additive manufacturing (AM) enables fabricating complex parts through a layer-by-layer process. AM makes it possible to produce one-piece and lightweight functional products, which are traditionally made from several parts. This paper introduces constraint programming (CP) models to minimise makespan in single, parallel identical and parallel unrelated AM machine scheduling environments for selective laser melting. Alternative CP formulations are explored to improve efficiency. The proposed CP model significantly benefits from the introduction of interval variables to replace binary assignment variables, and pre-definitions to narrow the search space, resulting in increased search performance. A computational study has been conducted to compare the performance of our proposed CP model with both a mixed-integer programming and a genetic algorithm from existing literature, evaluating improvements made to its search capability. Computational results indicate that the proposed CP model can obtain high-quality solutions in a timely manner even for several large-size instances.
Collaborative robots are increasingly utilized to assist the human workers to assemble tasks or complete the assembly tasks solely in assembly lines. This study considers the human-robot collaborative assembly lines w...
详细信息
Collaborative robots are increasingly utilized to assist the human workers to assemble tasks or complete the assembly tasks solely in assembly lines. This study considers the human-robot collaborative assembly lines with heterogeneous collaborative robots and limited resources to optimize cycle time where human workers and collaborative robots can operate the different tasks in parallel. A constraint programming model is formulated that was able to achieve the optimal solutions for small-sized instances. An improved fruit fly optimization algorithm is developed to tackle the large-sized instances. The proposed algorithm proposes two vectors for encoding, where task assignment vector tackles task allocation sub-problem and process alternative vector tackles process alternative allocation sub-problem. This algorithm utilizes a decoding procedure with a constraint programming approach to achieve an optimal scheduling scheme of the station with human worker and collaborative robot. The lower bound and upper bound of completion time of single station and the earliest and latest processing time of tasks are added to the constraint programming model to speed up the search process. Meanwhile, improved fruit fly optimization algorithm utilizes the improved olfactory phase, improved visual phase and restart phase to accelerate the evolution of the whole swarm and avoid being trapped in local optimum. Computational study demonstrates that constraint programming approach outperforms the current mixed integer programming approach in objective value and solution time. The decoding procedure with constraint programming outperforms the current decoding procedure with mixed integer programming. Comparative study demonstrates that the proposed method outperforms the original fruit fly optimization algorithm and achieves promising performance in comparison with other methods. Finally, the proposed method is applied on scheduling of a gear box assembly line.
The Multi-Mode Resource-Constrained Multiple Projects Scheduling Problem (MMRCMPSP) is an important combinatorial optimization problem for both real-world situations in industry and academic research. Its objective is...
详细信息
The Multi-Mode Resource-Constrained Multiple Projects Scheduling Problem (MMRCMPSP) is an important combinatorial optimization problem for both real-world situations in industry and academic research. Its objective is to find the best schedule for activities across multiple projects that can be executed in different modes. The schedule must consider shared resource availability and satisfy precedence and time constraints. To tackle this problem, we propose a hybrid approach that combines constraint programming (CP) with meta-heuristic algorithms. We introduce and assess a CP model that incorporates all MMRCMPSP constraints. By leveraging the strengths of CP and meta-heuristics, our approach yields new upper bounds for various MMRCMPSP benchmark instances. Additionally, we evaluate our method using existing benchmark instances for single-project scheduling problems with multiple modes and provide improved solutions for many of them.
This paper proposes an exact constraint programming (CP) method with an extensive focus on real-world constraints for the Multi-manned Assembly Line Balancing Problem with Assignment Restrictions (MALBPAR). We perform...
详细信息
This paper proposes an exact constraint programming (CP) method with an extensive focus on real-world constraints for the Multi-manned Assembly Line Balancing Problem with Assignment Restrictions (MALBPAR). We perform an in-depth literature review to gather examples from real assembly lines and organize the AR regarding tasks, stations, workers, and mounting positions. Our study classifies the AR related to transformed resources and provides a general and unified model. We explore the concept of variable workplaces to dynamically assign workers to mounting positions and aggregate no overlap restrictions to avoid interference between workers. The classic MALBP model is extended by gradually incrementing the number of restrictions. The model variant found in the literature is herein called Partial MALBP-AR. Compared to the previous state-of-the-art Tabu Search Algorithm (TSA) for this problem, the Partial MALBP-AR found twelve additional optimality proofs. Besides the relevant results regarding solution quality, the CP method also has a satisfactory CPU performance. We also propose an entirely new set of AR and test these practical conditions with the so-called Extended MALBP-AR. Such an extended model, which covers all the AR presented here, reached optimality within the computational time limit for 36 out of 38 instances. The worst-case gap for an open instance is 8.20%. The results show a trade-off between the number of deemed restrictions and the computational performance. However, considering the detailed set of AR, we can obtain more representative solutions regarding the final balancing implementation compared to theoretical cases. The method can be used to design experiments, turning certain constraints on and off and allowing managers to evaluate different resource allocation scenarios.
暂无评论