14 votes
Accepted

Best model for precedence constraints within scheduling problem

Can you change the meaning of your variables? A classic trick when you have a lot of precedences is to use the by formulation. Let $s'_{jt}$ be 1 if job $j$ starts by time $t$ (i.e. at time $t$ or ...
Borelian's user avatar
  • 803
14 votes

How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour

Recognize that each route can be viewed as being a node on a graph. Edges connect nodes if the routes the nodes represent intersect. This is the canonical graph coloring problem for which there are a ...
Richard's user avatar
  • 543
12 votes

Number of aircraft to operate in an airline company

In this document the airline fleet decision process has been categorized in the following bullets: Forecast of expected traffic demand (RPK) Planning average load factor (%) ASK needed to be ...
Oguz Toragay's user avatar
  • 8,622
12 votes
Accepted

How to model a mixed-integer linear programming formulation in Python using Gurobi?

Here is the complete implementation for the above-mentioned model. ...
Mostafa's user avatar
  • 2,086
12 votes
Accepted

Finding minimum time for vehicle to reach to its destination

You can solve this with a mixed integer linear program. It has some similarities to job shop scheduling (with parallel machines) and multiprocessor scheduling, although it is not identical to either. ...
prubin's user avatar
  • 37.8k
11 votes

Best model for precedence constraints within scheduling problem

A straightforward formulation that suffices is to impose conflict constraints of the form $$s_{j_1,t_1}+s_{j_2,t_2}\le 1$$ if $t_1+d_1>t_2$, but you can strengthen that to $$\sum_{t\ge t_1}s_{j_1,t}...
RobPratt's user avatar
  • 30.3k
10 votes

How to implement a "generic" solver for scheduling problems?

As you mentioned about "scheduling/production planning problems", I refer it to manufacturing planning and detailed schedule. Also, I know that there are specific methods to solve other planning and ...
A.Omidi's user avatar
  • 8,382
10 votes

What is the difference bewteen CP and MILP approaches in Job Shop Scheduling?

CP is not a subset of MILP. They are separate modeling/solving paradigms whose domains of application overlap. Both can solve for optimal solutions (in CP's case, by incorporating a constraint that ...
prubin's user avatar
  • 37.8k
9 votes
Accepted

Maximize assigned tasks to each worker

Why quadratic? just use a larger (linear) weight for tasks assigned to worker 1.
Laurent Perron's user avatar
9 votes
Accepted

What is the difference between job shop scheduling and resource constrained project scheduling?

There are three main structural differences between the classic job-shop problem and the classic RCPSP: 1) In the job-shop problem, resource consumption of tasks and capacities of resources (machines)...
Ruslan Sadykov's user avatar
8 votes

Number of aircraft to operate in an airline company

The reason you're not finding anything about this in the literature is that airlines do everything they can to avoid having airplanes in reserve: an airplane on the ground is an airplane that's losing ...
Mark's user avatar
  • 181
8 votes
Accepted

Scheduling problem data generation

It is not ideal, but sometimes I think the best you can do is utilize problem collections from published papers as benchmarks, even if their parameters are rather arbitrary (not necessarily based on ...
prubin's user avatar
  • 37.8k
8 votes

Job shop scheduling advice

It should be possible to model the production process using an integer or mixed-integer linear program. There is a lot of literature out there about MIP models for job shop scheduling. The data would ...
prubin's user avatar
  • 37.8k
8 votes

How to add logical OR constraint in OR-Tools?

Introduce a binary variable $x_{d,s}$ and change the right hand side to $1+2x_{d,s}$.
RobPratt's user avatar
  • 30.3k
8 votes
Accepted

How to minimize the number of breaks in sports scheduling?

If I understood you correctly, you could do it like this (assuming that $n$ is even and $m = n-1$) First, add the binary variables $$ \begin{align} h_{is} &= \begin{cases} 1, &\text{if team $i$...
joni's user avatar
  • 1,477
8 votes
Accepted

Doubles Round Robin Sorting Algorithm

You can solve this with an integer programming model. I will omit the objective function, since any feasible solution produces a viable schedule. You might give some thought to whether there is a ...
prubin's user avatar
  • 37.8k
7 votes
Accepted

Workforce Scheduling problem - Modelling to minimize resources

I assume that each defect requires a specified amount of labor (expressed in worker-hours) to solve, and that each worker contributes one hour of labor for each hour of their shift (no breaks). You ...
prubin's user avatar
  • 37.8k
7 votes

Dealing with non-overlapping constraints

One easy way to convince yourself that this is a non-convex problem - and hence can't be represented without integer constraints, or some other non-convex constraint - is to ask: "If X1 and X2 are ...
GB supports the mod strike's user avatar
7 votes
Accepted

Dealing with non-overlapping constraints

I do not know of any way of handling this without some sort of variable that sorts out whether $i$ begins before $j$ or vice versa. Given the NP-completeness of the underlying problem, you will need ...
Michael Trick's user avatar
7 votes

How to model a mixed-integer linear programming formulation in Python using Gurobi?

Substantively similar to the OP's answer, but with some Python tweaks. Mostly, I just put things in their own functions, tweaked some Gurobi API calls to be cleaner and more efficient, and provided an ...
David M.'s user avatar
  • 2,047
7 votes

How to implement a "generic" solver for scheduling problems?

The "generic" aspect of the solver might just mean that management has, um, inflated expectations. That said, and focusing on the use of metaheuristics, I'll throw out a few ideas. Where possible, ...
prubin's user avatar
  • 37.8k
7 votes

How to implement a "generic" solver for scheduling problems?

Before you even start worrying about algorithms, you need to figure out the solver's architecture. You can do so by posing and answering questions such as the ones I ask below. The answers will be a ...
Nikos Kazazakis's user avatar
7 votes
Accepted

Scheduling events in order to maximize preparation time

If you use a constraint programming (CP) solver, I do not think you will need to convert constraints into algebraic expressions (at least not linear ones). Your first requirement can be handled by an "...
prubin's user avatar
  • 37.8k
7 votes

Gurobi and CPLEX cannot exploit more than 32 cores of machine

You need to distinguish between threads and (physical) cores. Is it possible that the cores you see in your machine are actually just hyperthreads, i.e. 2 cores resemble one physical core? Furthermore,...
mattmilten's user avatar
  • 1,548
7 votes

Gurobi and CPLEX cannot exploit more than 32 cores of machine

Modern CPUs are very complex and have at least two features that limit their scaling capability. The first one is a turbo feature that increases the clock speed when not all cores are utilized. The ...
LinAlg's user avatar
  • 171
7 votes

How to minimize the number of breaks in sports scheduling?

joni's answer is correct. However, this formulation will not allow you to find an optimal solution for anything more than 10-12 teams, even without any additional typical sports scheduling constraints....
Walter Sebastian Gisler's user avatar
7 votes

How to model a non-overlap constraint between 2 groups of tasks?

One simple approach is to impose the classical non-overlap constraints for each pair of tasks for which one task is in $T_1$ and one task is in $T_2$, as shown here.
RobPratt's user avatar
  • 30.3k
7 votes
Accepted

How to model a non-overlap constraint between 2 groups of tasks?

within CPLEX you could try CPOptimizer and use intervals. In OPL (One of CPLEX API) you could write ...
Alex Fleischer's user avatar
6 votes

What is this type of scheduling problem called?

I guess I'm missing something here, or making an incorrect assumption, because the problem seems trivial. I'm assuming that the contribution of each partially done project is a nondecreasing function ...
prubin's user avatar
  • 37.8k
6 votes

How to model a mixed-integer linear programming formulation in Python using Gurobi?

To complete the answer, I will add some other things that may be useful. To change the parameters of the solver gurobi, e.g. setting the time-limit to 600 seconds: ...
Mostafa's user avatar
  • 2,086

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