3
$\begingroup$

I'm building a production scheduling optimization model (but not exactly a jobshop, so I can't just use OR tools). I have decision variables for both the start time of each job, and the duration. For each pair of jobs, there is a changeover time that is unique for the permutation. So for example, changeover from Job A to Job B may be 2 hours, but from Job B to Job A may be 3 hours. I want to add constraints to ensure this changeover. In a nonlinear way, I would describe it as: $$ \mbox{Start}_A + \mbox{Duration}_A + \mbox{Changeover}_{AB} \le \mbox{Start}_B \quad \mbox{if } \mbox{Start}_A \le \mbox{Start}_B \\ \mbox{Start}_B + \mbox{Duration}_B + \mbox{Changeover}_{BA} \le \mbox{Start}_A \quad \mbox{if } \mbox{Start}_B \le \mbox{Start}_A $$ $\mbox{Start}_A$, $\mbox{Start}_B$, $\mbox{Duration}_A$, $\mbox{Duration}_B$ all continuous variables $\ge 0$. $\mbox{Changeover}_{AB}$ and $\mbox{Changeover}_{BA}$ are scalars.

How do I formulate these as constraints? I can either produce Job_A or Job_B first, there's no requirement of order.

Improve this question
$\endgroup$
3
  • $\begingroup$ Can more than one job be in progress at the same time? Is the objective to minimize the makespan? $\endgroup$
    – RobPratt
    Commented Mar 11, 2022 at 22:01
  • $\begingroup$ No, single line and only one job in progress at a single time. Objective function is based upon the relative value of producing (or not) each product on the line, that's why the duration of the jobs are themselves continuous decision variables $\endgroup$
    – Ralph Asher
    Commented Mar 11, 2022 at 22:17
  • $\begingroup$ Why can't you use CP-SAT from OR-Tools ? $\endgroup$
    – Laurent Perron
    Commented Dec 22, 2023 at 14:59

2 Answers 2

Reset to default
6
$\begingroup$

If you let $x_{ij} $ be a binary variable equalling 1 iff job $i$ comes just before job $j$, and continuous variables $u_i$ be the start time of job $i$, then you may model your constraints using MTZ constraints of the form \[ u_i - u_j + s_i + t_{ij} \leq M(1-x_{ij}) \] Here $s_i$ is the processing time of job $i$ and $t_{ij} $ is the change over time from job $i$ to job $j$. $M$ is the smallest large enough number you can think of.

Improve this answer
$\endgroup$
3
  • $\begingroup$ There will also need to be constraints involving the $x_{ij}$ to ensure that every job has exactly one successor (which would be an extra dummy "job" for the last actual job) and every job has exactly one predecessor (which would be another dummy "job" for the first actual job), or something similar, to ensure that $x_{ij} = 1$ exactly when it is supposed to. $\endgroup$
    – prubin ♦
    Commented Mar 11, 2022 at 22:46
  • $\begingroup$ Yes. It's basically a TSP structure with a dummy start job. Maybe you could avoid the dummy "end" job by setting $t_{i, d} =0$ for all actual jobs $i$ and the dummy job $d$? This way you would not "pay" a "change back to start" time $\endgroup$
    – Sune
    Commented Mar 12, 2022 at 10:55
  • 1
    $\begingroup$ Agreed. One dummy job suffices if you turn the schedule into a "loop" a la TSP, with 0 setup time from or to the dummy job. $\endgroup$
    – prubin ♦
    Commented Mar 12, 2022 at 16:50
1
$\begingroup$

I was able to modify @Sune response slightly to get the intended effect.

For every pair of jobs (a,b) in the set of jobs, define constraints:

start_a - start_b + duration_a + changeover_ab <= M*(1 - x_ab)
start_b - start_a + duration_b + changeover_ba <= M*(1 - x_ba)

Where

start_a, start_b, duration_a, duration_b are continuous decision variables

changeover_ab is scalar, the changeover time from job a to job b

changeover_ba is scalar, the changeover time from job b to job a

x_ab, x_ba binary

The key is to make sure x_ab + x_ba = 1, so rewrite the second constraint as:

start_b - start_a + duration_b + changeover_ba <= M*(x_ab)

When running my MILP, the solution's job start times reflect the required minimum changeover times between subsequent jobs.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your solution is only partially correct, since you don’t identify directly following jobs. In or-tools cp-sat solver you can identify closest jobs with circuit constraint. In MILP it can be tricky to identify closest jobs. I don’t know what you mean by or-tools, it is library of various solvers, in case of cp-sat solver you can use same equations as in case of MILP model and much more. $\endgroup$
    – gregy4
    Commented Mar 16, 2022 at 21:52
  • $\begingroup$ The order of the jobs is part of what I want the model to determine based upon the objective function. The way these constraints work out, for every pair of jobs, the time between the conclusion of the first job, and the start of the second job, is AT LEAST as long as the required changeover time. So if I need at least 3 hours between job A and job B, it's acceptable for Job C to be in the middle as long as end_A + 3 <= start_B. These constraints enforce that rule. I already recycled my scrap paper where I tested this out prior to coding, otherwise I'd post $\endgroup$
    – Ralph Asher
    Commented Mar 17, 2022 at 21:21
  • $\begingroup$ In case duration of job C plus changeovers AC and CB are always more than 3 hours (changeover AB) you are right. If not, you should identify following jobs. Maybe you should rename your post since it is not about changeover when another job can be between - instead changeover AB there are changeovers AC and CB, and you say that nonexistent changeover should be respected. $\endgroup$
    – gregy4
    Commented Mar 18, 2022 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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