PERT scheduling with convex cost functions.
type: Item
instance of: scholarly article
title: PERT scheduling with convex cost functions.
zbMATH Open document ID: 1059.90066
DOI: 10.1016/S0304-3975(01)00220-1
author: Philippe Chrétienne
author: Francis Sourd
published in: Theoretical Computer Science
publication date: 2003-01-22T00:00:00Z
review text: This paper deals with the problem of finding a minimum cost schedule for a set of dependent activities when a convex cost function is attached to the starting time of each activity. A first optimality necessary and sufficient condition bearing on the head and tail blocks of a schedule is first established. A second such condition that uses the spanning active equality trees of a schedule leads to design a generic algorithm for the general case. When the cost function is the usual earliness--tardiness linear function with assymetric and independent penalty coefficients, the problem is shown to be solved in \(O(n\max\{n,m\})\). Finally, the special cases when the precedence graph is an intree or a family of chains are then also shown to be solved by efficient polynomial algorithms.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 1857216
zbMATH Keywords: Deterministic
zbMATH Keywords: PERT scheduling
zbMATH Keywords: Convex cost functions
zbMATH Keywords: Polynomial algorithm
MaRDI profile type: Publication
cites work: Q4263700
cites work: Q4096964
cites work: Q4396949
cites work: Resource-constrained project scheduling: Notation, classification, models, and methods
cites work: One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: Q4938774
cites work: Optimal timing schedules in earliness-tardiness single machine sequencing
description: scientific article; zbMATH DE number 1857216