The discrete time-cost tradeoff problem (DTCTP) is a well-researched topic in the field of operations research. The majority of existing DTCTP models are based on traditional activity networks, which permit the execut...
详细信息
The discrete time-cost tradeoff problem (DTCTP) is a well-researched topic in the field of operations research. The majority of existing DTCTP models are based on traditional activity networks, which permit the execution of an activity as soon as all its predecessors have been completed. This assumption is reasonable, but it is important to note that there are always exceptions. The main work of this study was threefold. Firstly, we expanded the analysis of the DTCTP to encompass time-constrained activity networks (DTCTPTC), which encompassed three different types of time constraints. The first constraint was the time-window constraint, which limited the time interval during which an activity could be executed. The second constraint was the time-schedule constraint, which specified the times at which an activity could begin execution. The third constraint was the time-switch constraint, which required project activities to start at specific times and remain inactive during designated time periods. Secondly, a constraint programming (CP) model was developed for the purpose of solving the DTCTPTC. The model employed interval variables to define the activity and its potential time constraints, while CP expressions were utilized to ensure the feasibility of the solution. The objective was to identify the optimal execution mode for each activity, the optimal start times for time-scheduled activities, and the optimal work/rest patterns for time-switch activities, with the aim of minimizing the total cost of the project. Finally, the efficacy of the proposed CP model was validated through two case studies based on two illustrative projects of varying sizes. The outcomes were then compared against existing algorithms. The results demonstrated that time constraints were important factors affecting schedule optimization, and the proposed CP model had the ability to solve large-scale DTCTPTC.
In sustainable agriculture, intercropping systems represent a valuable approach. These systems involve placing mutually beneficial plant types in close proximity to each other, with the goal of exploiting biodiversity...
详细信息
In sustainable agriculture, intercropping systems represent a valuable approach. These systems involve placing mutually beneficial plant types in close proximity to each other, with the goal of exploiting biodiversity to reduce pesticide and water usage, as well as improve soil nutrient utilization. Despite its potential, the optimization of intercropping systems has received limited attention in previous studies. One of the first steps in the design of an intercropping system is the solution of the crop planting layout problem, which involves meeting crop demand while maximizing positive interactions between adjacent plants. We perform a complexity analysis of this problem and solve it through constraint programming, an artificial intelligence technique, which relies on automated reasoning, constraint propagation and search heuristics. To this aim, we present two constraint programming models based on integer variables and interval variables, respectively. Through a computational study on real -life instances, we examine the impact of different modelling approaches on the difficulty of solving the crop planting layout problem with standard constraint programming solvers. This research work has also provided the groundwork for a sowing robotic arm (under development), aiming to automate intercropping systems and assist farm workers.
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.
Scheduling tasks on reconfigurable hardware is a well-known problem. Yet, the adoption of advanced scheduling strategies for reconfigurable systems is still low. We argue that a pragmatic solution not relying on low-l...
详细信息
ISBN:
(纸本)9781665497473
Scheduling tasks on reconfigurable hardware is a well-known problem. Yet, the adoption of advanced scheduling strategies for reconfigurable systems is still low. We argue that a pragmatic solution not relying on low-level features like partial reconfiguration is feasible. Our theoretical framework describes reconfigurable hardware in a simple and abstract way. The constraints of a schedule are used to derive a constraint programming formulation. We present two heuristic algorithms based on list scheduling and on clustering, respectively. The model is evaluated and compared to partial reconfiguration using parameters from a previously observed LU decomposition on an FPGA. The losses are compared to a conventional, optimal approach. It can be integrated into existing technologies to aide the adoption of high-level FPGA programming environments.
Simulation-optimization is often used in enterprise decision-making processes, both operational and tactical. This paper shows how an intuitive mapping from descriptive problem to optimization model can be realized wi...
详细信息
ISBN:
(纸本)9783031115202;9783031115196
Simulation-optimization is often used in enterprise decision-making processes, both operational and tactical. This paper shows how an intuitive mapping from descriptive problem to optimization model can be realized with constraint programming (CP). It shows how a CP model can be constructed given a simulation model and a set of business goals. The approach is to train a neural network (NN) on simulation model inputs and outputs, and embed the NN into the CP model together with a set of soft constraints that represent business goals. We study this novel simulation-optimization approach through a set of experiments, finding that it is flexible to changing multiple objectives simultaneously, allows an intuitive mapping from business goals expressed in natural language to a formal model suitable for state-of-the-art optimization solvers, and is realizable for diverse managerial problems.
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programmin...
详细信息
Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings, for an exhaustive search and for a type of local search called Large Neighborhood Search. We show its use in the analysis of real datasets. Finally, we show an application of the CP framework for model selection using the Minimum Description Length principle.
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.
暂无评论