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$
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.

$\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
3
$\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.

New contributor
Petr Vilím is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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

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.