Lecture

Shortest path, PERT

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture explains the Program Evaluation and Review Technique (PERT) used in project management to determine the minimum project duration and critical tasks. It demonstrates how to model a project as a network and calculate the longest path to identify critical tasks.

In MOOC

Optimization: principles and algorithms - Network and discrete optimization

Introduction to the mathematical concept of networks, and to two important optimization problems on networks: the transshipment problem and the shortest path problem. Short introduction to the modeling power of discrete optimization, with reference to classical problems. Introduction to the branch and bound algorithm, and the concept of cuts.

Official source

Related concepts (12)

Critical path method

The critical path method (CPM), or critical path analysis (CPA), is an algorithm for scheduling a set of project activities. A critical path is determined by identifying the longest stretch of dependent activities and measuring the time required to complete them from start to finish. It is commonly used in conjunction with the program evaluation and review technique (PERT). The CPM is a project-modeling technique developed in the late 1950s by Morgan R. Walker of DuPont and James E. Kelley Jr. of Remington Rand.

Project management

Project management is the process of leading the work of a team to achieve all project goals within the given constraints. This information is usually described in project documentation, created at the beginning of the development process. The primary constraints are scope, time, and budget. The secondary challenge is to optimize the allocation of necessary inputs and apply them to meet pre-defined objectives. The objective of project management is to produce a complete project which complies with the client's objectives.

Project management software

Project management software (PMS) has the capacity to help plan, organize, and manage resource tools and develop resource estimates. Depending on the sophistication of the software, it can manage estimation and planning, scheduling, cost control and budget management, resource allocation, collaboration software, communication, decision-making, quality management, time management and documentation or administration systems. Numerous PC and browser-based project management software and contract management software products and services are available.

Longest path problem

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete.

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.

Related lectures (13)

Project Management: Planning and Scheduling

Covers project management methodologies, network calculation, resource allocation, and monitoring-control in project planning and scheduling.

Gantt Chart: Project Management

Covers the Gantt chart, a tool for optimal project planning and tracking progress.

Project Management Essentials: Scope, Time, and Cost

Covers essential project management aspects like scope, time, and cost, along with resource allocation, schedule optimization, and risk management.

Algorithmic Paradigms for Dynamic Graph Problems

Covers algorithmic paradigms for dynamic graph problems, including dynamic connectivity, expander decomposition, and local clustering, breaking barriers in k-vertex connectivity problems.

Shortest path, Longest path MOOC: Optimization: principles and algorithms - Network and discrete optimization