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

Polyhedral reformulation of a scheduling problem and related theoretical results

RAIRO-OPERATIONS RESEARCH 2008年第3期42卷 325-359页

作者： Damay, Jean Quilliot, Alain Sanlaville, Eric Univ Blaise Pascal CNRS UMR 6158 LIMOS F-63173 Aubiere France

We deal here with a scheduling problem GPPCSP (Generalized Parallelism and Preemption constrained scheduling problem) which is an extension of both the well-known resource constrained scheduling problem and the scheduling problem with Disjunctive Constraints. We first propose a reformulation of GPPCSP: according to it, solving GPPCSP means finding a vertex of the Feasible Vertex Subset of an Antichain Polyhedron. Next, we state several theoretical results related to this reformulation process and to structural properties of this specific Feasible Vertex Subset (connectivity,...). We end by focusing on the preemptive case of GPPCSP and by identifying specific instances of GPPCSP which are such that any vertex of the related Antichain Polyhedron may be projected on its related Feasible Vertex Subset without any deterioration of the makespan. For such an instance, the GPPCSP problem may be solved in a simple way through linear programming.

关键词： partially ordered sets hypergraphs linear programming polyhedra multiprocessor scheduling resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Pattern mining-based pruning strategies in stochastic local searches for scheduling problems

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2022年第5期29卷 2815-2840页

作者： Laurent, Arnaud Lamy, Damien Dalmas, Benjamin Clerc, Vincent INRIA Lille France Univ Clermont Auvergne CNRS UMR 6158 LIMOSInst Henri FayolMines St Etienne F-42023 St Etienne France Univ Clermont Auvergne CNRS UMR 6158 LIMOSCtr CISMines St Etienne F-42023 St Etienne France

scheduling problems are a subclass of combinatorial problems consisting of a set of tasks/activities/jobs to be processed by a set of resources usually to minimize a time criterion. Some optimization methods used to solve these problems are hybridized with knowledge discovery techniques to extract information during the optimization process and enhance it. However, most of these hybrid techniques are custom-designed and lack generalization. In this paper, a module for knowledge extraction in Stochastic Local Searches is designed, aiming to be problem independent and plugged into optimization methods that relies on multiple Stochastic Local Search replications. The objective is to prune parts of the search space for which the exploration is likely to lead to poor solutions. This is performed through the extraction of high-quality patterns occurring in locally optimal solutions. Benchmarked on two well-known scheduling problems, the Job-shop problem and the resource constrained project scheduling problem, the results show both a speed up in the convergence and the reaching of better local optima solutions.

关键词： stochastic local search pattern mining machine learning scheduling problem job‐ shop resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Investigating constraint programming and hybrid methods for real world industrial test laboratory scheduling

引用

JOURNAL OF scheduling 2024年第6期27卷 607-622页

作者： Geibinger, Tobias Mischek, Florian Musliu, Nysret TU Wien Christian Doppler Lab Artificial Intelligence & Op Databases & Artificial Intelligence Grp Favoritenstr 9-11 A-1040 Vienna Austria

In this paper we deal with a complex real world scheduling problem closely related to the well-known resource-constrained project scheduling problem (RCPSP). The problem concerns industrial test laboratories in which a large number of tests are performed by qualified personnel using specialised equipment, while respecting deadlines and other constraints. We present different constraint programming models and search strategies for this problem. Furthermore, we propose a Very Large Neighborhood Search approach based on our CP methods. Our models are evaluated using CP solvers and a MIP solver both on real-world test laboratory data and on a set of generated instances of different sizes based on the real-world data. Further, we compare the exact approaches with VLNS and a Simulated Annealing heuristic. We could find feasible solutions for all instances and several optimal solutions and we show that using VLNS we can improve upon the results of the other approaches.

关键词： RCPSP resource constrained project scheduling problem project scheduling Constraint programming VLNS Very large neighborhood search

来源：评论

学校读者我要写书评

暂无评论

resource constrained project scheduling formulation for optimization of product input sequence and workforce scheduling for multi-stage multi-product cellular production lines

引用

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING 2024年第5期18卷

作者： Nishi, Tatsushi Kurakado, Hidefumi Liu, Ziang Okayama Univ Grad Sch Environm Life Nat Sci & Technol 3-1-1 Tsushima NakaKita Ku Okayama Okayama 7008530 Japan

The workforce scheduling problem for cell production lines has been recognized as one of the significant issues in manufacturing systems. In most of previous studies, complex workers' operations in a cell such as traveling times of multi-skilled operators in another cell to their workplaces, have not been considered in the workforce optimization model. In this paper, we consider the simultaneous optimization of the product input sequence and workforce assignment scheduling problem for multi-stage multi-item cell production lines. The problem is formulated as a resource-constrained project scheduling problem (RCPSP). We propose an RCPSP formulation of the scheduling problem for multi-product cell production lines where the traveling time of operators and products are considered. The exact solution of the RCPSP formulation is derived by using a general-purpose solver, Gurobi. The validity of the RCPSP model is verified by comparing it with a genetic algorithm (GA) using a commercial simulation software (Siemens Plant Simulation). Experimental results show that the derived exact solution of RCPSP is better than that of the solutions derived by the GA algorithm in the Siemens Plant Simulation.

关键词： Multi-product cellular production resource constrained project scheduling problem Workforce scheduling

来源：评论

学校读者我要写书评

暂无评论

A New Algorithm for resource Constraint project scheduling problem Based on Multi-Agent Systems

引用

Transactions of Tianjin University 2003年第4期9卷 348-352页

作者：何曙光齐二石李钢 School of Management

The resource constrained project scheduling problem (RCPSP) and a decision-making model based on multi-agent systems (MAS) and general equilibrium marketing are proposed. An algorithm leading to the resource allocation decision involved in RCPSP has also been developed. And this algorithm can be used in the multi-project scheduling field as ***, an illustration is given.

关键词： resource constrained project scheduling problem multi-agent systems general equilibrium market algorithm

来源：评论

学校读者我要写书评

暂无评论

A Critical Chain project scheduling problem with Multi-mode

A Critical Chain Project Scheduling Problem with Multi-mode

引用

14th International Manufacturing Conference in China

作者： Peng, W. L. Jiao, Q. J. Shenyang Ligong Univ Sch Econ & Management Shenyang Peoples R China

ISBN: (纸本)9783037852378

Critical chain method (CCM) is a new project method which combines project network technologies and management arts. Although there are lots of researches on it, the existing critical chain method has some drawbacks limiting its decision level in practical application. To improve the decision level and application range of critical chain method, the critical chain method with multi-mode is studied. The project network technology is the foundation of project scheduling problem. All the existing project management tools can only support single mode project network, that is, all the project activities have only one executive mode. We study the multi-mode project network as the foundation of multi-mode CC. Furthermore, by relating multi-mode project network to critical chain method, the critical chain method with multi-mode is presented, and the implementation procedure is proposed. In the implementation of multi-mode CCM, the activity priority rules and mode priority rules are investigated.

关键词： project management Critical chain resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

A Genetic Algorithm for Solving RCPSP

A Genetic Algorithm for Solving RCPSP

引用

International Symposium on Computer Science and Computational Technology

作者： Zhang, Hua Xu, Hao Peng, Wuliang Shenyang Ligong Univ Sch Mech Engn Shenyang Peoples R China Shenyang Ligong Univ Sch Econ & Management Shenyang Peoples R China

ISBN: (纸本)9780769534985

A genetic algorithm (GA) was proposed to solve the resource constrained project scheduling problem(RCPSP), in which resources are renewable and there is a single mode to perform each activity. This work employed genetic algorithms to schedule project activities to minimize make-span subject to precedence constraints and resources availability. In the genetic algorithm, a new permutation of priority-based encoding scheme was designed in the algorithm, and it inherits all the merits of both the permutation-based encoding scheme and the priority-based encoding scheme. The serial generation scheme was used in decoding scheme to generate project plan. A full factorial computational experiment was set up using the well-known standard instances in PSPLIB, and the algorithm given in this paper was compared with the existing intelligent optimization algorithms, the results reveal that the algorithm is effective for the RCPSP.

关键词： genetic algorithm project scheduling resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

An ACO for Solving RCPSP

An ACO for Solving RCPSP

引用

International Symposium on Computer Science and Computational Technology

作者： Zhou, Li Wang, Dong Peng, Wuliang Shenyang Ligong Univ Sch Mech Engn Shenyang Peoples R China Shenyang Ligong Univ Sch Econ & Management Shenyang Peoples R China

ISBN: (纸本)9780769534985

An improved ant colony optimization (ACO) was developed based on the characteristics of resource-constrained project scheduling problem (RCPSP). In the algorithm, a new permutation of priorities-based encoding scheme is employed, and the summation evaluation is applied to direct the moving of ants. The priority rule pool, in which lots of priority rules can be managed, is presented to strengthen the learning ability and adaptability of ACO. Taking full advantage of ACO, each ant is provided a single thread and the algorithm is realized in the multithreading architecture. A full factorial computational experiment is set up using the well-known standard instances in PSPLIB, and the algorithm given in this paper is compared to the existing swarm intelligence optimization algorithms, the results reveal that the algorithm is effective for the RCPSP.

关键词： ant colony optimization, project scheduling resource constrained project scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Multi-Mode RCPSP with Safety Margin Maximization: Models and Algorithms 10th

Multi-Mode RCPSP with Safety Margin Maximization: Models and...

引用

10th International Conference on Operations Research and Enterprise Systems (ICORES)

作者： Artigues, Christian Hebrard, Emmanuel Quilliot, Alain Toussaint, Helene CNRS LAAS Lab Toulouse France CNRS LIMOS Lab Clermont Ferrand France

ISBN: (纸本)9789897584855

We study here a variant of the multimode resource constrained project scheduling problem (RCPSP), which involves continuous modes, and a notion of Safety Margin maximization. Our interest was motivated by a work package inside the GEOSAFE H2020 project, devoted to the design of evacuation plans in face of natural disasters, and more specifically wildfire.

关键词： scheduling resource constrained project scheduling problem Evacuation Process Network Flow Branch and Bound Linear Programming

来源：评论

学校读者我要写书评

暂无评论

Memetic Algorithm for Heterogeneous project scheduling problems

Memetic Algorithm for Heterogeneous Project Scheduling Probl...

引用

IEEE Symposium Series on Computational Intelligence (IEEE SSCI)

作者： Mahmud, Firoz Zaman, Forhad Sarker, Ruhul Essam, Daryl Univ New South Wales Sch Engn & Informat Technol Canberra ACT Australia

ISBN: (纸本)9781728125473

resource-constrained project scheduling problem (RCPSP) is a well-known challenging optimization problem. Over the last few decades, many different approaches have been proposed for solving different variant of RCPSPs. In those problems, it is usually assumed that the activities are homogeneous, that means, all activities are similar or they require similar types of resource over the entire project horizon. However, in real-world applications, a project consists of heterogeneous activities where the activities really need different kinds of resource. The existing algorithms, which are mostly developed for RCPSPs with homogeneous activities, can be applied to the projects with heterogeneous activities with a simple modification. However, they are computationally expensive as they need to perform many unnecessary computation. So, in this paper, we propose a customized approach for RCPSPs with heterogeneous activities based on a memetic algorithm. The proposed memetic algorithm is basically a genetic algorithm combined with a local search. The performance of the propose algorithm has been tested by solving a good number of problem instances and a few real-world problems, and comparing the results with an appropriate state-of-the-art algorithm. It is found that propose approach obtains high quality solutions within a considerably lower computational effort.

关键词： resource constrained project scheduling problem Heterogeneous activities Genetic Algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：