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

Rule-based modeling and constraint programming based solution of the assembly line balancing problem

EXPERT SYSTEMS WITH APPLICATIONS 2012年第3期39卷 3484-3493页

作者： Topaloglu, Seyda Salum, Latif Supciller, Aliye Ayca Dokuz Eylul Univ Dept Ind Engn TR-35160 Izmir Turkey

The assembly line balancing problem employs traditional precedence graphs to model precedence relations among assembly tasks. Yet they cannot address alternative ways of assembling a product. That is, they only model conjunctions, not disjunctions. Moreover, some additional constraints need also to be considered, but these constraints cannot be modeled effectively through precedence graphs, e.g., constraints indicating certain tasks cannot be assigned into the same station. To address these issues, this paper proposes to model assembly constraints through the well known If-then rules, and to solve the rule-based model through constraint programming (CP), as CP naturally models logical assertions. The paper also shows how to map a rule-based model to a CP or an integer programming (IP) model. Finally, a computational experiment is carried out to analyze the performances of CP and IP models with respect to modeling capability, solution quality and time. The results reveal that CP is more effective and efficient than IP. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Assembly line balancing Precedence graphs Rule-based modeling constraint programming

来源：评论

学校读者我要写书评

暂无评论

Manufacturing cell formation with flexible processing capabilities and worker assignment: Comparison of constraint programming and integer programming approaches

引用

PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE 2018年第11期232卷 2054-2068页

作者： Baykasoglu, Adil Topaloglu, Seyda Senyuzluler, Filiz Dokuz Eylul Univ Fac Engn Dept Ind Engn Tinaztepe Campus TR-35397 Izmir Turkey

Cell formation deals with grouping of machines and parts in manufacturing systems according to their compatibility. Manufacturing processes are surrounded with an abundance of complex constraints which should be considered carefully and represented clearly for obtaining high efficiency and productivity. constraint programming is a new approach to combinatorial optimization and provides a rich language to represent complex constraints easily. However, the cell formation problems are well suited to be solved by constraint programming approach since the problem has many constraints such as part-machine requirements, availabilities in the system in terms of capacity, machine and worker abilities. In this study, the cell formation problem is modeled using machine, part processing and worker flexibilities via resource element-based representation. Resource elements define the processing requirements of parts and processing capabilities of machines and workers, which are resource-independent capability units. A total of 12 case problems are generated, and different search phases of constraint programming are defined for the solution procedure. The cell formation problem is modeled in both constraint programming and integer programming, and a comparative analysis of constraint programming and integer programming model solutions is done. The results indicate that both the models are effective and efficient in the solution of the cell formation problem.

关键词： Cellular manufacturing group technology constraint programming flexibility resource elements

来源：评论

学校读者我要写书评

暂无评论

Combining mixed integer programming and constraint programming to solve the integrated scheduling problem of container handling operations of a single vessel

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第3期285卷 884-901页

作者： Qin, Tianbao Du, Yuquan Chen, Jiang Hang Sha, Mei Shanghai Maritime Univ Coll Transport & Commun Shanghai 200135 Peoples R China Univ Tasmania Australian Maritime Coll Natl Ctr Ports & Shipping Launceston Tas 7250 Australia Xian Jiao Tong Liverpool Univ Int Business Sch Suzhou Suzhou 215123 Peoples R China

In the container terminals of seaports, the container handling system consists of a variety of container handling machines such as quay cranes, internal yard trucks, and yard cranes. This study applies a holistic approach to the integrated scheduling of these machines for the container handling operations of a single vessel. We formulate this special hybrid flow shop scheduling problem through both mixed integer programming (MIP) and constraint programming (CP) techniques. Then we develop an easily-implemented approach that combines the strengths of MIP and CP. First, the MIP model, which only considers quay crane scheduling, is solved by an MIP solver, and a quay crane allocation plan is retrieved from the MIP solution. Then, this quay crane allocation plan is fed to the CP model, warm-starting the branch-and-prune algorithm built in a CP optimizer. Our numerical experiments reveal that this hybrid MIP/CP approach can solve the large-sized instances with up to 10 00 containers, 6 quay cranes, 36 yard trucks, and 15 yard cranes to optimality with a gap of less than 3.31%, within a solution time of 2 minutes. If we increase the solution time to 5 minutes, this hybrid approach solves larger instances with up to 1400 containers to optimality with a gap of less than 1.41%. The state-of-the-art dedicated algorithms reported in the literature (which address an easier version of the same problem by ignoring non-crossing constraints and safety margins between quay cranes) are only able to find solutions for real-life instances with up to 500 containers within the solution time of 2930 or 5221 seconds, leaving a 4% or an unknown optimality gap. Thus, this study improves the solution of this integrated scheduling problem in terms of the instance size, solution efficiency, and solution optimality. (C) 2020 Elsevier B.V. All rights reserved.

关键词： OR in maritime industry Container terminal Container unloading/loading problem Mixed integer programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

Transient inter-production scheduling based on Petri nets and constraint programming

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2011年第22期49卷 6591-6608页

作者： Bourdeaud'huy, Thomas Belkahla, Olfa Yim, Pascal Korbaa, Ouajdi Ghedira, Khaled Ecole Cent Lille Lab Automat Genie Informat & Signal F-5960 Villeneuve Dascq France

In this article, we focus on the transient inter-production scheduling problem between two cyclic productions in the framework of flexible manufacturing systems. This problem is first formulated as a reachability problem in timed Petri nets (TPN), then solved using a methodology based on constraint programming. Our work is based on the controlled executions proposed by Chretienne to model the sequence of transition firing dates. Our methodology is based on a preliminary resolution of the state equation between initial and final states in the underlying non-TPN. Then, we choose a duration T-max corresponding to the maximal duration time of the scheduling. For each solution S of the state equation, we build a controlled execution from the sequence of firings in S. After the propagation of firing date constraints and reachability constraints in the TPN, we use constraint programming to enumerate the set of feasible controlled executions.

关键词： cyclic scheduling transient production Petri nets constraint programming

来源：评论

学校读者我要写书评

暂无评论

Efficient Optimization Strategies with constraint programming

引用

AICHE JOURNAL 2010年第2期56卷 387-404页

作者： Kotecha, Prakash R. Bhushan, Mani Gudi, Ravindra D. Indian Inst Technol Dept Chem Engn Bombay 400076 Maharashtra India

In this article, we propose novel strategies for the efficient determination of multiple solutions for a single objective, as well as globally optimal pareto fronts for multiobjective, optimization problems using constraint programming (CP). In particular, we propose strategies to determine, (i) all the multiple (globally) optimal solutions of a single objective optimization problem, (ii) K-best feasible solutions of a single objective optimization problem, and (iii) globally optimal pareto fronts (including non-convex pareto fronts) along with their multiple realizations for multiobjective optimization problems. It is shown here that the proposed strategy for determining K-best feasible solutions can be tuned as per the requirement of the user to determine either K-best distinct or nondistinct solutions. Similarly, the strategy for determining globally optimal pareto fronts can also be modified as per the requirement of the user to determine either only the distinct set of pareto points or determine the pareto points along with all their multiple realizations. All the proposed techniques involve appropriately modifying the search techniques and are shown to be computationally efficient in terms of not requiring successive re-solving of the problem to obtain the required solutions. This work therefore convincingly addresses the issue of efficiently determining globally optimal pareto fronts;in addition, it also guarantees the determination of all the possible realizations associated with each pareto point. The uncovering of such solutions can greatly aid the designer in making informed decisions. The proposed approaches are demonstrated via two case studies, which are nonlinear, combinatorial optimization problems, taken from the area of sensor network design. (C) 2009 American Institute of Chemical Engineers AIChE J, 56: 387-404, 2010

关键词： optimization design multiobjective optimization constraint programming sensor network design multiple solutions pareto fronts

来源：评论

学校读者我要写书评

暂无评论

On the verification of UML/OCL class diagrams using constraint programming

引用

JOURNAL OF SYSTEMS AND SOFTWARE 2014年 93卷 1-23页

作者： Cabot, J. Clariso, R. Riera, D. Ecole Mines Nantes INRIA AtlanMod Res Grp F-44307 Nantes 3 France Univ Oberta Catalunya Estudis Informat Multimedia & Telecomunicacio Barcelona 08018 Spain

Assessment of the correctness of software models is a key issue to ensure the quality of the final application. To this end, this paper presents an automatic method for the verification of UML class diagrams extended with OCL constraints. Our method checks compliance of the diagram with respect to several correctness properties including weak and strong satisfiability or absence of constraint redundancies among others. The method works by translating the UML/OCL model into a constraint Satisfaction Problem (CSP) that is evaluated using state-of-the-art constraint solvers to determine the correctness of the initial model. Our approach is particularly relevant to current MDA and MOD methods where software models are the primary artifacts of the development process and the basis for the (semi-)automatic code-generation of the final application. (C) 2014 Elsevier Inc. All rights reserved.

关键词： UML/OCL Model verification constraint programming

来源：评论

学校读者我要写书评

暂无评论

Design of financial CDO squared transactions using constraint programming

引用

constraintS 2007年第2期12卷 179-205页

作者： Flener, Pierre Pearson, Justin Reyna, Luis G. Sivertsson, Olof Uppsala Univ Dept Informat Technol SE-75105 Uppsala Sweden Swiss Re Swiss Re Financial Prod New York NY 10055 USA

We give an approximate and often extremely fast method of building a particular kind of portfolio in finance, here called a portfolio design (PD), with applications in the credit derivatives market, for example when designing collateralised debt obligations squared (CDO2) transactions. A PD generalises a balanced incomplete block design (BIBD) and is usually harder to build. Worse, typical financial PDs are an order of magnitude larger than the largest BIBDs built so far by constraint programs, and in practice an optimisation version of the problem of building PDs has to be solved. Our method is based on embedding small designs, whose determination is itself a constraint satisfaction problem, into the original large design. Together with the detection of when a PD might be a BIBD, symmetry breaking, extended reuse of previously built PDs, and admissibility checking during search, the performance of the method becomes good enough for designing (near-)optimal CDO2 transactions, with sizes common in the credit derivatives market, within minutes. For example, we optimally build a typical financial PD, which has over 10(746) symmetries, in just a few minutes. The high quality of our approximate designs can be assessed by comparison with a lower bound on the optimum. Our designs sufficiently improve the currently best ones so as often to make the difference between having and not having a feasible CDO2 transaction due to investor and rating-agency constraints.

关键词： financial mathematics credit derivatives collateralised debt obligation (CDO) CDO squared portfolio design (PD) optimal portfolio design (OPD) balanced incomplete block design (BIBD) constraint programming embedding

来源：评论

学校读者我要写书评

暂无评论

Scheduling a Real-World Photolithography Area With constraint programming

引用

IEEE TRANSACTIONS ON SEMICONDUCTOR MANUFACTURING 2023年第4期36卷 590-598页

作者： Deenen, Patrick Nuijten, Wim Akcay, Alp Eindhoven Univ Technol Dept Ind Engn & Innovat Sci Operat Planning Accoun NL-5600 MB Eindhoven Netherlands Eindhoven Univ Technol Math & Comp Sci Dept NL-5612 AE Eindhoven Netherlands Eindhoven Univ Technol Dept Ind Engn & Innovat Sci NL-5600 MB Eindhoven Netherlands

This paper studies the problem of scheduling machines in the photolithography area of a semiconductor manufacturing facility. The scheduling problem is characterized as an unrelated parallel machine scheduling problem with machine eligibilities, sequence- and machine-dependent setup times, auxiliary resources and transfer times for the auxiliary resources. Each job requires two auxiliary resources: a reticle and a pod. Reticles are handled in pods and a pod contains multiple reticles. Both reticles and pods are used on multiple machines and a transfer time is required if transferred from one machine to another. A novel constraint programming (CP) approach is proposed and is benchmarked against a mixed-integer programming (MIP) method. The results of the study, consisting of a real-world case study at a global semiconductor manufacturer, demonstrate that the CP approach significantly outperforms the MIP method and produces high-quality solutions for multiple real-world instances, although optimality cannot be guaranteed.

关键词： Semiconductor manufacturing production scheduling photolithography constraint programming integer linear programming real-world case study

来源：评论

学校读者我要写书评

暂无评论

A multi-objective constraint programming approach to address clustering problems in mine planning

引用

ENGINEERING COMPUTATIONS 2024年第10期41卷 2682-2706页

作者： Mariz, Jorge Luiz Valenca Peroni, Rodrigo de Lemos Silva, Ricardo Martins de Abreu Badiozamani, Mohammad Mahdi Askari-Nasab, Hooman Univ Fed Rio Grande Do Sul Min Engn Dept Porto Alegre Brazil Univ Alberta Sch Min & Petr Engn Dept Civil & Environm Engn Edmonton AB Canada Univ Alberta Sch Min & Petr Engn Edmonton AB Canada

Purpose - The mine sequencing problem is NP-hard. Therefore, simplifying it is necessary. One way to do this is to employ clusters as input instead of individual blocks. The mining cut clustering problem has been little addressed in the literature, and the solutions used are almost always heuristic. We solve the mining cut clustering problem, which is NP-hard, through single- and multi-objective optimization, finding results that are local optima in acceptable computational time. Design/methodology/approach - We first elaborate an ILP-based model to address the mining cut clustering problem. We employ a mono-objective approach and two multi-objective approaches, solving all these models by constraint programming. To choose the best solutions generated by multi-objective approaches, we employ two multi-criteria decision analysis approaches, considering different weight configurations. We developed a case study using real data. Findings - We verified that the approaches based on multi-objective optimization performed better than the mono-objective approach for the economic return criterion. The weighted-sum multi-objective approach presented the best results considering all objective functions used. Once viable solutions were obtained through multi-objective optimization, multi-criteria decision analysis approaches almost always selected the same solution. We obtained solutions that are local optima in acceptable computational time. Research limitations/implications This study solves an instance with 80 blocks. Consequently, it is aimed at short-term mine planning. The methodology has not yet been evaluated in large instances related to medium- and long-term mine planning. Originality/value - This is the first time that multi-objective optimization has been employed to solve the mining cut custering problem. Even other problems related to mine planning were, at most, solved by goal programming, so that multi-objective optimization is a knowledge that is not widespread

关键词： Mine planning Operational mine sequencing Mining cut clustering Multi-objective optimization constraint programming

来源：评论

学校读者我要写书评

暂无评论

Mathematical programming techniques in constraint programming: A short overview

引用

JOURNAL OF HEURISTICS 2002年第1期8卷 7-17页

作者： Focacci, F Lodi, A Milano, M Univ Ferrara Dipartimento Ingn I-44100 Ferrara Italy ILOG SA 9 F-94253 Gentilly France Univ Bologna DEIS I-40136 Bologna Italy

In recent years, the integration of techniques from Artificial Intelligence and Operations Research has shown to improve the solutions of complex and large scale combinatorial optimization problems, in terms of efficiency, scalability and optimality. In this context, constraint programming is an emerging discipline situated at the confluence of the two fields that has been recognized as a suitable environment for achieving such an integration. This paper briefly presents the integration directions explored in the literature, and provides some pointers to relevant work in these directions.

关键词： mathematical programming constraint programming integration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：