Instruction following evaluates large language models (LLMs) on their abilityto generate outputs that adhere to user-defined constraints. However, existingbenchmarks often rely on templated constraint prompts, which l...
详细信息
In the automotive industry, a manufacturer must perform several hundreds of tests on prototypes of a vehicle before starting its mass production. Tests must be allocated to suitable prototypes and ordered to satisfy t...
详细信息
In the automotive industry, a manufacturer must perform several hundreds of tests on prototypes of a vehicle before starting its mass production. Tests must be allocated to suitable prototypes and ordered to satisfy temporal constraints and various kinds of test dependencies. The manufacturer aims to minimize the number of prototypes required. We present improvements of constraint programming (CP) and hybrid approaches to effectively solve random instances from an existing benchmark. CP mostly achieves better solutions than the previous heuristic technique and genetic algorithm. We also provide customized search schemes to enhance the performance of general search algorithms. The hybrid approach applies mixed integer linear programming (MILP) to solve the planning part and CP to find the complete schedule. We consider several logical principles such that the MILP model can accurately estimate the prototype demand, while its size particularly for large instances does not exceed memory capacity. Moreover, the robustness is alleviated when we allow CP to partially change the allocation obtained from the MILP model. The hybrid method can contribute to optimal solutions in some instances.
constraint satisfaction problems (CSPs) are widely used in domains such as product configuration, scheduling, and resource allocation. However, formulating constraint models remains a significant challenge that often ...
详细信息
constraint satisfaction problems (CSPs) are widely used in domains such as product configuration, scheduling, and resource allocation. However, formulating constraint models remains a significant challenge that often requires specialized expertise in constraint programming (CP). This study introduces the Automatic constraint Model Generator (ACMG), a novel framework that leverages fine-tuned large language models (LLMs) to automate the translation of natural language problem descriptions into formal CSP models. The ACMG employs a multi-step process involving semantic entity extraction, constraint model generation, and iterative validation using the MiniZinc solver. Our approach achieves state-of-the-art (SOTA) or near-SOTA results, demonstrating the viability of LLMs in simplifying the adoption of CP. Its key contributions include a high-quality dataset for fine-tuning, a modular architecture with specialized LLM components, and empirical validation which shows its promising results for complex configuration tasks. By bridging the gap between natural language and formal constraint models, the ACMG significantly lowers the barrier to CP, making it more accessible to non-experts while maintaining a high level of robustness for industrial applications.
In this paper we present work towards automating two process steps supporting the optimization of the runnable-to-task mapping in automotive multi-core control units. We describe these steps in close relation to the A...
详细信息
ISBN:
(纸本)9781728151250
In this paper we present work towards automating two process steps supporting the optimization of the runnable-to-task mapping in automotive multi-core control units. We describe these steps in close relation to the AUTOSAR methodology to facilitate the integration with existing design processes. The first step is the automated generation of an initial configuration that balances the core utilization using constraint programming. The second step is the optimization of an existing configuration based on dynamic system behavior using an evolutionary algorithm. An abstract intermediate representation provides interoperability with existing AUTOSAR tools. We use a small case study to evaluate the feasibility of our approach.
作者：
Hà, Minh HoàngTa, Dinh QuyNguyen, Trung ThanhORLab
Faculty of Computer Science Phenikaa University Hanoi12116 Viet Nam ORLab
Faculty of Information Technology VNU University of Engineering and Technology Hanoi Viet Nam
Machine scheduling problems involving conflict jobs can be seen as a constrained version of the classical scheduling problem, in which some jobs are conflict in the sense that they cannot be proceeded simultaneously o...
详细信息
In a previous work we introduced a global StockingCost constraint to compute the total number of periods between the production periods and the due dates in a multi-order capacitated lot-sizing problem. Here we consid...
详细信息
In a previous work we introduced a global StockingCost constraint to compute the total number of periods between the production periods and the due dates in a multi-order capacitated lot-sizing problem. Here we consider a more general case in which each order can have a different per period stocking cost and the goal is to minimise the total stocking cost. In addition the production capacity, limiting the number of orders produced in a given period, is allowed to vary over time. We propose an efficient filtering algorithm in O(n log n) where n is the number of orders to produce. On a variant of the capacitated lot-sizing problem, we demonstrate experimentally that our new filtering algorithm scales well and is competitive wrt the StockingCost constraint when the stocking cost is the same for all orders.
This paper considers the flow shop scheduling problem with minimum and maximum time-lag requirements. According to the time-lag constraints, the starting time of each operation of a job must be within a specified time...
详细信息
This paper considers the flow shop scheduling problem with minimum and maximum time-lag requirements. According to the time-lag constraints, the starting time of each operation of a job must be within a specified time-window after the completion of its previous operation. The considered objective function is makespan and the problem is strongly NP-hard. In this article, a mixed integer linear programming (MILP) and two constraint programming (CP) models are proposed for the problem. To deal with the larger instances of this problems, it is decomposed into a sequencing and a timetabling sub-problem. A tabu search (TS) is developed to handle the sequencing sub-problem. Furthermore, an exact method based on the developed MILP as well as a greedy algorithm are proposed to deal with the timetabling sub-problem. A large number of test cases with different time-lag settings are solved to assess the performance of the proposed algorithm. Computational results confirm that the proposed TS is efficient and competitive. Moreover, the greedy timetabling method proves to be significantly faster than the exact method without sacrificing the solution quality.
This study investigates the integration of finite capacity scheduling with POLCA-based workload control in high-mix, low-volume production environments. We propose a proactive scheduling approach that embeds POLCA con...
详细信息
This study investigates the integration of finite capacity scheduling with POLCA-based workload control in high-mix, low-volume production environments. We propose a proactive scheduling approach that embeds POLCA constraints into a constraint programming (CP) model, aiming to reconcile the trade-offs between utilization efficiency and system responsiveness. The proposed methodology is evaluated in two phases. First, a simplified job shop simulation compares a traditional reactive POLCA implementation with the CP-based proactive approach under varying system configurations, demonstrating significant reductions in lead times, tardiness, and deadlock occurrences. Second, an industrial case study in an aerospace manufacturing firm validates the practical applicability of the approach by retrospectively comparing the CP model against an existing commercial scheduler. The results underscore that the integrated framework not only enhances scheduling performance through improved workload control but also provides a more stable operational environment.
This research details the creation of a large-scale optimization approach for solving an application of a multi-period bilevel network interdiction problem (NIP). In this class of multi-period NIP, interdiction activi...
详细信息
This research details the creation of a large-scale optimization approach for solving an application of a multi-period bilevel network interdiction problem (NIP). In this class of multi-period NIP, interdiction activities must be scheduled to minimize the cumulative maximum flow over a finite time horizon. A logic-based decomposition (LBD) approach is proposed that utilizes constraint programming to exploit the scheduling nature of this multi-period NIP. Computational results-comparing solutions obtained using the proposed approach versus traditional mixed-integer programming approach-suggest that the LBD approach is more efficient in finding solutions for medium to large problem instances. (C) 2018 Elsevier Ltd. All rights reserved.
Fast-tracking is an important process to speed the delivery of construction projects. To support optimum fast-tracking decisions, this paper introduces a generic schedule optimization framework that integrates four sc...
详细信息
Fast-tracking is an important process to speed the delivery of construction projects. To support optimum fast-tracking decisions, this paper introduces a generic schedule optimization framework that integrates four schedule acceleration dimensions: linear activity crashing;discrete activity modes of execution;alternative network paths;and flexible activity overlapping. Because excessive schedule compression can lead to space congestion and overstressed workers, the optimization formulation uses specific variables and constraints to prevent simultaneous use of overlapping and crashing at the same activity segment. To handle complex projects with a variety of milestones, resource limits, and constraints, the framework has been implemented using the constraint programming (CP) technique. Comparison with a literature case study and further experimentation demonstrated the flexibility and superior performance of the proposed model. The novelty of the model stems from its integrated multi-dimensional formulation, its CP engine, and its ability to provide alternative fast-track schedules to strictly constrained projects without overstressing the construction workers.
暂无评论