MPM Buffer Calculation

#!/usr/bin/env python
# -*- coding: utf8 -*-
__author__ = "Jiezheng Zhang"
__copyright__ = "Copyright 2014, Jiezheng Zhang"
__credits__ = ["Jiezheng (Sebastian) Zhang", "Altan Karakul", "Yusuf Azal","Wassilij Mikheyev"]
__license__ = "GPL"
__version__ = "1.0.0"
__email__ = "jiezheng.zhang@gmail.com"

import math,sys
####################################################
#Schritt 1 Input

#Dauer von Vorgänge
D = [0,8,16,36,8,20,20,16,16,16,12,12,12,8,2,0]

#Zmin mit Graph Topologie
#Datentyp 2D Dictionary
#Beispiel
#Definiert z.B. durch  Z = {0:{1:5},1:{}}
#Z[0][1]ist Zmin von Vorgang 0 zu Vorgang 1,gleich 5
#Knote 1 hat kein Nachfolger
Z = {0:{1:0,2:0},
     1:{4:0,5:0,7:0,8:0},
     2:{3:0},
     3:{11:0,12:0},
     4:{6:0},
     5:{11:0},
     6:{12:0},
     7:{9:0},
     8:{10:0},
     9:{7:-34,11:0},
     10:{8:-30,12:0},
     11:{13:0},
     12:{13:0},
     13:{11:-24,12:-24,14:8},
     14:{15:0},
     15:{}
    }

#Max. Projekt Dauer
T = sys.maxint
Debug = True
####################################################
#Schritt 2 Bestimmung von FAZ

#Init

#Queue fuer noch zu bearbeitende Vorgänge
Q = [0]
# early start time
FAZ = [-sys.maxint-1 for x in xrange(len(D))]
FAZ[0] = 0
#invertiere Z zu Vorgaenger Dictionary P
#P[j][i] == Z[i][j]
P={0:{}}
for i in Z:
    for j in Z[i]:
        if not P.has_key(j):
            P[j] = {}
        P[j][i] = Z[i][j]
#FAZ
if Debug:
    print "#Vorwaertsrechnung:"
while Q:
    i = Q.pop(0)
    for j in Z[i]:
        if FAZ[j] < FAZ[i] + D[i]+Z[i][j]:
            FAZ[j] = FAZ[i] + D[i]+Z[i][j]
            if j not in Q:
                Q.append(j)
    #Debug output
    if Debug:
        print "FAZ:","\n", FAZ
        print "Q:","\n", Q


#Logische Fehler bei Projektendtermin entdecken
for i in xrange(len(FAZ)):
    if T < FAZ[i]:
        print "der vorgegebene Projektendtermin ist nicht zu halten"
        sys.exit()

####################################################
#Schritt 3 Bestimmung von SAZ

#Init
if T == sys.maxint:
    T = FAZ[-1]

SAZ = [sys.maxint for x in xrange(len(D))]
SAZ[-1] = T
Q = [len(SAZ)-1]
if Debug:
    print "#Rueckwaertsrechnung:"

while Q:
    i = Q.pop(0)
    for k in P[i]:
        if SAZ[k] > SAZ[i] - D[k]-Z[k][i]:
            SAZ[k] = SAZ[i] - D[k]-Z[k][i]
            if k not in Q:
                Q.append(k)
    #Debug output
    if Debug:
        print "SAZ:",SAZ
        print "Q", Q


####################################################
#Schritt 4 Puffer
FEZ = [0 for x in xrange(len(D))]
SEZ = [0 for x in xrange(len(D))]
GP = [0 for x in xrange(len(D))]
K = []

FP = [0 for x in xrange(len(D))]
FRP = [0 for x in xrange(len(D))]
UP = [0 for x in xrange(len(D))]

for i in xrange(len(D)):
    FEZ[i] = FAZ[i]+D[i]
    SEZ[i] = SAZ[i]+D[i]
    GP[i] = SAZ[i]-FAZ[i]

    if GP[i] == FAZ[0]:
        K.append(True)
    else:
        K.append(False)

    minFAZjMinusZij = None
    FP[i] = - FEZ[i]
    for j in Z[i]:
        if minFAZjMinusZij is not None:
            minFAZjMinusZij = min(minFAZjMinusZij,FAZ[j]-Z[i][j])
        else:
            minFAZjMinusZij = FAZ[j]-Z[i][j]
        FP[i] = minFAZjMinusZij - FEZ[i]

    if minFAZjMinusZij is None:
        minFAZjMinusZij=0


    maxSEZkPlusZkj = None
    FRP[i] = SAZ[i]
    for k in P[i]:
            maxSEZkPlusZkj = max(maxSEZkPlusZkj,SEZ[k]+Z[k][i])
            FRP[i] = SAZ[i]-maxSEZkPlusZkj

    if maxSEZkPlusZkj is None:
        maxSEZkPlusZkj=0
    UP[i]= max(0,minFAZjMinusZij - maxSEZkPlusZkj - D[i])
####################################################
#output

print ("i\tD\tFAZ\tFEZ\tSAZ\tSEZ\tGP\tK\tFP\tFRP\tUP")
for i in xrange(len(FAZ)):
    print "{}\t{}\t{}\t{}\t{}\t{}\t{}\t{}\t{}\t{}\t{}".format(i,D[i],
                                                                FAZ[i],
                                                                FEZ[i],
                                                                SAZ[i],
                                                                SEZ[i],
                                                                GP[i],
                                K[i],                               K[i],
                                                                FP[i],
                                                                FRP[i],
                                                                UP[i]
                                                                )