We use integer programming (IP) and constraint programming (CP) to search for sets of mutually orthogonal latin squares (MOLS). We improve the performance of the solvers by formulating an extended symmetry breaking me...
详细信息
ISBN:
(纸本)9781577358763
We use integer programming (IP) and constraint programming (CP) to search for sets of mutually orthogonal latin squares (MOLS). We improve the performance of the solvers by formulating an extended symmetry breaking method and provide an alternative CP encoding which performs much better in practice. Using state-of-the-art solvers we are able to quickly find pairs of MOLS (or prove their nonexistence) in all orders up to and including eleven. We also analyze the effectiveness of using CP and IP solvers to search for triples of MOLS and estimate the running time of using this approach to resolve the longstanding open problem of determining the existence of a triple of MOLS of order ten.
We investigate the novel Two-stage Cutting Stock Problem with Flexible Length and Flexible Demand (2SCSP-FF): orders for rectangular items must be cut from rectangular stocks using guillotine cuts with the objective t...
详细信息
ISBN:
(数字)9783031080111
ISBN:
(纸本)9783031080111;9783031080104
We investigate the novel Two-stage Cutting Stock Problem with Flexible Length and Flexible Demand (2SCSP-FF): orders for rectangular items must be cut from rectangular stocks using guillotine cuts with the objective to minimize waste. Motivated by our industrial partner and different from problems in the literature, the 2SCSP-FF allows both the length of individual items and the total area of orders to vary within customer-specified intervals. We develop constraint programming (CP) and mixed-integer programming models, with the most successful coming from the adaptation of CP scheduling techniques. Numerical results show that this CP model has orders of magnitude smaller memory requirements and is the only model-based approach investigated that can solve industrial instances.
Scheduling of megaprojects is very challenging because of typical characteristics, such as expected long project durations, many activities with multiple modes, scarce resources, and investment decisions. Furthermore,...
详细信息
Scheduling of megaprojects is very challenging because of typical characteristics, such as expected long project durations, many activities with multiple modes, scarce resources, and investment decisions. Furthermore, each megaproject has additional specific characteristics to be considered. Since the number of nuclear dismantling projects is expected to increase considerably worldwide in the coming decades, we use this type of megaproject as an application case in this paper. Therefore, we consider the specific characteristics of constrained renewable and non-renewable resources, multiple modes, precedence relations with and without no-wait condition, and a cost minimisation objective. To reliably plan at minimum costs considering all relevant characteristics, scheduling methods can be applied. But the extensive literature review conducted did not reveal a scheduling method considering the special characteristics of nuclear dismantling projects. Consequently, we introduce a novel scheduling problem referred to as the nuclear dismantling project scheduling problem. Furthermore, we developed and implemented an effective metaheuristic to obtain feasible schedules for projects with about 300 activities. We tested our approach with real-life data of three different nuclear dismantling projects in Germany. On average, it took less than a second to find an initial feasible solution for our samples. This solution could be further improved using metaheuristic procedures and exact optimisation techniques such as mixed-integer programming and constraint programming. The computational study shows that utilising exact optimisation techniques is beneficial compared to standard metaheuristics. The main result is the development of an initial solution finding procedure and an adaptive large neighbourhood search with iterative destroy and recreate operations that is competitive with state-of-the-art methods of related problems. The described problem and findings can be transferred
Although operations in container terminals are highly interdependent, they are traditionally optimized by decomposing the overall problem into a sequence of smaller sub-problems, each focusing on a single operation. R...
详细信息
Although operations in container terminals are highly interdependent, they are traditionally optimized by decomposing the overall problem into a sequence of smaller sub-problems, each focusing on a single operation. Recent studies, however, have demonstrated the need and potential of optimizing these interdependent operations jointly. This paper proposes the Integrated Port Container Terminal Problem (IPCTP) that considers the joint optimization of quay crane assignment and scheduling, yard crane assignment and scheduling, yard location assignments, and yard truck assignment and scheduling. The IPCTP aims at minimizing the turnover times of the vessels and maximize terminal throughput. It also considers inbound and outbound containers simultaneously and models the safety distance and the interference constraints for the quay cranes. To solve the IPCTP, the paper proposes several constraint programming (CP) models. Computational results show that CP provides exact solutions in acceptable time to IPCTP instances derived from an actual (small) container terminal in Turkey. For hard IPCTP instances, the CP model can be generalized in a two-stage optimization approach to produce high-quality solutions in reasonable times. (C) 2020 Elsevier B.V. All rights reserved.
In the literature, most of the researchers studying assembly line balancing have only considered task assignments. However, resources are needed to perform the tasks. Therefore, assigning resources related to tasks be...
详细信息
In the literature, most of the researchers studying assembly line balancing have only considered task assignments. However, resources are needed to perform the tasks. Therefore, assigning resources related to tasks becomes more realistic when assigning tasks to stations. In the general case of the problem, the task is performed with a specified amount of resources. If resource types such as a, b, c are required to perform tasks in an assembly line, the combination of tasks required from these resources should also be assigned to the stations. This type of problem is defined as general resources-constrained assembly line balancing problem (GRCALBP). In this study, GRCALBP is addressed to minimize cycle time and resource usage for a given number of stations. New constraint programming (CP) models based on conjunction normal form are proposed. The CP models are tested with generated problem instances from the data set in the literature. The experimental results show that CP is an efficient and effective modeling technique to solve GRCALBP. Finally, suggestions are made regarding alternative objective functions.
This paper focuses on the cost minimization of the multi-mode resource-constrained repetitive project scheduling problem with multiple crews, crew interruptions, and soft logic. The resource allocation of each crew is...
详细信息
This paper focuses on the cost minimization of the multi-mode resource-constrained repetitive project scheduling problem with multiple crews, crew interruptions, and soft logic. The resource allocation of each crew is considered. To explore the impact of different construction strategies on project costs, mixed-integer linear programming (MILP) and constraint programming (CP) models are developed representing different construction scenarios. A relax-and-solve (R&S) algorithm, incorporating a rolling horizon and constraint programming, is proposed to obtain near-optimal solutions within reasonable time limits. The case study reveals that considering crew resource allocation and adopting more flexible construction strategies can contribute to reducing total project costs. The findings provide construction managers with practical strategies to improve scheduling, resource management, and cost control. Meanwhile, the proposed algorithm performs competitively compared with MILP and CP models, which inspires future research to apply this algorithm to other repetitive project scheduling problems.
In this manuscript we present an original implementation of network management functions in the context of Software Defined Networking. We demonstrate a full integration of an artificial intelligence driven management...
详细信息
In this manuscript we present an original implementation of network management functions in the context of Software Defined Networking. We demonstrate a full integration of an artificial intelligence driven management, an SDN control plane, and a programmable data plane. constraint programming is used to implement a management operating system that accepts high level specifications, via a northbound interface, in terms of operational objective and directives. These are translated in technology-specific constraints and directives for the SDN control plane, leveraging the programmable data plane, which is enriched with functionalities suited to feed data that enable the most effective operation of the "intelligent" control plane, by exploiting the P4 language.
In serial batch (s-batch) scheduling, jobs are grouped in batches and processed sequentially within their batch. This paper considers multiple parallel machines, nonidentical job weights and release times, and sequenc...
详细信息
constraint programming (CP) is used widely for solving real-world problems. However, designing these models require substantial expertise. In this paper, we tackle this problem by synthesizing models automatically fro...
详细信息
In this work, a constraint programming (CP) formulation of the multi-mode resource-constrained project scheduling problem (MMRCPSP) is proposed for solving the flexible job shop scheduling problem (FJSSP) under the ma...
详细信息
In this work, a constraint programming (CP) formulation of the multi-mode resource-constrained project scheduling problem (MMRCPSP) is proposed for solving the flexible job shop scheduling problem (FJSSP) under the makespan minimization criterion. The resulting CP model allows us to tackle the classical instances of the FJSSP (such as where the operations of a given job follow a linear order). It can also handle FJSSP instances where the precedence relationships between operations are defined by an arbitrary directed acyclic graph (sequencing flexibility). The performance of our approach was tested using 271 classical FJSSP instances and 50 FJSSP instances with sequencing flexibility. We establish the validity of our approach by achieving an average relative percentage deviation of 3.04% and 0.18% when compared to the best-known lower and upper bounds, respectively. Additionally, we were able to contribute to the literature with ten new lower bounds and two new upper bounds. Our CP approach is relatively simple yet competitive and can be quickly applied and adapted by new practitioners in the area.
暂无评论