Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Shortest path, PERT

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

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)

Gantt Chart: Project Management

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

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

Explores the implications of transforming a shortest path problem into a longest path problem in optimization.

SCION: Next-Generation Internet Security

Presents SCION, a highly secure and efficient next-generation internet architecture with a focus on security and efficiency.

Neural Signals and Connectomes

Explores neural signals, connectomes, graph theory, and multi-voxel pattern analysis in fMRI trials.

Project Management: Planning and Scheduling Log in to Mediaspace to watch this video