סמינר מחלקתי

Efficient algorithms for the time cost tradeoff problem
Dorit S. Hochbaum
UC Berkeley

Abstract :

The time cost tradeoff problem in project management, TCT, is to expedite the durations of activities in order to achieve shorter target project completion time than possible with the normal durations.  The linear TCT problem, in which the expediting costs of each activity are linear as a function of the number of time periods reduced,  is commonly solved using linear programming.  We present here an algorithm, based on a non-polynomial time algorithm by Phillips and Dessouky 1977, PD-algorithm.   PD-algorithm repeats iterations in each of which the project duration is reduced by one time unit, at a minimum cost.  The activities to expedite, in order to reduce the project duration by one unit, correspond to forward and backward arcs, that reside on a minimum cut in a respective graph.

We present here previously unknown properties of PD algorithm and use these properties to devise a variant of PD-algorithm and that runs in polynomial time for both linear and convex expediting costs and uses a minimum s,t-cut routine at each iteration.

For the uniform costs TCT problem we present here a new algorithm that runs in O(mn) for a project network on n activities and m precedence constraints.    The key building block of this algorithm is the generation of all optimal minimum cuts simultaneously, in the same complexity as a single minimum cut.  We discuss the implications of this algorithm for maximum weight flow problem with unit capacities.

Time permitting, we will show a dual algorithm for TCT, that solves the problem in time O(n log n (m + n \log n).

ההרצאה תתקיים ביום שלישי 09/06/15, בשעה 13:00 בחדר 206, בנין וולפסון הנדסה, הפקולטה להנדסה, אוניברסיטת תל-אביב