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 ...
- 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 ...
- 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 ...
- 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.
...
- 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. ...
- 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}...
- 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 ...
- 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 ...
- 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.
- 2,587
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)...
- 1,394
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 ...
- 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 ...
- 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 ...
- 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}$.
- 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$...
- 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 ...
- 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 ...
- 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 ...
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 ...
- 2,362
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 ...
- 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, ...
- 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 ...
- 11.9k
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 "...
- 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,...
- 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 ...
- 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....
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.
- 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
...
- 3,990
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 ...
- 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:
...
- 2,086
Only top scored, non community-wiki answers of a minimum length are eligible