[Help-glpk] Help regarding expressing a constraint for a scheduling prob.

[gaurav khanna]

Hi all,

I am trying to solve the following problem using 0-1 IP. I have a graph
which represents a set of processing nodes connected via varying bandwidth
links. I have a set of files of possibly different sizes and each file has
an associated source and destination. All files are initally present on
their respective source nodes. The files need to be sent to their
respective destinations using a store and forward model where the file is
stored on every node on way to its destination and there is edge
contention as well as node contention. The goal is to minimize
the overall finish time of all these file transfers that is to minimize
the makespan. I have introduced the following two sets of 0-1 variables in
my formulation.

TR_{fijt} - which is 1 if file f is being transferred from node i to
adjacent node j during time [t-1,t].

STORED_{fit} - which is 1 file f is present on node i at time t. This
also means that if a file f is present on a node i at time t, then it
stays present on that node at all later times.

Here f varies from 1 - #files to be transferred
     i,j varies from 1 to #nodes in the graph
     t varies from 0 to upper bound on the overall finish time which I have 
calculated separately.

The goal is defined using a variable OBJ which is the overall finish time.

I have been able to express most of the constraints using these variables.
However, I am having trouble expressing one constraint.

I need to say that the transfer completion time of each file transfer
should be less than OBJ.
Now the transfer completion time of a file f is the earliest time t when
it becomes present at its destination d. Basically , i am looking for
the earliest time t such that STORED_{fdt}=1. Then I need to say that this
t is less than or equal to OBJ.

Is there a way to do this ?

Regards
Gaurav


Gaurav Khanna
Phd Student
CSE Department,OSU

Phone (office):614-292-7036