Originally posted by: ozgur_u

Hi,

I've been trying to fix an error for almost two weeks. I am relatively a long-time user of ILOG products and this is the first time I am not able to fix the problem.

The code attached is for a CP model of a moldable task scheduling problem in which tasks can be processed by more than one machine. I'm giving task to machine assignment, processing times and sort information to the model (aaa.txt).  Until adding transition distances, everything seems fine ; however I cannot reach a solution by getting an help from documentation. Could you please tell me what is my mistake? I urgently need your help. Thanks!

Ozgur

Originally posted by: PhilippeLaborie

Hello,

The model seems to create a long propagation soon after the beginning of the search. I had a look at the model and my feeling is that you probably could formulate the problem in a way that results in stronger propagation in the engine. I see that there are two types of interval variables:

- present interval variables for each task i: CP_taskk[i]

- optional interval variables for each task i / machine j: CP_x[i][j]

What I do not understand is the relation you want to express between those interval variables. In your model there is:

1- a span constraint between CP_taskk[i] and all the optional intervals of task i on machines (all(j ...) CP_x[i][j])

2- constraints CPamountofprocessed[i][j]==IloEndOf(CP_x[i][j])-IloStartOf(CP_x[i][j]))

3- constraints  CPamountofprocessed[i][j]==IloSizeOf(CP_taskk[i])*IloPresenceOf(env,CP_x[i][j])

Constraint 3 seems to suggest that only one machine j can be selected for a given task i. Is it right? If this is the case, you should use an IloAlternative constraint instead of a span constraint in 1. You will just write:

> Alternative(env,CP_taskk[i],disjunctive2[i]);

> Constraints CPamountofprocessed[i][j]==IloLengthOf(CP_x[i][j],0)

The alternative constraint synchronizes the start/end/length of the selected interval variable CP_x[i][j] with the master CP_taskk[i]. And in case CP_x[i][j] is not selected, thus is absent, IloLengthOf(CP_x[i][j],0)=0. But unless used elsewhere, variables CPamountofprocessed[i][j] are not necessary here so the alternative constraint should be enough here.

If the length of the task depends on the selected machine, you can directly constrain the lengthof interval variables CP_x[i][j], for instance: CP_x[i][j].setLengthMin(CP_P[i][j]).

Modeling this type of problem is illustrated in distributed example sched_jobshopflex.cpp (Flexible JobShop Scheduling Problem).

Is it really an alternative selection of machines by tasks that you want to model here or is it something more complex?

Philippe

Originally posted by: ozgur_u

Dear Laborie,

Thank you for the quick reply.

I investigated your suggestions for better modeling. However I think the things that I want to model here are something more complex. The problem here is in my problem a task can be processed by more than one machine simultaneously and the processing size of the task is dependent to the number of machines assigned to it.

I know it may far from being effective but these constraints works for my problem which is quite different than a classical flowshop or any disjunctive scheduling problem in which a task can be processed by one and only one machine simultaneously.

In my model, Constraints 2 and 3 together guarantees all machines assigned to a same task i must process this task simultaneously from start to end.

I don't think any special constraint like "alternative" works here so I'm ok with using the CPamountofprocessed as an auxillary variable to make things work. I have used c++ rather than OPL because I am using this model to calculate fitness values for a genetic algorithm and model is solved optimally even 50 task 5 machines instances within 3 miliseconds.

Ozgur

Originally posted by: PhilippeLaborie

I see. I would then suggest to use an alternative constraint with a cardinality variable. By default the alternative constraint selects a single interval variable but you can specify an additional constant or variable that represents the number of alternatives that can be / have to be selected. This constraint will synchronize the start/end of the selected interval variables with the alternative master and you will be able to write constraints to relate the length of the task with the number of selected machines.

IloAlternative(const IloEnv env, const IloIntervalVar a, const IloIntervalVarArray bs, const IloIntExprArg c, const char * name=0)

An instance of IloAlternative represents an alternative constraint. An alternative constraint between an interval variable a and a set of interval variables {b1,...,bn} models an exclusive alternative between {b1,...,bn}. If interval a is present, then exactly one of intervals {b1,...,bn} is present and a starts and ends together with this specific interval. Interval a is absent if and only if all intervals in {b1,...,bn} are absent.

Additionaly, an alternative constraint can specify a non-negative integer cardinality c. In this case, if interval a is present, it is not 1 but c intervals in the set {b1,...,bn} that will be selected and all these c intervals will have to start and end together with interval a.

Philippe

Originally posted by: ozgur_u

Thanks! Your modeling suggestion leads to a significant improvement

However my initial problem remains the same.

Namely, I am trying to add them between the tasks assigned to the same machine.

My tasks are 1..5 and machines are 1..3
 

const IloInt TaskType[] = { 0,1,2,3,4,5 };

    IloIntervalVarArray2 disjunctive(env,nbMachines+1);

        for (j=1; j<=nbMachines; ++j)
                disjunctive[j]=IloIntervalVarArray(env);
                

//IloIntervalVarArray disj(env);

        for (j=1; j<=nbMachines; ++j)
        for (i=1; i<=nbTasks; ++i)
        disjunctive[j].add(CP_x[i][j]);

    IloIntArray tp(env, nbTasks+1);
    for (i=1; i<=nbTasks; i++)
    {
        IloInt type = TaskType [i];
        tp[i]=type;
    cout<<"tp"<<tp[i]<<endl;
    }

      IloTransitionDistance dist(env, nbTasks+1);
  for (i=1; i<=nbTasks; ++i)
    for (j=1; j<=nbTasks; ++j)
    {
      dist.setValue(i,j,IloAbs(i-j)); // Setup time between types i and j
      cout<<i<<" "<<j<<" "<<dist.getValue(i,j)<<endl;
    }


    IloIntervalSequenceVarArray CP_seq(env,nbMachines+1);

        for (j=1; j<=nbMachines; ++j)
        CP_seq[j]=IloIntervalSequenceVar(env,disjunctive[j],tp);



    for (j=1; j<=nbMachines; j++)
    model.add(IloNoOverlap(env, CP_seq[j],dist,IloTrue));

After adding transition times to the model, c++ code terminates with an error. I tried many things for two weeks, but I cannot find a solution. What's my mistake here?

Originally posted by: PhilippeLaborie

What type of error? Can you attach the full new version of the model?

Philippe

Originally posted by: ozgur_u

Making below replacement seems allows code to work however it's still not clear why this works and I am not that sure that it calculates all transition distances correctly.

   for (i=1; i<=nbTasks; i++)
    {
        IloInt type = TaskType [i];
        tp[i]=type;
    cout<<"tp"<<tp[i]<<endl;
    }

      IloTransitionDistance dist(env, nbTasks+1);
  for (i=1; i<=nbTasks; ++i)
    for (j=1; j<=nbTasks; ++j)
    {
      dist.setValue(i,j,IloAbs(i-j)); // Setup time between types i and j
      cout<<i<<" "<<j<<" "<<dist.getValue(i,j)<<endl;
    }

Originally posted by: ozgur_u

Attached the new version.

Originally posted by: PhilippeLaborie

I think you should either compile your program in DEBUG mode and/or catch and display the exceptions thrown by the program:

try {
  // ... your code
} catch (IloException& e) {
  cout << e << endl;
}

You would see that there are many problems in your code related with some mismatch in the size of arrays and also some uninitialized values at position 0 in the arrays. For instance:
 

* In the definition of the sequence variables, arrays  disjunctive[j] and tp do not have the same size:

CP_seq[j]=IloIntervalSequenceVar(env, disjunctive[j],tp);

disjunctive[j] is of size nbTasks
tp is of size nbTasks+1

* tp[0] is not initialized:

IloIntArray tp(env, nbTasks);
for (i=1; i<=nbTasks; i++) {
  IloInt type = TaskType [i];
    tp[i]=type;
    cout<<"tp"<<tp[i]<<endl;
}

There are several other arrays for which the first element (index 0) does not seem to be initialized.

Philipppe

Originally posted by: ozgur_u

Dear Philippe,

Thanks a lot! I solved the problem, which is caused by "arrays  disjunctive[j] and tp do not have the same size".

Ozgur