Skip to main content
5 votes
Accepted

Replace the constraint using ==> by a linear formulation

You want to enforce the logical implication $$t \le \text{Fin}[j] \implies \text{Act}[j,t] \ge \text{Act}[j,t-1]$$ Equivalently, the contrapositive is $$\text{Act}[j,t] < \text{Act}[j,t-1] \implies ...
RobPratt's user avatar
  • 32.3k
4 votes
Accepted

Scheduling to minimize total "wait to start" time

I recommend using your second formulation with $np$ binary assignment variables and $n$ continuous start variables. To prevent overlapping tasks for the same worker, impose a linear disjunction for ...
RobPratt's user avatar
  • 32.3k
4 votes
Accepted

Can dynamic programming find globally optimal solutions for scheduling problems

Assuming your state space is discrete (for instance, there are finitely many possible charge levels for the vehicle), and assuming that how much you pay for charging depends on the amount of charging ...
prubin's user avatar
  • 39.3k
4 votes

How to model weekend constraints in a nurse rostering problem?

You want to enforce $$(y_{i,6} \land y_{i,7} \land \lnot y_{i,13} \land \lnot y_{i,14}) \lor (\lnot y_{i,6} \land \lnot y_{i,7} \land y_{i,13} \land y_{i,14}).$$ Rewriting in conjunctive normal form ...
RobPratt's user avatar
  • 32.3k
3 votes

How to modify a model to be cyclic?

If you want to enforce that $x_{i,t,j}=x_{i,t+28,j}$, you can explicitly impose that constraint and let the presolver do the substitution. Or omit the explicit constraints and do the substitution ...
RobPratt's user avatar
  • 32.3k
3 votes
Accepted

Compute overlapping time

First note that you can omit $t_{ij}$ for any pair $(i,j)$ for which the time windows do not overlap because $t_{ij}=0$ in that case. Tasks $i$ and $j$ overlap if and only if the later starting time $\...
RobPratt's user avatar
  • 32.3k
3 votes
Accepted

Formulation for choosing how many items to manufacture

If you need both $x$ and $y$ in the model, a third option is to enforce \begin{align} y_{m,p,s} &\ge x_{m,p,s} \\ y_{m,p,s} &\le \text{PartsPerShift}_p x_{m,p,s} \end{align} This modification ...
RobPratt's user avatar
  • 32.3k
3 votes
Accepted

How to fill the days in sequence?

You want to enforce $h_i > 0 \implies h_{i-1} = 8$. You can do so by introducing binary variables $x_i$ and the following constraints: \begin{align} h_i > 0 &\implies x_i = 1 \\ x_i = 1 &...
RobPratt's user avatar
  • 32.3k
2 votes

Scheduling to minimize total "wait to start" time

Based on what you mentioned, something should be considered. First, your problem falls in the class of parallel machine scheduling problems. There are $n$ tasks that should be processed by $p$ ...
A.Omidi's user avatar
  • 8,950
2 votes

Machine Scheduling with simultaneous processing of jobs

The keyword is "resource constrained scheduling problem". Here is a book chapter about the classical mixed-integer programming models for the standard version of the problem: Artigues, ...
fontanf's user avatar
  • 2,623
2 votes

Best known results on the flexible jobshop benchmarks

The recent FJSP overview paper by Dauzère-Pérès et al. (2024) has a list of best-known solutions for classical FJSP instances in their supplementary materials. However, they did not include results ...
Leon Lan's user avatar
  • 185
2 votes
Accepted

Meaning of the domain propagation in the context of mixed-integer programming

Overview I think the canonical resource to this topic is: Achterberg, Tobias. Constraint integer programming. Diss. 2007. Example Code As this basiclly describes the theory behind the open-source ...
sascha's user avatar
  • 517
2 votes

Best algorithm for scheduling interviews

You can model your problem as ILP and implement it e.g., in Pythons PuLP library and solve it with commercial solvers (e.g., GUROBI or CPLEX) or non-commercial solvers such as COIN-OR. However, you ...
PeterD's user avatar
  • 1,626
2 votes

Is this classed as a version of jobshop? How should it be approached?

It's definitely a job-shop variant. Usually we use the terms "release time" and "deadline". See the job characteristics list here: https://en.wikipedia.org/wiki/...
Brannon's user avatar
  • 900
2 votes

How to combine MIP solver with a CP one?

General Many works combining MILP and CP are what's sometimes called logic-based benders decomposition and there is even a book on the topic: Hooker, John. "Logic-Based Benders Decomposition: ...
sascha's user avatar
  • 517
2 votes
Accepted

How to combine MIP solver with a CP one?

I think they actually state it very clearly in the paper in the part they call Algorithm 3. IP/CP: solve a relaxation of the original and then generate no-good cuts that remove infeasible solution. In ...
Sune's user avatar
  • 6,552
2 votes
Accepted

Workforce scheduling problem

Consider a side-constrained network formulation in which you have a node for each employee-day-shift and a directed arc if the employees are the same, the days are consecutive, and the shifts do not ...
RobPratt's user avatar
  • 32.3k
2 votes

Scheduling & Routing Problem

One possibility might be to start by constructing feasible one-day schedules for techs (service just A, service A and B in some order, service A, B and C in that order, ...). The MILP model would then ...
prubin's user avatar
  • 39.3k
2 votes

Problem 8.17 of Korte and Vygen

Hints: This exercise comes from a chapter on network flow. Source and sink Directed arcs Split node $i$ and replace with arc from $i$ to $i’$ with lower bound $1$. Minimize cost. A few links that ...
RobPratt's user avatar
  • 32.3k
2 votes

multiple shifts per day constraint for a workforce scheduling problem

For the requirement that the roles performed by a single worker in a day must be distinct, here are two alternative approaches. One way is to augment the node definitions to include all roles that ...
RobPratt's user avatar
  • 32.3k
1 vote

Scheduling optimization problem - Where to begin?

Track 2 in the International Timetabling Competition 2007 was similar if I recall correctly: Post Enrollment based Course Timetabling. You might be able to find some papers around that. I've heard ...
Geoffrey De Smet's user avatar
1 vote

Workforce scheduling problem difficulty

You could run a solver for a short time, to evaluate the score of that output on feasibility (broken hard constraints) or unassigned shifts, but even that will take solving time. In practice, when ...
Geoffrey De Smet's user avatar
1 vote

Problem 8.17 of Korte and Vygen

This could be seen as a graph coloring problem. The nodes are the possible flights. Draw an edge between two nodes if they are incompatible (how would they be incompatible?) Then find an optimal ...
jot240's user avatar
  • 31
1 vote

Circular queue modeling

$0 \le x_{p,d} \le T' \quad \forall p \in P \ \forall d \le T$. $d$ is the index of slots covering required duration of each job as in column $T$. For e.g. for job $1$ d.v. will be $x_{1,1},x_{1,2},x_{...
Sutanu Majumdar's user avatar
1 vote
Accepted

Compute time between tasks

What you could do is the following: Introduce variable $t_{ij}$ that is the time between tasks $i$ and $j$. This variable is only defined for once per pair $ij$, therefore the $j >i$. Then, you can ...
PeterD's user avatar
  • 1,626
1 vote

Mixed-Integer Programming Model for Scheduling with Dynamic Jobs

To determine the number of AGVs in your production system, their working procedure should be exploded first based on the following states: $$ \{ \text{Idle time, empty travel time, loading time, ...
A.Omidi's user avatar
  • 8,950
1 vote
Accepted

How to define the sequence depending setup time based on a time index formulation

Here is a way to model sequence-dependent setup times for a time-indexed formulation: $$ \forall j, j' \in J, j \neq j' \quad \forall m \in M, \quad \forall t \in T, \qquad x_{j, m, t} + \sum_{t' = t +...
fontanf's user avatar
  • 2,623
1 vote

Scheduling repeated tasks with minimum duty cycles

The repeating time frame is called cyclic scheduling. The max distance between tasks is called max delay. CP-SAT is a good tool to model it. You will need to use interval variables, the no_overlap ...
Laurent Perron's user avatar
1 vote

How to fill the days in sequence?

$ -20x_i \le 20-\sum_{d}^{i-1} h_d - 8 \le 20(1-x_i)$ $ 8(1-x_i) \le h_i \le 20-\sum_{d}^{i-1} h_d $ where $x_i$ is a binary
Sutanu Majumdar's user avatar
1 vote

How to fill the days in sequence?

If the work load can be discretized, you could model this like a bin packing problem. If the time granularity is for example the hour, let $x_{ij}$ be a binary variable that takes value $1$ if and ...
Kuifje's user avatar
  • 13.5k

Only top scored, non community-wiki answers of a minimum length are eligible