Originally posted by: ChWeil

Hi guys,

I have a scheduling problem in which setup times must be included. I modeled them with a transition matrix which works fine. 

One part of the objective function is to minimize the setup costs so setup times are multiplied by a cost factor. Some extractions of my formulation:

int jobs 

int scenarios //scenarios for different processing times of jobs

...

st[j in jobs][k in jobs]=...;//setup times between jobs 

...

tuple triplet { int j, int k, int st };

{triplet} setup = { <j,k,st[j][k]> | j,k in jobs : 0 <= st[j][k]};

....

forall (s in scenarios)

noOverlap (seq[s], setup, 1);

If I just minimize st[j][k] it calculates all combinations in the matrix, but I need the cost only for the transitions in the actual sequence, 

So far I tried to introduce pseudo-types and use a typeOfNext formulation such as st[Typ[j]] [typeOfNext (seq[s], y[s][j], 0,0]. Unfortunately it returns that the model is infeasible because the constraint typeOfNext is always false and the elements in this formulation are out of range, 

Does someone have a solution for my problem? 

Best regards 

Originally posted by: Petr Vilím

Hello,

you're on the right path. Just only one missing piece of puzzle is that function typeOfNext returns value 0 when the interval variable is absent or when it is last (you can parametrize typeOfNext to return other values). So in your setup matrix there must be a cost (probably zero) for going from any state into state 0. If it is missing (e.g. you index normal states from 1) then the problem is indeed infeasible.

You may also have a look at example opl/examples/opl/sched_tcost/sched_tcost.mod in your installation directory. It is using escape vale nbTypes for the case an interval is last. Notice that cost matrix "isLongSetup" includes index nbTypes (unlike matrix used for setup times).

I hope it helps, Petr

Originally posted by: ChWeil

Hi,

Thanks for your reply. It helped to solve the problem. Anyways, I am wondering if there exist any formulation to avoid introducing a new Typ parameter as I do not really need it for my model. 

The formulation costs a lot of extra memory I have the feeling. So if you a suggestion for an easier way to model setup costs I would be glad to hear about it, 

Best regards

Originally posted by: Petr Vilím

Hello,

there is no lighter way to compute setup cost. The same model is recommended for example here (see the bottom of the page):

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cpo.help/CP_Optimizer/User_manual/topics/designsched_costs.html

In your case you may save some memory by using the same matrix for both transition times and computation of setup cost.

Setup cost is often a kind of secondary criteria. For example minimizing makespan also leads to small setups, while makespan is much simpler objective and propagates more. So if you're looking for a lighter model, you may minimize just makespan (or something similar). If setups doesn't look good then, when the search ends, you may use "starting point" feature to further optimize existing solution: replace objective in the model by setup cost, add a constraint that forbids deterioration of original objective and then use current solution as a starting solution for the new search. This second model will be heavy again but most of the work would be already done by the first model.

Best regards, Petr