๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Worst-case performance of critical path type algorithms

โœ Scribed by G. Singh; Y. Zinder

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
343 KB
Volume
7
Category
Article
ISSN
0969-6016

No coin nor oath required. For personal study only.

โœฆ Synopsis

The critical path method remains one of the most popular approaches in practical scheduling. Being developed for the makespan problem this method can also be generalized to the maximum lateness problem. For the unit execution time task system and parallel processors this generalization is known as the BruckerยฑGareyยฑJohnson algorithm. We characterize this algorithm by introducing an upper bound on the deviation of the criterion from its optimal value. The bound is stated in terms of parameters characterizing the problem, namely number of processors, the length of the longest path, and the total required processing time. We also derive a similar bound for the preemptive version of the Bruckerยฑ GareyยฑJohnson algorithm.

๐Ÿ“œ SIMILAR VOLUMES

Worst-case performance of approximation
Worst-case performance of approximation algorithms for tool management problems
โœ Yves Crama; Joris van de Klundert ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 122 KB ๐Ÿ‘ 2 views

Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so-called tool management problems appear to b

A New Algorithm and Worst Case Complexit
A New Algorithm and Worst Case Complexity for Feynmanโ€“Kac Path Integration
โœ Leszek Plaskota; Grzegorz W. Wasilkowski; Henryk Woลบniakowski ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 121 KB

We study algorithms for approximation of Feynman-Kac path integrals in the worst case setting. The algorithms use a finite number of samples of the initial condition and potential functions. We present a new algorithm and an explicit bound on its cost to compute an ฮต-approximation to the Feynman-Kac