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

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.