OPL is a modeling language for mathematical programming and combinatorial optimization problems. It is the first modeling language to combine high-level algebraic and set notations from modeling languages with a rich ...
详细信息
ISBN:
(数字)9783540481645
ISBN:
(纸本)3540665404
OPL is a modeling language for mathematical programming and combinatorial optimization problems. It is the first modeling language to combine high-level algebraic and set notations from modeling languages with a rich constraint language and the ability to specify search procedures and strategies that is the essence of constraint programming. In addition, OPL models can be controlled and composed using OPLSCRIPT, a script language that simplifies the development of applications that solve sequences of models, several instances of the same model, or a combination of both as in column-generation applications. This paper illustrates some of the functionalities of OPL for constraint programming using frequency allocation, sport-scheduling, and job-shop scheduling applications. It also illustrates how OPL models can be composed using OPLSCRIPT on a simple configuration example.
Bilevel optimization problems involve two decision makers who make their choices sequentially, either one according to its own objective function. Many problems arising in economy and management science can be modeled...
详细信息
Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real pro...
详细信息
Planning research is recently concerned with the resolution of more realistic problems as evidenced in the many works and new extensions to the Planning Domain Definition Language (PDDL) to better approximate real problems. Researchers' works to push planning algorithms and capture more complex domains share an essential ingredient, namely the incorporation of new types of constraints. Adding constraints seems to be the way of approximating real problems: these constraints represent the duration of tasks, temporal and resource constraints, deadlines, soft constraints, etc., i.e. features that have been traditionally associated to the area of scheduling. This desired expressiveness can be achieved by augmenting the planning reasoning capabilities, at the cost of slightly deviating the planning process from its traditional implicit purpose, that is finding the causal structure of the plan. However, the resolution of complex domains with a great variety of different constraints may involve as much planning effort as scheduling effort (and perhaps the latter being more prominent in many problems). For this reason, in this paper we present a general approach to model those problems under a constraint programming formulation which allows us to represent and handle a wide range of constraints. Our work is based on the original model of CPT, an optimal temporal planner, and it extends the CPT's formulation to deal with more expressive constraints. We will show that our general formulation can be used for planning and/or scheduling, from scheduling a given complete plan to generating the whole plan from scratch. However, our contribution is not a new planner but a constraint programming formulation for representing highly-constrained planning + scheduling problems.
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.
This study investigated resource leveling problems concerning linear construction projects based on the line of balance (LOB) technique and constraint programming. In addition, an LOB-based scheduling optimization mod...
详细信息
This study investigated resource leveling problems concerning linear construction projects based on the line of balance (LOB) technique and constraint programming. In addition, an LOB-based scheduling optimization model for resource leveling is proposed. This model retains the advantages of the conventional models, including multiple-resource management and natural rhythm concept, and showcases new abilities: scheduling optimization without specifying a fixed schedule;scheduling optimization on more comprehensive optimization objects and variable values;maintaining continuity of resource while completely eliminating the occurrence of idle time;handling more comprehensive constraints after the addition of logical constraints and explicit expression of certain new constraints. The flexibility, practicality, and solution quality of the proposed model were enhanced accordingly. Further, a scheduling system was developed to assist in schedule optimization and visualization. Lastly, effectiveness of the proposed model was verified based on four case studies involving three case projects investigated in extant LOB-based studies.
This paper addresses the non-preemptive unrelated parallel machine scheduling problem (PMSP) with job sequence and machine dependent setup times. This is a widely seen NP-hard (non-deterministic polynomial-time) probl...
详细信息
This paper addresses the non-preemptive unrelated parallel machine scheduling problem (PMSP) with job sequence and machine dependent setup times. This is a widely seen NP-hard (non-deterministic polynomial-time) problem with the objective to minimize the makespan. This study provides a noval constraint programming (CP) model with two customized branching strategies that utilize CP's global constraints, interval decision variables, and domain filtering algorithms. The performance of the CP model is evaluated against the state-of-art algorithms. In addition, we compare the performance of the default branching method in the CP solver against the two customized variants. In terms of average solution quality, the computational results indicate that the CP model slightly outperforms all of the state-of-art algorithms in solving small problem instances, is able to prove the optimality of 283 currently best-known solutions. It is also effective in finding good quality feasible solutions for the larger problem instances.
This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several j...
详细信息
This paper presents a constraint programming approach for a batch processing machine on which a finite number of jobs of non-identical sizes must be scheduled. A parallel batch processing machine can process several jobs simultaneously and the objective is to minimize the maximal lateness. The constraint programming formulation proposed relies on the decomposition of the problem into finding an assignment of the jobs to the batches, and then minimizing the lateness of the batches on a single machine. This formulation is enhanced by a new optimization constraint which is based on a relaxed problem and applies cost-based domain filtering techniques. Experimental results demonstrate the efficiency of cost-based domain filtering techniques. Comparisons to other exact approaches clearly show the benefits of the proposed approach: it can optimally solve problems that are one order of magnitude greater than those solved by a mathematical formulation or by a branch-and-price. (c) 2012 Elsevier B.V. All rights reserved.
In the past few years, the mining industry has seen a lot of operational changes. Digitalization and automation of many processes have paved the way for an increase in its general productivity. In keeping with this tr...
详细信息
In the past few years, the mining industry has seen a lot of operational changes. Digitalization and automation of many processes have paved the way for an increase in its general productivity. In keeping with this trend, this article presents a novel approach for optimizing underground mine scheduling for the short- and medium-term. This problem is similar to the Resource-Constrained Project Scheduling Problem, with the difference that all task completions are optional. The model uses constraint programming principles to maximize the Net Present Value of a mining project. It plans work shifts for up to a year in advance, considering specialized equipment, rock support and operational constraints. This is the first published paper using optional variables to model optional tasks in a real-life application. Results from its applications to datasets based on a Canadian gold mine demonstrate its ability to find optimal solutions in a reasonable time. A comparison with an equivalent Mixed Integer Programing model proves that the constraint programming approach offers clear gains in terms of computability and readability of the constraints.
Container vessel stowage planning is a hard combinatorial optimization problem with both high economic and environmental impact. We have developed an approach that often is able to generate near-optimal plans for larg...
详细信息
Container vessel stowage planning is a hard combinatorial optimization problem with both high economic and environmental impact. We have developed an approach that often is able to generate near-optimal plans for large container vessels within a few minutes. It decomposes the problem into a master planning phase that distributes the containers to bay sections and a slot planning phase that assigns containers of each bay section to slots. In this paper, we focus on the slot planning phase of this approach and present a constraint programming and Integer programming model for stowing a set of containers in a single bay section. This so-called slot planning problem is NP-hard and often involves stowing several hundred containers. Using state-of-the-art constraint solvers and modeling techniques, however, we were able to solve 90% of 236 real instances from our industrial collaborator to optimality within 1 second. Thus, somewhat to our surprise, it is possible to solve most of these problems optimally within the time required for practical application. (C) 2012 Elsevier B.V. All rights reserved.
For over five decades, researchers have presented various assembly line problems. Recently, assembly lines with multiple workers at each workstation have become very common in the literature. These lines are often fou...
详细信息
For over five decades, researchers have presented various assembly line problems. Recently, assembly lines with multiple workers at each workstation have become very common in the literature. These lines are often found in the manufacturing of large vehicles, where workers at a workstation may perform their assigned tasks at the same time. Most research on multi-manned assembly lines focuses on balancing tasks and workers among workstations and scheduling tasks for workers. This study, however, concentrates on assigning tasks to workers already assigned to a specific workstation, rather than balancing the entire line. The problem was identified through an industrial case study at a large vehicle manufacturing company. The study presents two methods, one using mixed integer linear programming and the other using constraint programming, to minimise the number of workers required on a multi-manned assembly line with sequence-dependent setup times. The results of the computational experiments indicate that the constraint programming method performs better than the mixed integer linear programming method on several modified benchmark instances from the literature. The constraint programming model is also tested on the real-world scenario of our industrial case study and leads to significant improvements in the productivity of the workstations.
暂无评论