This paper examines scheduling problem denoted as P |seq, ser|Cmax in Graham’s notation;in other words, scheduling of tasks on parallel identical machines (P) with sequence-dependent setups (seq) each performed by on...
详细信息
A container vessel carries containers of various characteristics, in terms of size, weight, and contents. The cargo load of a container vessel, being subjected to a set of operational conditions and restrictions regar...
详细信息
A container vessel carries containers of various characteristics, in terms of size, weight, and contents. The cargo load of a container vessel, being subjected to a set of operational conditions and restrictions regarding ship stability and safety, is a fundamental element in decision-making when a shipping line provides logistics services to clients. This study presents a constraint programming-based model for the capacity planning of a container vessel under various operational conditions. The proposed model generates base solutions and is complemented with a rich scenario-based analysis that utilizes real-life ship data of a container vessel operated by a liner shipping company with a significant market presence. Solutions obtained from the model provide insights on containership capacity planning with differing settings and search strategies. Recommendations to container carriers, regarding improved capacity planning, are the highlights of the study.
Scheduling repetitive construction projects (RCPs) is a challenging task due to the nature of the activities involved. It requires careful consideration of both flexibility and computational performance. This paper de...
详细信息
Scheduling repetitive construction projects (RCPs) is a challenging task due to the nature of the activities involved. It requires careful consideration of both flexibility and computational performance. This paper develops a versatile RCP scheduling framework applicable to multiple construction scenarios, providing greater flexibility than existing models. The framework incorporates various scheduling features for repetitive activities, such as soft logic, multiskilled crews, multimode execution, crew transfers, and continuous or noncontinuous execution. It also offers optional optimization objectives, such as minimizing the overall project duration, total cost, crew interruption time, and number of employed crews. Planners can combine the features of repetitive activities and choose one or more objectives to meet their needs and preferences. The proposed framework is based on constraint programming, which balances computational efficiency and solution quality while remaining user-friendly. The practicality and effectiveness of the framework are verified through three case studies involving five real-life projects. The results demonstrate that the proposed framework can produce RCP schedules with shorter duration, lower costs, or reduced resource utilization compared with those generated by existing models.
constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the so...
详细信息
constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning -based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance. Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively compared to four existing methods. Finally, we showcase the benefits of integrating machine learning -based variable ordering methods with conventional domain -based approaches through tie -breaking.
We propose a constraint programming (CP)-based branch -and -price -and -cut framework to exactly solve bipath multicommodity flow (MCF): an MCF problem with two paths for each demand. The goal is to route demands in a...
详细信息
We propose a constraint programming (CP)-based branch -and -price -and -cut framework to exactly solve bipath multicommodity flow (MCF): an MCF problem with two paths for each demand. The goal is to route demands in a capacitated network under the minimum cost. The two paths must have disjoint arcs, and the delays accumulated along the two paths must be within a small deviation of each other. CP is used at multiple points in this framework: for solving pricing problems, for cut generation, and for primal and branching node heuristics. These modules use a CP solver designed for network routing problems and can be adapted to other combinatorial optimization problems. We also develop a novel, complete, two -level branching scheme. On a set of diverse bipath MCF instances, experimental results show that our algorithm significantly outperforms monolithic CP and mixed integer linear programming models and demonstrate the efficiency and flexibility brought by the tailored integration of linear programming and CP methodologies.
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.
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.
暂无评论