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

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

来源：评论

学校读者我要写书评

暂无评论

Optimal configuration planning of rule and optimization-based driven storage coupled micro cogeneration systems by the implementation of constraint programming

引用

JOURNAL OF ENERGY STORAGE 2022年 48卷

作者： Mohammadi, Hesam Mohammadi, Mohammad Ghasemi, Amir Shiraz Univ Sch Elect & Comp Engn Shiraz Iran Univ Tehran Coll Engn Sch Environm Tehran Iran

In this paper, an optimization model for optimal size and dispatch planning of micro combined heat and power systems regarding distinct structures for the inclusion of the cogeneration unit, auxiliary boiler, heat storage and battery storage in the configuration of the system is introduced. The presented model is developed in a unified form by the implementation of constraint programming to consider different strategies for the system's operation. Furthermore, important details such as minimum/maximum permissible state of charge, maximum charge/ discharge rate and battery inverter for modeling practical storages as technical specifications and simultaneous consideration of calendar life and life cycle as service life as well as assessment of heat dumping avoidance has been taken into account in this study. The model has been applied to three operation strategies and four kinds of buildings while considering two single-objective and one multi-objective optimization for minimization of the greenhouse gas emissions and annual costs of the system. The study has been validated by multiple study cases and the analyzes indicate that the implementation of different structures for the configuration of the micro CHP systems can impressively affect the optimum size and dispatch of these systems in each operation strategy. Comparison of the obtained results for the candidate multi-criteria solutions considering the exploitation of different storage options indicates that the inclusion of the heat storage by up to 21.5% further reduction in annual expenditures with an equal amount of emissions is a more influential energy storage option for utilization in the proposed residential cogeneration system. Regarding heat dumping assumption, dumping avoidance can be a powerful key factor in the system's management to prevent extra greenhouse generations by restricting the heedless minimization of the annual costs when it adversely affects the generation of the emissions.

关键词： Micro combined heat and power Energy storage Rule-based operation strategy Optimization-based operation strategy Heat dumping avoidance constraint programming

来源：评论

学校读者我要写书评

暂无评论

A novel constraint programming and simulated annealing for disassembly line balancing problem with AND/OR precedence and sequence dependent setup times

引用

COMPUTERS & OPERATIONS RESEARCH 2022年 146卷

作者： Kizilay, Damla ?Izmir Democracy Univ Ind Engn Dept TR-35140 Izmir Turkey

This study considers recycling the products to reuse or reproduce the precious parts of these products to provide environmental sustainability and for companies to adapt to competitive conditions. These recycling processes include the dismantling of the products using the disassembly lines. Disassembly line balancing problems contribute to these processes by ensuring that products are disassembled efficiently and at minimum cost. Therefore, these problems have started to attract more attention in the literature. This study considers the disassembly line balancing problem, with sequence-dependent setup time and complex AND/OR precedence relations between tasks. The managerial impacts highlighted by the proposed problem are of great importance both from environmental and industrial sustainability due to the recycling process of the life-threatening wastes. The study aims to disassemble the products using a minimum number of workstations. Mixed-integer linear programming and constraint programming models have been developed for the considered problem in question. As far as is known, the sequence-dependent disassembly line balancing problem, which has complex precedence relations, has not been studied in the literature before, and the constraint programming model developed is also novel. The study also compares the constraint programming model with/without an initial solution. In addition, a simulated annealing metaheuristic is proposed to solve the problem, and its results are compared with the results of the models. Setup times were generated for well-known instances obtained from the literature. The results obtained using these instances showed that the constraint programming model successfully solved the problem under consideration

关键词： Disassembly line balancing constraint programming Mixed integer linear programming Simulated annealing Sequence dependent setup time

来源：评论

学校读者我要写书评

暂无评论

A constraint programming model for making recommendations in personal process management: A design science research approach

引用

DECISION SUPPORT SYSTEMS 2022年 152卷 1页

作者： Oruc, Sercan Eren, P. Erhan Kocyigit, Altan Middle East Tech Univ Ankara Turkey

Decision-making in everyday life has an essential role in effectively completing personal tasks and processes. The complexity of these processes and the resulting cognitive load of managing them may vary significantly. To decrease the cognitive load created by such decision-making efforts and to obtain better outcomes, recommendation systems carry significant potential. In order to investigate the benefits provided by decision support systems (DSS) in personal process management (PPM), we first build a constraint programming (CP) model and a prototype context-aware-mobile application employing this CP model. Then, we evaluate the application and the model via two exemplary real-world scenarios. The scenarios form the core of the experiments conducted with 50 participants. We compare the participants' planning performances with and without the PPM system with quantitative metrics such as planning times and scenario objective values. In addition, System Usability Scale (SUS) questionnaires and open-ended questions provide qualitative evaluation results. Throughout the study, we apply the Design Science Research methodology to rigorously conduct research activities by proof of concept, proof of use, and proof of value. The empirical results clearly show that our proposed model for PPM is effective, and the developed prototype solution generates positive participant comments as well as a high SUS score. Overall, the prototype PPM system with CP implementation leads to better planning in less time in the planning phase, and it lets the user do fast replanning in the execution phase, which is invaluable in dynamically changing situations such as daily activities.

关键词： Personal process management Design science research constraint programming Business process management Intelligent personal assistants

来源：评论

学校读者我要写书评

暂无评论

Counterfactual explanations via inverse constraint programming 27

Counterfactual explanations via inverse constraint programmi...

引用

27th International Conference on Principles and Practice of constraint programming, CP 2021

作者： Korikov, Anton Beck, J. Christopher Department of Mechanical and Industrial Engineering University of Toronto Canada

ISBN: (纸本)9783959772112

It is increasingly recognized that automated decision making systems cannot be black boxes: users require insight into the reasons that decisions are made. Explainable AI (XAI) has developed a number of approaches to this challenge, including the framework of counterfactual explanations where an explanation takes the form of the minimal change to the world required for a user's desired decisions to be made. Building on recent work, we show that for a user query specifying an assignment to a subset of variables, a counterfactual explanation can be found using inverse optimization. Thus, we develop inverse constraint programming (CP): to our knowledge, the first definition and treatment of inverse optimization in constraint programming. We modify a cutting plane algorithm for inverse mixed-integer programming (MIP), resulting in both pure and hybrid inverse CP algorithms. We evaluate the performance of these algorithms in generating counterfactual explanations for two combinatorial optimization problems: the 0-1 knapsack problem and single machine scheduling with release dates. Our numerical experiments show that a MIP-CP hybrid approach extended with a novel early stopping criteria can substantially out-perform a MIP approach particularly when CP is the state of the art for the underlying optimization problem. © Anton Korikov and J. Christopher Beck.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

A constraint programming Approach to Solve Multi-skill Resource-constrained Project Scheduling Problem with Calendars

引用

INTERNATIONAL JOURNAL OF ENGINEERING 2022年第8期35卷 1579-1587页

作者： Nikaeen, R. Najafi, A. A. KN Toosi Univ Technol Fac Ind Engn Tehran Iran Ecole Technol Super Syst Engn Dept Montreal PQ Canada

The multi-skill resource constrained project scheduling is an important and challenging problem in project management. Two key issues that turn this topic into a challenging problem are the assumptions that are considered to approximate the model to a real-world problem and exact solution approach for the model. In this paper, we deal with this two issues. To consider real-word situations, we take into account calendars specifying time intervals during which the resources are available. We proposed a constraint programming approach to solve the problem exactly. The problem with and without resource calendars are modeled with mathematical programming (MP) and constraint programming (CP). In addition, the performance of CP approach is evaluated by comparing Time-Indexed Model (TIM) and Branch and Price (B&P) approaches. Computational results show that the proposed approach can efficiently solve real-size instances.

关键词： Multi-skill Project Scheduling constraint programming Mathematical programming

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Automated Verification of Care Pathways Using constraint programming

引用

IEEE JOURNAL OF BIOMEDICAL AND HEALTH INFORMATICS 2020年第9期24卷 2718-2725页

作者： de Figueiredo, Renan Pereira Ferreira Filho, Joao Bosco Sousa, Flavio R. C. Weber, Philip Litchfield, Ian Univ Fed Ceara Dept Comp Grp Comp Networking Software Engn & Syst GREat BR-60020181 Fortaleza Ceara Brazil Univ Fed Ceara Teleinformat Engn Dept DETI BR-60020181 Fortaleza Ceara Brazil Aston Univ Birmingham B4 7ET W Midlands England Univ Birmingham Inst Appl Hlth Res Birmingham B15 2TT W Midlands England

Bad construction of modeled care pathways can lead to satisfiability problems during the pathway execution. These problems can ultimately result in medical errors and need to be checked as formally as possible. Therefore, this study proposes a set of algorithms using a free open-source library dedicated to constraint programming allied with a DSL to encode and verify care pathways, checking four possible problems: states in deadlock, non-determinism, inaccessible steps and transitions with logically equivalent guard conditions. We then test our algorithms in 84 real care pathways used both in hospitals and surgeries. Using our algorithms, we were able to find 200 problems taking less than 1 second to complete the verification on most pathways.

关键词： Medical services Informatics DSL programming Business System recovery Electronic mail Clinical pathway constraint programming data-dependent transition system DSL satisfiability problems

来源：评论

学校读者我要写书评

暂无评论

Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2020年第23期58卷 7149-7166页

作者： Polo-Mejia, Oliver Artigues, Christian Lopez, Pierre Basini, Virginie Univ Toulouse CNRS LAAS CNRS Toulouse France CEA SETC DEC DEN St Paul Les Durance France

This paper presents the results of a research project aiming to optimise the scheduling of activities within a research laboratory of the 'Commissariat a l'Energie Atomique et aux Energies Alternatives (CEA)'. To tackle this problem, we decompose every activity into a set of elementary tasks to apply standard scheduling methods. We model the problem as an extended version of the Multi-Skill Project Scheduling Problem (MSPSP). As a first approach, we propose a Multi-Skill Project Scheduling Problem with penalty for preemption, along with its mixed-integer/linear programming (MILP) formulation, where the preemption is allowed applying a penalty every time an activity is interrupted. However, the previous approach does not take into account all safety constraints at the facility, and a more accurate variant of the problem is needed. We propose then to integrate the concept of partial preemption to the MSPSP. This concept, that has not been yet studied in the scientific literature, implies that only a subset of resources is released during preemption periods. The resulting MSPSP with partial preemption (MSPSP-PP) is modelled using two methodologies: MILP and constraint programming. Regarding the industrial need of having good solutions in a short time, we also present a greedy algorithm for the MSPSP-PP.

关键词： multi-skill research project scheduling partial preemption nuclear facility mixed-integer linear programming constraint programming greedy heuristic

来源：评论

学校读者我要写书评

暂无评论

A new constraint programming model and solving for the cyclic hoist scheduling problem

引用

constraintS 2020年第3-4期25卷 319-337页

作者： Wallace, Mark Yorke-Smith, Neil Monash Univ Melbourne Vic Australia Delft Univ Technol Delft Netherlands

The cyclic hoist scheduling problem (CHSP) is a well-studied optimisation problem due to its importance in industry. Despite the wide range of solving techniques applied to the CHSP and its variants, the models have remained complicated and inflexible, or have failed to scale up with larger problem instances. This article re-examines modelling of the CHSP and proposes a new simple, flexible constraint programming formulation. We compare current state-of-the-art solving technologies on this formulation, and show that modelling in a high-level constraint language, MiniZinc, leads to both a simple, generic model and to computational results that outperform the state of the art. We further demonstrate that combining integer programming and lazy clause generation, using the multiple cores of modern processors, has potential to improve over either solving approach alone.

关键词： constraint programming Hoist scheduling Modelling MiniZinc

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：