7
$\begingroup$

I can not seem to find the needed functions to model the following problem through the Java API (CP Optimizer): a machine that has downtime and sequence-dependent setup times, with the extra constraint, that the physical preparation (setup) of a job ends right before the job starts.

Since there are no preemptions, I am using IloIntervalSequenceVar (with a noOverlap that contains the setup time matrix) and IloNumToNumStepFunction for downtimes. This leads to solutions in which a job can start right after a downtime, because the downtime offers enough distance for the transition time to take place (or at least a part of it). The problem is that this transition itself is also an activity, so it is illegal for it to overlap with downtime.

Next, I tried modeling the setup times and/or downtimes as intervals themselves, which solves the overlap problem. However, I always bump into the same problem: it is possible to access intervals and their properties after the model has been solved, but not when formulating decision variables. Since setup times are sequence-dependent, I want to assign a certain size to a setup interval, based on its predecessor (its successor is implied through the constraint I mentioned earlier). I have no way of retrieving this. Methods such as getPrev are Native, methods such as prev are Constraints. I basically want a Boolean matrix for each setup interval so I can assign the correct size to it based on the setup time matrix, but I can not find any method that provides this. I can think of ways without modeling setups as intervals, using extra constraints, but they need this same functionality.

What do I oversee, is there a better way to go about this?

Thanks in advance.

Edit for clarification with $A$, $B$, $\rm Setup$ and $\rm Downtime$ being intervals, $A$ being the last job before $B$:

\begin{align}{\rm End}(A) + |{\rm{Setup}}(A,B)| &\leq {\rm Start}(B)\\{\rm End}({\rm Setup}(A,B)) &= {\rm Start}(B)\\{\rm Downtime} \cap (A \cup {\rm Setup}(A,B) \cup B)&= \emptyset\end{align}

Which propagates the following constraint I am trying to model as such:

\begin{align}&{\rm Start}({\rm Downtime}) - {\rm End}(A) < |{\rm Setup}(A,B)| + |B|\\\implies&{\rm End}({\rm Downtime}) + |{\rm Setup}(A,B)| \leq {\rm Start}(B) \end{align}

$\endgroup$
4
$\begingroup$

I think that you're looking for function IloCP::typeOfPrev. Its documentation is for example here, the description of the general concept is here.

Basically, each interval participating in sequence variable can have a type. By default each interval has different type counted from 0 in the order as they are specified in the sequence variable. So type of the previous interval is the index into the array that was used to create the sequence variable.

Note that IloCP::typeOfPrev returns an expression, not a constant. That's because the value is not known, it depends on the particular solution. There are also similar functions, e.g. IloCP::endOfPrev.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks for giving authoritative answers to questions here.Because you are providing answers regarding IBM products, you might want to add to your profile that you are an IBM employee. $\endgroup$ – Mark L. Stone Jan 21 at 20:34
  • $\begingroup$ Why is there no straight access to π(a), using for instance IloCP::typeOf? When checking the position before an interval, I don't yet know what interval is at that position. So to detect whether itv a comes right before itv b, one of the contructions I can think about is prev(a) == prev(b) - 1, creating annoying bound conditions. For now, I get -1 as return value (and I can't seem to find what's wrong), but your answer should fix it once I figure out my mistake. Thanks. $\endgroup$ – Maarten Mar 1 at 14:21
  • $\begingroup$ Yes, there is no direct access to π(a) during the modeling. The main reason is that it is not the way the solver works internally. The advantage of expressions such as typeOfPrev is that they can propagate even if position in the sequence is still unknown.The idea is that usually it is not important what interval is before in particular but what are the properties of the previous interval. And those are accessible by typeOfPrev, endOfPrev, lengthOfPrev and sizeOfPrev. Note that there are optional arguments for the case the interval is first or absent. $\endgroup$ – Petr Vilím Mar 1 at 17:44
3
$\begingroup$

I'm not a CP Optimizer user, so this may be clunkier than necessary (by an order of magnitude). I'm going to assume that your setup times satisfy the triangle inequality (meaning it's faster to go straight from A to B than from A to C to B).

For each place where you would use an interval variable for down time, you could instead create multiple interval variables, one for each possible state the machine might be in either when it went down or when it came up (i.e., the state of the last job before it went down or the first job after it came up -- I'm being intentionally vague about which). You would make those variables optional (IloIntervalVar.setOptional()) and tell the model that exactly one must be present (IloCP.alternative()). Then give them noOverlaps with all possible preceding and following intervals using the appropriate setup times. If the schedule contains a sequence "job A" -- down -- "job B", then one of three things will happen. If the solver chooses an "A flavor" of the downtime variable, you'll pay the A-B setup when downtime ends. If it chooses a "B flavor" downtime variable, you'll pay the A-B setup when downtime begins. If it chooses the "C flavor", you'll pay both an A-C and a C-B setup cost, which via the triangle inequality is no better than A-B. So, in this case, the solver might have some unintentional inserted slack in the schedule ... but that should only happen if it does not affect the optimal solution.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Sure, although the only acceptable option is a downtime mimicking its predecessor with respect to its successor (or a type that causes no shorter setups for that matter). Even with triangle inequality satisfaction, C-B might be faster than A-B, and that's the flavour I would go for as a solver (since the objective is to minimise tardiness). After the last job before a downtime finishes, the machine remains untouched until that same downtime is finished. Only then, a setup from A to B is in good taste. $\endgroup$ – Maarten Oct 26 '19 at 0:40
  • $\begingroup$ I should clarify that a downtime need not be contiguous with the job before, which makes it possible that an alleged transition between A and a C flavour does not always 'push' a downtime to the right. $\endgroup$ – Maarten Oct 26 '19 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.