In this study, the U-type assembly line balancing problem (UALBP) with assignment restrictions (AR-UALBP) is considered. Linked and incompatible distance and station restrictions are taken into account. New mathematic...
详细信息
In this study, the U-type assembly line balancing problem (UALBP) with assignment restrictions (AR-UALBP) is considered. Linked and incompatible distance and station restrictions are taken into account. New mathematical programming (MP) and constraint programming (CP) models are proposed. The objective function of the models is minimizing the cycle time for a given number of workstations. In addition to this objective, line efficiency and CPU time are also considered as other performance measurements. Numerical experiments on some problems from the literature are performed to evaluate the effectiveness of the proposed models. The results are compared with the results of the CP model of the straight ALBP with assignment restrictions and also the results from MP and CP models are compared with each other. The numerical results indicate that the proposed CP and MP models are more effective in obtaining better and optimal results when solving the AR-UALBP.
This paper addresses the three-dimensional open -dimension rectangular packing problem (3D-ODRPP). This problem addresses a set of rectangular boxes of given dimensions and a rectangular container of open dimensions. ...
详细信息
This paper addresses the three-dimensional open -dimension rectangular packing problem (3D-ODRPP). This problem addresses a set of rectangular boxes of given dimensions and a rectangular container of open dimensions. The objective is to pack all boxes orthogonally into the container while minimizing the container volume. Real -world applications of the 3D-ODRPP arise in production systems with operations of shipping or moving. The literature has presented mainly mixed -integer programming (MIP) formulations and their linearization techniques for the problem allied with general-purpose optimization solvers. To model and solve the 3D-ODRPP, we propose a constraint programming model based on a position -free modeling approach with logic operators. We ran computational experiments to assess the performance of the proposed model compared to the benchmark MIP models from instances of the literature. The results show our approach is competitive in different sets of problem instances in terms of reaching optimality as well as providing satisfactory feasible solutions quickly.
作者：
He, FangQu, RongUniv Nottingham
Sch Comp Sci Automated Scheduling Optimisat & Planning ASAP Gr Nottingham NG8 1BB England
This paper presents our investigations on a hybrid constraint programming based column generation (CP-CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world const...
详细信息
This paper presents our investigations on a hybrid constraint programming based column generation (CP-CG) approach to nurse rostering problems. We present a complete model to formulate all the complex real-world constraints in several benchmark nurse rostering problems. The hybrid CP-CG approach is featured with not only the effective relaxation and optimality reasoning of linear programming but also the powerful expressiveness of constraint programming in modeling the complex logical constraints in nurse rostering problems. In solving the CP pricing subproblem, we propose two strategies to generate promising columns which contribute to the efficiency of the CG procedure. A Depth Bounded Discrepancy Search is employed to obtain diverse columns. A cost threshold is adaptively tightened based on the information collected during the search to generate columns of good quality. Computational experiments on a set of benchmark nurse rostering problems demonstrate a faster convergence by the two strategies and justify the effectiveness and efficiency of the hybrid CP-CG approach. (c) 2012 Elsevier Ltd. All rights reserved.
The planning of operating rooms under block strategy is addressed in this study. The decisions are about opening the operating rooms and assigning specialties and surgeons to blocks at the tactical level, and sequenci...
详细信息
The planning of operating rooms under block strategy is addressed in this study. The decisions are about opening the operating rooms and assigning specialties and surgeons to blocks at the tactical level, and sequencing the surgeries at the operational level. This problem aims to minimize the costs of opening the operating rooms and their overtime, the waiting costs of patients, and the surgeons' idle costs. We propose two mixed integer linear programming models, a constraint programming (CP) model and a constraint programming-based column generation (CPCG) method for handling the problem. The performance of the models is evaluated by random test instances. The results indicate that CP and CPCG models are more efficient than the linear programming models in terms of computational time, and the number of variables and constraints. The proposed method CPCG generates optimal solutions for problem instances of up to 30 surgeries in less than 4 min. The CP model finds the optimal solutions in about one minute but proving the optimality of the found solutions is time-consuming in some instances. The maximum optimality gap for the proposed two-step linear programming model is 2%, while its run time is less than 20 s. A sensitivity analysis is done on the main parameters of the problem like objectives' weights, opening cost of ORs, unit waiting cost of patients, and the maximum available time in surgery blocks. Among the three objectives, the unit waiting cost of patients has the most sensitivity to variations of the objective function weights.(c) 2022 Elsevier Inc. All rights reserved.
An edge-coloring of a graph G = (V, E) is a function c that assigns an integer c(e) (called color) in {0,1,2, ... } to every edge e e E so that adjacent edges are assigned different colors. An edge-coloring is compact...
详细信息
An edge-coloring of a graph G = (V, E) is a function c that assigns an integer c(e) (called color) in {0,1,2, ... } to every edge e e E so that adjacent edges are assigned different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set of consecutive integers. The deficiency problem is to determine the minimum number of pendant edges that must be added to a graph such that the resulting graph admits a compact edge-coloring. We propose and analyze three integer programming models and one constraint programming model for the deficiency problem. (C) 2015 Elsevier Ltd. All rights reserved.
this paper, we present an original approach (CPRTA for "constraint programming for solving Real-Time Allocation") based on constraint programming to solve a static allocation problem of hard real-time tasks....
详细信息
this paper, we present an original approach (CPRTA for "constraint programming for solving Real-Time Allocation") based on constraint programming to solve a static allocation problem of hard real-time tasks. This problem consists in assigning periodic tasks to distributed processors in the context of fixed priority preemptive scheduling. CPRTA is built on dynamic constraint programming together with a learning method to find a feasible processor allocation under constraints. Two efficient new approaches are proposed and validated with experimental results. Moreover, CPRTA exhibits very interesting properties. It is complete (if a problem has no solution, the algorithm is able to prove it);it is non-parametric (it does not require specific tuning) thus allowing a large diversity of models to be easily considered. Finally, thanks to its capacity to explain failures, it offers attractive perspectives for guiding the architectural design process. (c) 2007 Elsevier Inc. All rights reserved.
The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles can be packed in a larger rectangle of fixed size. We propose an exact method for 2OPP, based on a new constraint-ba...
详细信息
The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles can be packed in a larger rectangle of fixed size. We propose an exact method for 2OPP, based on a new constraint-based scheduling model. We provide a generalization of energetic reasoning techniques for the problem under investigation. Feasibility tests requiring the solution of subset-sum problems are described. Computational results confirm the efficiency of our method compared to others in the literature. (c) 2006 Elsevier Ltd. All rights reserved.
Scheduling and dispatching tools for high-performance computing (HPC) machines have the key role of mapping jobs to the available resources, trying to maximize performance and quality-of-service (QoS). Allocation and ...
详细信息
Scheduling and dispatching tools for high-performance computing (HPC) machines have the key role of mapping jobs to the available resources, trying to maximize performance and quality-of-service (QoS). Allocation and Scheduling in the general case are well-known NP-hard problems, forcing commercial schedulers to adopt greedy approaches to improve performance and QoS. Search-based approaches featuring the exploration of the solution space have seldom been employed in this setting, but mostly applied in off-line scenarios. In this paper, we present the first search-based approach to job allocation and scheduling for HPC machines, working in a production environment. The scheduler is based on constraint programming, an effective programming technique for optimization problems. The resulting scheduler is flexible, as it can be easily customized for dealing with heterogeneous resources, user-defined constraints and different metrics. We evaluate our solution both on virtual machines using synthetic workloads, and on the Eurora HPC with production workloads. Tests on a wide range of operating conditions show significant improvements in waitings and QoS in mid-tier HPC machines w.r.t state-of-the-art commercial rule-based dispatchers. Furthermore, we analyze the conditions under which our approach outperforms commercial approaches, to create a portfolio of scheduling algorithms that ensures robustness, flexibility and scalability.
Background: The protein folding problem remains one of the most challenging open problems in computational biology. Simplified models in terms of lattice structure and energy function have been proposed to ease the co...
详细信息
Background: The protein folding problem remains one of the most challenging open problems in computational biology. Simplified models in terms of lattice structure and energy function have been proposed to ease the computational hardness of this optimization problem. Heuristic search algorithms and constraint programming are two common techniques to approach this problem. The present study introduces a novel hybrid approach to simulate the protein folding problem using constraint programming technique integrated within local search. Results: Using the face-centered-cubic lattice model and 20 amino acid pairwise interactions energy function for the protein folding problem, a constraint programming technique has been applied to generate the neighbourhood conformations that are to be used in generic local search procedure. Experiments have been conducted for a few small and medium sized proteins. Results have been compared with both pure constraint programming approach and local search using well-established local move set. Substantial improvements have been observed in terms of final energy values within acceptable runtime using the hybrid approach. Conclusion: constraint programming approaches usually provide optimal results but become slow as the problem size grows. Local search approaches are usually faster but do not guarantee optimal solutions and tend to stuck in local minima. The encouraging results obtained on the small proteins show that these two approaches can be combined efficiently to obtain better quality solutions within acceptable time. It also encourages future researchers on adopting hybrid techniques to solve other hard optimization problems.
This contribution introduces an efficient constraint programming (CP) model that copes with largescale scheduling problems in multiproduct multistage batch plants. It addresses several features found in industrial env...
详细信息
This contribution introduces an efficient constraint programming (CP) model that copes with largescale scheduling problems in multiproduct multistage batch plants. It addresses several features found in industrial environments, such as topology constraints, forbidden product-equipment assignments, sequence-dependent changeover tasks, dissimilar parallel units at each stage, limiting renewable resources and multiple-batch orders, among other relevant plant characteristics. Moreover, the contribution deals with various inter-stage storage and operational policies. In addition, multiple-batch orders can be handled by defining a campaign operating mode, and lower and upper bounds on the number of batches per campaign can be fixed. The proposed model has been extensively tested by means of several case studies having various problem sizes and characteristics. The results have shown that the model can efficiently solve medium and large-scale problems with multiple constraining features. The approach has also rendered good quality solutions for problems that consider multiple-batch orders under a campaign-based operational policy. (C) 2016 Elsevier Ltd. All rights reserved.
暂无评论