检索结果-内蒙古大学图书馆

A constraint programming approach for a batch processing problem with non-identical job sizes

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2012年第3期221卷 533-545页

作者： Malapert, Arnaud Gueret, Christelle Rousseau, Louis-Martin Ecole Mines CNRS LINA UMR 6241 Nantes France Ecole Mines CNRS IRCCyN UMR 6597 Nantes France Ecole Polytech CIRRELT Montreal PQ H3C 3A7 Canada

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.

关键词： Combinatorial optimization Artificial intelligence constraint programming Scheduling Packing

来源：评论

学校读者我要写书评

暂无评论

A constraint programming model for fast optimal stowage of container vessel bays

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2012年第1期220卷 251-261页

作者： Delgado, Alberto Jensen, Rune Moller Janstrup, Kira Rose, Trine Hoyer Andersen, Kent Hoj IT Univ Copenhagen DK-2300 Copenhagen S Denmark Univ Copenhagen DK-2100 Copenhagen O Denmark Aarhus Univ DK-8000 Aarhus Denmark

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.

关键词： Container vessel stowage planning Slot planning constraint programming Integer programming

来源：评论

学校读者我要写书评

暂无评论

Generalised graph colouring by a hybrid of local search and constraint programming

引用

DISCRETE APPLIED MATHEMATICS 2008年第2期156卷 148-158页

作者： Prestwich, Steven Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Constraint Computat Ctr Cork Ireland

The IMPASSE class of local search algorithms have given good results on many vertex colouring benchmarks. Previous work enhanced IMPASSE by adding the constraint programming technique of forward checking, in order to prune colouration neighbourhoods during search. On several large graphs the algorithm found the best known colourings. This paper extends the work by improving the heuristics and generalising the approach to bandwidth multicolouring. It is shown to give better results than a related search algorithm on an integer programming model, and to be competitive with published results. Experiments indicate that stronger constraint propagation further improves search performance, but that a symmetry breaking technique has unpredictable effects. (C) 2007 Elsevier B.V. All rights reserved.

关键词： generalised graph colouring hybrid local search constraint programming forward checking

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach to a real-world workforce scheduling problem for multi-manned assembly lines with sequence-dependent setup times

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年第9期62卷 3212-3229页

作者： Guner, Funda Gorur, Abdul K. Satir, Benhur Kandiller, Levent Drake, John H. Cankaya Univ Dept Ind Engn Ankara Turkiye Cankaya Univ Software Engn Ankara Turkiye Yasar Univ Dept Ind Engn Izmir Turkiye Univ Leicester Sch Comp & Math Sci Leicester England

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.

关键词： Workforce scheduling multi-manned assembly line constraint programming sequence-dependent setup times mixed integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Equitable optimized airspace sectorization based on constraint programming and OWA aggregation

引用

AIRCRAFT ENGINEERING AND AEROSPACE TECHNOLOGY 2020年第8期92卷 1225-1243页

作者： Mogtit, Abdessamed Aribi, Noureddine Lebbah, Yahia Lagha, Mohand BLIDA1 Univ Aeronaut Sci Lab Aeronaut & Spatial Studies Inst Blida Algeria Univ Oran1 LITIO Lab Oran Algeria

Purpose Airspace sectorization is an important task, which has a significant impact in the everyday work of air control services. Especially in recent years, because of the constant increase in air traffic, existing airspace sectorization techniques have difficulties to tackle the large air traffic volumes, creating imbalanced sectors and uneven workload distribution among sectors. The purpose of this paper is to propose a new approach to find optimal airspace sectorization balancing the traffic controller workload between sectors, subject to airspace requirements. Design/methodology/approach A constraint programming (CP) model called equitable airspace sectorization problem (EQASP) relies on ordered weighted averaging (OWA) multiagent optimization and the parallel portfolio architecture has been developed, which integrates the equity into an existing CP approach (Trandacet al., 2005). The EQASP was evaluated and compared with the method ofTrandacet al.(2005), according to the quality of workload balancing between sectors and the resolution performance. The comparison was achieved using real air traffic low-altitude network data sets of French airspace for five flight information regions for 24 h a day and the Algerian airspace for three various periods (off peak hours, peak hours and 24 h). Findings It has been demonstrated that the proposed EQASP model, which is based on OWA multicriteria optimization method, significantly improved both the solving performance and the workload equity between sectors, while offering strong theoretical properties of the balancing requirement. Interestingly, when solving hard instances, our parallel sectorization tool can provide, at any time, a workable solution, which satisfies all geometric constraints of sectorization. Practical implications This study can be used to design well-balanced air sectors in terms of workload between control units in the strategic phase. To fulfil the airspace users' constraints, one can refer to this

关键词： Airspace sectorization Air traffic management Equity constraint programming Multicriteria optimization Portfolio approach

来源：评论

学校读者我要写书评

暂无评论

Operating room scheduling with surgical team: a new approach with constraint programming and goal programming

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2023年第4期31卷 1061-1085页

作者： Gur, Seyda Pinarbasi, Mehmet Alakas, Haci Mehmet Eren, Tamer Organized Ind Zone Vocat Sch Sanliurfa Turkey Kirikkale Univ Fac Engn Dept Ind Engn Kirikkale Turkey

In recent years, there has been a significant increase in health expenditures due to population growth. In this context, hospital administrators have started to look for ways to use existing resources effectively. Operating rooms are one of the most important units of a hospital. The efficient use of these units is seen as a decrease in cost items and an increase in revenues. At this point, it is aimed to use the operating rooms effectively in this study. The fact that it contains many uncertainties and many stakeholders in its structure complicates the solution process of the operating room scheduling problem. In this study, planning was made that considered the uncertainty in the operation times and the surgeons, nurses, and anesthesiologists in the surgical team. To solve the problem, the logical modeling power of the constraint programming method and the power of the goal programming method to stretch rigid constraints were utilized. In the first stage, the balanced assignment of the surgical team (surgeon-nurse-anesthesiologist) was carried out, while in the second stage, operations were assigned to the operating rooms. The proposed model was evaluated according to the operating rooms' utilization rates and the solution's effectiveness. The results showed that the proposed model successfully created an effective and efficient schedule.

关键词： Operating room scheduling Goal programming constraint programming Surgical team

来源：评论

学校读者我要写书评

暂无评论

Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 142卷 106347-106347页

作者： Meng, Leilei Zhang, Chaoyong Ren, Yaping Zhang, Biao Lv, Chang Liaocheng Univ Sch Comp Sci Liaocheng 252059 Shandong Peoples R China Huazhong Univ Sci & Technol State Key Lab Digital Mfg Equipment & Technol Wuhan 430074 Peoples R China Jinan Univ Sch Intelligent Syst Sci & Engn Zhuhai Campus Zhuhai 519070 Peoples R China

This paper intends to address the distributed flexible job shop scheduling problem (DFJSP) with minimizing maximum completion time (makespan). In order to solve this problem, we propose four mixed integer linear programming (MILP) models as well as a constraint programming (CP) model, among which four MILP models are formulated based on four different modeling ideas. MILP models are effective in solving small-scaled problems to optimality. DFJSP is NP-hard, therefore, we propose an efficient constraint programming (CP) model based on interval decision variables and domain filtering algorithms. Numerical experiments are conducted to evaluate the performance of the proposed MILP models and CP model. The results show that the sequence-based MILP model is the most efficient one, and the proposed CP model is effective in finding good quality solutions for the both the small-sized and large-sized instances. The CP model incomparably outperforms the state-of-the-art algorithms and obtains new best solutions for 11 benchmark problems. Moreover, the best MILP model and CP model have proved the optimality of 62 best-known solutions.

关键词： Distributed flexible job shop scheduling problem Mixed integer linear programming constraint programming Makespan

来源：评论

学校读者我要写书评

暂无评论

Optimization of Next-Day Delivery Coverage using constraint programming and Random Key Optimizers

arXiv

引用

arXiv 2025年

作者： Brubaker, Kyle Booth, Kyle E.C. Schuetz, Martin J.A. Loick, Philipp Shen, Jian Ramamurthy, Arun Paschos, Georgios Amazon Advanced Solutions Lab SeattleWA98170 United States Amazon EU Science and Technology Luxembourg

We consider the logistics network of an e-commerce retailer, specifically the so-called "middle mile" network, that routes inventory from supply warehouses to distribution stations to be ingested into the terminal ("last mile") delivery network. The speed of packages through this middle mile network is a key determinant for the ultimate delivery speed to the end user. An important target for a retailer is to maximize the fraction of user orders that can be serviced within one day, i.e., next-day delivery. As such, we formulate the maximization of expected next-day delivery coverage within the middle-mile network as an optimization problem, involving a set of temporal and capacity-based constraints on the network and requiring the use of a black-box model to evaluate the objective function. We design both exact constraint programming (CP) and heuristic random-key optimizer (RKO) approaches, the former of which uses a proxy objective function. We perform experiments on large-scale, real-world problem instances and show that both approaches have merit, in that they can match or outperform the baseline solution, a bespoke greedy solver with integrated local search, in expected next-day delivery coverage. Our experiments focus on two high-level problem definitions, starting with a base problem and then adding more complexity, and also explore the generalization of the solvers across a range of problem instance sizes. We find that a hybrid model using RKO and a bespoke local search protocol performs best on the full problem definition with respect to expected next-day delivery (increase of +50 basis points [bps] over baseline) but can take days to run, whereas the hybrid model using CP and local search is slightly less competitive (+20 bps) but takes only hours to run. Copyright © 2025, The Authors. All rights reserved.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming Model for Assembly Line Balancing and Scheduling with Walking Workers and Parallel Stations 30

Constraint Programming Model for Assembly Line Balancing and...

引用

30th International Conference on Principles and Practice of constraint programming, CP 2024

作者： Pucel, Xavier Roussel, Stéphanie ONERA ONERA DTIS Université de Toulouse Toulouse France

ISBN: (纸本)9783959773362

In the context of aircraft assembly lines, increasing the production rate and decreasing the operating costs are two important, and sometimes contradictory, objectives. In small assembly lines, sharing production resources across workstations is a simple and efficient way to reduce operating costs. Therefore, workers are not assigned to a unique workstation but can walk between them. On the other side, paralleling workstations is an efficient way to increase the production rate. However, the combination of both strategies create complex conditions for tasks to access the production resources. This paper addresses the problem of allocating tasks to workstations and scheduling them in an assembly line where workers can freely walk across workstations, and where workstations can be organized in parallel. We model this novel problem with constraint programming. We evaluate it on real world industrial use cases coming from aircraft manufacturers, as well as synthetic use cases adapted from the literature. © Xavier Pucel and Stéphanie Roussel.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

constraint programming and industrial applications 1st

Constraint programming and industrial applications

引用

1st International Conference on Principles and Practice of constraint programming, CP 1995

作者： Touraïvane, T. PrologIA Parc Technologique de Luminy case 919 MarseilleCedex 0913288 France

ISBN: (纸本)3540602992

PrologIA has been designing and marketing AI languages and tools since 1984. The company occupies a active position in research into CLP and Natural Language processing. PrologIA has created expert systems for diagnosis aid, file rationalization etc… and develops turnkey real-life applications. This paper presents two applications based on CLP technology: a decision support system in the field of middle term banking planning grounded on the constraint Logic programming technology and a crew scheduling application mixing constraint Logic programming and Set Partioning Modeling. © Springer-Verlag Berlin Heidelberg 1995.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：