Originally posted by: andrei.zaharia

Hi

 

   I am trying to model a business case but i'm having some difficulties.

The simplified business case: We have a fix number of flight (with caracteristics) that must be allocated to a number of resources (ex.: all arrival flights in a given period of time must be allocated to arrival gates). For each flight we know the time it occupies a gate.

The allocation must tell us how many gates we need to process all the flights and the beginning and end occupation time for each flight.

 

The flights are defined as a tuple and we get from the data file the set of flights:

int nbFlights = ...;

tuple Flight {
  int id;
  string flightCategory;
  int occupationTime;
};

{Flight} flights = ...;

Each flight has an earliest start of processing calculated based on its arrival time:

int earliestStartOfProcessing [flights] = ...;

The resources are also as a tuple:

tuple Resource {
  int id;
  string name;
  int maxUtilizationTime;
}
Since we need the start/end occupation time for each flight assigned to a resource i declared the decision variable:

dvar interval itvs[r in resources, f in flights];

and the usage for each resource:

cumulFunction usage[r in resources] = sum (f in flights) pulse(itvs[r][f], f.occupationTime);

The objective would be to minimize the resources used. We can say equivalently that we need for each resource to maximize the usage (maximize the number of occupied time).

I am not sure how to model the objective.  Any help would be appreciated.

 

Example of the data file:

nbFlights = 3;

flights = {
<1, "DOM", 10>,
<2, "INT", 30>,
<3, "SCH", 20>
};
earliestStartOfProcessing = [0, 5, 10];

 

Thank you,

Andrei

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: ol

Hello,

A first remark, in:

  cumulFunction usage[r in resources] = sum (f in flights) pulse(itvs[r][f], f.occupationTime);

The second parameter of pulse is its height, not its length. The length of the pulse is given by the interval variable, which should be defined with what you call occupationTime. Then this line of code is probably not what you have in mind.

Anyway, for allocating flights to gates, maybe you will find useful the alternative contraint.
see the documentation at
http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.cpo.help/refcppcpoptimizer/html/constraints_groups.html?lang=en
It seems to match well what I suspect you want to do, by defining itvs[r][f] as optional.

As for the objective:
if all the flights needs to be allocated to gates, as their arrivals and departures are known, the sum of the occupation times of all the gates is also known and constant, so nothing to optimize there.
Instead, you may want to minimize the number of used gates. In this case, assuming all the gates are equivalent, you can force all the used gates to have an id less than a variable k, and minimize k. This can be done with the presence of intervals, and "span constraints" to express the activity period of a gate.
 
Regards,
Olivier

#DecisionOptimization
#OPLusingCPOptimizer