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

Schedule control model for linear projects based on linear scheduling method and constraint programming

AUTOMATION IN CONSTRUCTION 2014年 37卷 22-37页

作者： Tang, Yuanjie Liu, Rengkui Sun, Quanxin Beijing jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China Beijing Jiaotong Univ MOE Key Lab Urban Transportat Complex Syst Theory Beijing 100044 Peoples R China

China Railway is undertaking massive construction and development projects. A reasonable and resource-leveled schedule that allows for adjustments for unforeseen circumstances during construction is critical for managing railway construction projects. Currently, most construction projects use traditional network planning methods or the Gantt schedule for project management. However, these methods have limited applicability to railway construction projects, which are typically linear. This study uses the linear scheduling method and constraint programming techniques for solving schedule control problems faced during railroad construction. The proposal comprises a schedule control model, scheduling model, and schedule control system;the scheduling model is central to the schedule control model. Characteristics such as high flexibility and practicality facilitate multi-objective optimization during scheduling and modification of the linear schedule. The proposed model and algorithm were validated by comparing results with actual data from a highway construction project and the Urumqi-Dzungaria railway construction project. (C) 2013 Elsevier B.V. All rights reserved.

关键词： China railway construction project Linear scheduling method Resource leveling Schedule control constraint programming

来源：评论

学校读者我要写书评

暂无评论

Network configuration distributed production scheduling problem: A constraint programming approach

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2024年 188卷

作者： Ziadlou, Ghazal Emami, Saeed Asadi-Gangraj, Ebrahim Babol Noshiravani Univ Technol Dept Ind Engn Babol *** Iran

Nowadays, many massive factories are forced to distribute their products in several manufacturing units. This issue has caused the emergence of a novel category of problems called distributed production scheduling, which is vital in today's growing world. In this paper, the distributed production scheduling problem by considering network configuration with two echelons is addressed. The first and second echelon factories have different job configurations and have a hybrid flow shop and a flexible job shop environment, respectively. For this problem, A bi-objective mixed integer linear programming (MILP) model is presented to minimize the maximum completion time of jobs and transportation costs between the selected factories in two echelons, respectively. Consequently, the epsilon constraint method is used to deal with this bi-objective model. In addition, since distributed scheduling problems are classified as NP-Hard problems, it is very challenging to solve them for largesized instances. For this reason, a constraint programming model (CP) is also proposed. To evaluate the performance of the proposed MILP model and CP model, a total of 180 numerical instances are randomly generated in small, medium, and large sizes. The obtained results demonstrate the significant ability of the constraint programming approach in solving complex distributed scheduling problems even for large-sized instances with 30 jobs, 10 stages/operations for each job, 6 machines for each stage/operation, and 4 factories at each echelon in a reasonable time and proof that the CP model can outperform the MILP model in this problem.

关键词： Distributed scheduling Multi-factory scheduling Network configuration constraint programming Epsilon constraint method

来源：评论

学校读者我要写书评

暂无评论

A constraint programming approach to cutset problems

引用

COMPUTERS & OPERATIONS RESEARCH 2006年第10期33卷 2852-2865页

作者： Fages, F Lal, A INRIA Rocquencourt Projet Contraintes F-78153 Le Chesnay France

We consider the problem of finding a cutset in a directed graph G = (V, E), i.e., a set of vertices that cuts all cycles in G. Finding a cutset of minimum cardinality is NP-hard. There exist several approximate and exact algorithms, most of them using graph reduction techniques. In this paper, we propose a constraint programming approach to cutset problems and design a global constraint for computing cutsets. This cutset constraint is a global constraint over boolean variables associated to the vertices of a given graph and states that the subgraph restricted to the vertices having their boolean variable set to true is acyclic. We propose a filtering algorithm based on graph contraction operations and inference of simple boolean constraints, that has a linear time complexity in O (vertical bar E vertical bar +/- vertical bar V vertical bar). We discuss search heuristics based on graph properties provided by the cutset constraint, and show the efficiency of the cutset constraint on benchmarks of the literature for pure minimum cutset problems, and on an application to log-based reconciliation problems where the global cutset constraint is mixed with other boolean constraints. (c) 2005 Published by Elsevier Ltd.

关键词： constraint programming global constraints cutset feedback vertex set reconciliation

来源：评论

学校读者我要写书评

暂无评论

A Hybrid Tabu Search and constraint programming Algorithm for the Dynamic Dial-a-Ride Problem

引用

INFORMS JOURNAL ON COMPUTING 2012年第3期24卷 343-355页

作者： Berbeglia, Gerardo Cordeau, Jean-Francois Laporte, Gilbert HEC Montreal Dept Operat Management & Logist Montreal PQ H3T 2A7 Canada HEC Montreal Dept Management Sci Montreal PQ H3T 2A7 Canada

This paper introduces a hybrid algorithm for the dynamic dial-a-ride problem in which service requests arrive in real time. The hybrid algorithm combines an exact constraint programming algorithm and a tabu search heuristic. An important component of the tabu search heuristic consists of three scheduling procedures that are executed sequentially. Experiments show that the constraint programming algorithm is sometimes able to accept or reject incoming requests, and that the hybrid method outperforms each of the two algorithms when they are executed alone.

关键词： dial-a-ride problem dynamic constraint programming tabu search scheduling

来源：评论

学校读者我要写书评

暂无评论

Time windows and constraint programming to deal with strong restriction in the due date of productive systems

引用

ANNUAL REVIEWS IN CONTROL 2014年第1期38卷 134-146页

作者： Pessoa, Marcosiris A. O. Estombelo Montesco, Richard A. Junqueira, Fabricio dos Santos Filho, Diolino Jose Miyagi, Paulo E. Univ Sao Paulo Sao Paulo Brazil Univ Fed Sergipe Sergipe Brazil

The APS (Advanced Planning and Scheduling) systems are widely used by companies;however, the traditional APS systems cannot deal with problems whose the due date is a strong restriction. The problem derives from the way companies use their scheduling heuristics. This paper addresses this problem by using the concept of time windows with the constraint programming mechanism. A procedure is shown to generate the time windows and how they can be used for the APS systems. The APS heuristic approach that uses the concepts of time windows with constraint programming is introduced to solve problems for which the due date is a strong restriction. These heuristics, with tasks allocation either at the beginning or at the end of the task time window, eliminate the need for a priority scheme. To illustrate the advantage of the proposal, some examples are presented. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Mining Time-constrained Sequential Patterns with constraint programming

引用

constraintS 2017年第4期22卷 548-570页

作者： Aoga, John O. R. Guns, Tias Schaus, Pierre Univ Catholique Louvain UCLouvain Inst Informat & Commun Technol Elect & Appl Math Louvain Belgium UAC Ecole Doctorale Sci Ingn ED SDI Calavi Benin Vrije Univ Brussel Brussels Belgium Katholieke Univ Leuven Leuven Belgium

constraint programming (CP) has proven to be an effective platform for constraint based sequence mining. Previous work has focused on standard frequent sequence mining, as well as frequent sequence mining with a maximum 'gap' between two matching events in a sequence. The main challenge in the latter is that this constraint can not be imposed independently of the omnipresent frequency constraint. Indeed, the gap constraint changes whether a subsequence is included in a sequence, and hence its frequency. In this work, we go beyond that and investigate the integration of timed events and constraining the minimum/maximum gap as well as minimum/maximum span. The latter constrains the allowed time between the first and last matching event of a pattern. We show how the three are interrelated, and what the required changes to the frequency constraint are. Key in our approach is the concept of an extension window defined by gap/span and we develop techniques to avoid scanning the sequences needlessly, as well as using a backtracking-aware data structure. Experiments demonstrate that the proposed approach outperforms both specialized and CP-based approaches in almost all cases and that the advantage increases as the minimum frequency threshold decreases. This paper is an extension of the original manuscript presented at CPAIOR'17 [5].

关键词： Data mining Sequential pattern mining constraint programming Global constraint Gap constraint Span constraint Time constraint

来源：评论

学校读者我要写书评

暂无评论

On the optimal modeling and evaluation of job shops with a total weighted tardiness objective: constraint programming vs. mixed integer programming

引用

APPLIED MATHEMATICAL MODELLING 2015年第2期39卷 955-964页

作者： Sahraeian, Rashed Namakshenas, Mohammad Shahed Univ Coll Engn Dept Ind Engn Tehran Iran

In this study we consider the mapping of the main characteristics, i.e., the structural properties, of a classical job shop problem onto well-known combinatorial techniques, i.e., positional sets, disjunctive graphs, and linear orderings. We procedurally formulate three different models in terms of mixed integer programming (MIP) and constraint programming (CP) paradigms. We utilize the properties of positional sets and disjunctive graphs to construct tight MIP formulations in an efficient manner. In addition, the properties are retrieved by the polyhedral structures of the linear ordering and they are defined on a disjunctive graph to facilitate the formulation of the CP model and to reduce the number of dominant variables. The proposed models are solved and their computational performance levels are compared with well-known benchmarks in the job shop research area using IBM ILog Cplex software. We provide a more explicit analogy of the applicability of the proposed models based on parameters such as time efficiency, thereby producing strong bounds, as well as the expressive power of the modeling process. We also discuss the results to determine the best formulation, which is computationally efficient and structurally parsimonious with respect to different criteria. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Combinatorics constraint programming Job shop Mixed integer programming Total weighted tardiness

来源：评论

学校读者我要写书评

暂无评论

A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences

引用

constraintS 2022年第3期27卷 249-283页

作者： Cseh, Agnes Escamocher, Guillaume Genc, Begum Quesada, Luis Ctr Econ & Reg Studies Inst Econ Budapest Hungary Univ Coll Dublin Insight Ctr Data Analyt Dublin 4 Cork Dublin Ireland Univ Coll Cork Sch Comp Sci & Informat Technol Cork Ireland Confirm Ctr Smart Mfg Cork V94 C928 Ireland

We introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with, and that the choice of the search heuristic can help improve performance. Our experiments not only brought light to the role that learning and restarts can play in solving this kind of problems, but also allowed us to discover that in some cases combining strong and weak stability leads to reduced runtimes for the latter.

关键词： Three-dimensional stable matching with cyclic preferences 3DSM-cyc constraint programming Fairness

来源：评论

学校读者我要写书评

暂无评论

Mining diverse sets of patterns with constraint programming using the pairwise Jaccard similarity relaxation

引用

constraintS 2024年第1-2期29卷 80-111页

作者： Hien, Arnold Aribi, Noureddine Loudni, Samir Lebbah, Yahia Ouali, Abdelkader Zimmermann, Albrecht Univ Oran 1 Lab LITIO Oran 31000 Algeria IMT Atlantique TASC LS2N CNRS F-44307 Nantes France Normandie Univ CNRS UMR GREYC F-14000 Caen France

In recent years, pattern mining has evolved from a slow-moving, repetitive three-step process to a much more agile and iterative/user-centric mining model. A crucial element of this framework is the capability to rapidly provide a set of diverse patterns to the user. This paper proposes a pattern mining approach based on constraint programming that incorporates a non-redundancy/diversity constraint into closed pattern enumeration. The level of diversity is controlled through a threshold on the maximum pairwise Jaccard similarity of pattern occurrences. We show that the Jaccard measure does not have nice (anti-)monotonicity properties w.r.t. the general-to-specific enumeration. To address this limitation, we propose anti-monotonic lower and upper-bound relaxations of the Jaccard similarity with nice pruning-enabling properties, and connect the final results to the original Jaccard Index. To evaluate the effectiveness of our relaxations, we conduct a comprehensive comparison against several existing pattern mining techniques designed to control redundancy. Experimental results illustrate that our approach provides an effective solution for mining diverse itemsets, showing competitive performance in both runtime and flexibility.

关键词： constraint programming Pairwise Jaccard index Diversity Pattern mining Relaxation

来源：评论

学校读者我要写书评

暂无评论

Solving the integrated process planning and scheduling problem using an enhanced constraint programming-based approach

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2022年第18期60卷 5505-5522页

作者： Shi, Ganquan Yang, Zhouwang Xu, Yang Quan, Yuchen Univ Sci & Technol China Sch Math Sci Hefei Peoples R China Univ Sci & Technol China Sch Data Sci Hefei Peoples R China

Due to various factors of flexibility introduced into manufacturing systems, researchers have gradually shifted their focus to the integrated process planning and scheduling (IPPS) problem to improve productivity. The previous literature rarely associates IPPS with constraint programming, even though constraint programming has achieved success in the scheduling field. Furthermore, existing approaches are usually customized to certain types of IPPS problems and cannot handle the general problem. In this paper, with a view to obtaining the optimal AND/OR graph automatically, a depth first search generating algorithm is designed to convert the type-1 IPPS problem into our approach's standard input format. Moreover, we propose an approach based on enhanced constraint programming to cope with the general problem, employing advanced schemes to enhance the constraint propagation and improve the search efficiency. Our approach is implemented on ORTOOLS, and its superiority is verified by testing on 15 benchmarks with 50 instances. Experimental results indicate that 41 instances are solved optimally, among which the optimality of the solutions for 20 instances is newly confirmed, and the solutions of six instances are improved. Our approach is the first method to reach the overall optimum in the most influential benchmark with 24 instances.

关键词： integrated process planning and scheduling constraint programming AND OR graph graph-based model depth first search

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：