Tag Info

8

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 plays at home in round s and s-1}, \\ 0, &\text{otherwise}, \end{cases} \\\\ % a_{is} &= \begin{cases} 1, &\text{if team i plays away in ... 7 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 second one is that all cores share the same memory bus and the same L2 and L3 cache. If you solve the same problem in parallel (so start Python twice and let each ... 7 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, using many cores is not always very helpful to solve a MIP. You may want to try something like Concurrent Optimization in Gurobi to exploit performance ... 7 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. If you aren't using a commercial solver, the limit is even lower. There is an excellent book about round robin scheduling by Dirk Briskorn. It is a must-read ... 5 Let E be the set of employees, and let P be the set of periods. For e\in E and p\in P, let binary decision variable x_{e,p} indicate whether employee e goes to the company in period p. Let G be the set of groups that must go together at least once, and for g\in G, let E_g \subseteq E be the set of employees in group g. For g\in G, ... 5 If only a subset of nodes is to be transfered, and that the cardinality of this subset is undefined, then I agree with @LocalSolver. Otherwise (if all nodes have to be transfered 1 by 1), I believe the problem is not NP-hard (nor NP-complete): Consider the following graph : Create a first layer with the n nodes. Create a second layer with n \times n ... 5 This is a blocking job shop scheduling problem. The description from "An iterated greedy metaheuristic for the blocking job shop scheduling problem" (Pranzo et Pacciarelli, 2016) DOI In the job shop scheduling problem a set of jobs J must be processed on a set of machines M, each processing at most one job at a time. The processing of a job on ... 4 What are flow based formulations ? Flow based formulations can be used when working with networks. The classical approach is to define a variable for each edge of the network. In a flow based formulation, you basically perform a change of variables, and define a variable for each possible path/flow of the network. For what optimization problems are they ... 4 Start by defining the appropriate binary variable: x_{ij}=1 if and only if task i is assigned to resource j. A given task can only be assigned to one resource: \sum_j x_{ij}=1 \quad \forall i $$Daily capacity for each resource:$$ \sum_i \Delta_i x_{ij}\le 8 \quad \forall j $$(\Delta_i denotes the duration of task i) task t_3 must be ... 4 Why it is recommended to compare the relaxed versions of each formulation to deduce the running time (and more precisely about the B&B tree size)? Generally, better (= tighter) is the relaxation of an integer optimization model, better should work a brand-and-bound tree solution approach to this model. Nevertheless, there exist some NP-hard problems for ... 4 Disclaimer : this is more of a hint than a complete answer. You can use the following model as a starting point to make your own model. I am ignoring two items : Constraint from option 3: Under this option, he also must paint one year after the Option 3 repair at the same additional cost of 1M/boat. Surface area constraints You will have to tweak what ... 4 There are certainly different ways of achieving what you want. Here is how I would proceed: Start by predefining the set of all possible schedules which satisfy your constraints 2,3,4,6. Although there are many, I believe that with your constraints, it may be not too difficult to derive them somewhat automatically. Here is a subset of them in the table ... 4 Can anyone think about a better formulation? Another option is to use binary variables x_{it} that take value 1 if task i starts at time t. You then need two sets of constraints: one start time per task:$$ \sum_{t}x_{it} = 1 \quad \forall i $$don't overlap tasks:$$ \sum_{i}\sum_{k, t+1 - d_i \le k \le t}x_{ik} \le 1 \quad \forall t  This ...

4

Since you are unfamiliar with OR, I would recommend using discrete event simulation, which I think is the easiest approach for a newcomer (although it may require some programming chops, depending on what software you use). You will need a bit more than just average service completion times -- you will want a distribution of service times. (In the absence of ...

3

Yes, your proposal suffices. But the published second constraint is stronger, yielding a tighter formulation. You can think of it as a lifting obtained by using the first constraint.

3

A. Schaerf wrote an academic 40-page survey on the topic in 1999: A Survey of Automated Timetabling. Artificial Intelligence Review 13, 87–127 (1999). https://doi.org/10.1023/A:1006576209967. You can find the PDF file here. In this survey, Schaerf discusses school timetabling, course timetabling, examination timetabling, and related scheduling problems. He ...

3

Such a problem is difficult to model and solve following a MILP approach, as you observed. Boolean modeling approaches are tedious to write and don't scale well for this kind of problem. Your problem can be modeled compactly by following a list-based modeling approach instead of the classical Boolean modeling approach, as you described in your question. This ...

3

since you deal with scheduling on top of MIP you could try CPOptimizer scheduling. For instance you could start with https://github.com/AlexFleischerParis/howtowithopl/blob/master/tspcpo.mod using CP; int n = ...; range Cities = 1..n; int realCity[i in 1..n+1]=(i<=n)?i:1; // Edges -- sparse set tuple edge {int i; int j;} setof(...

3

In OptaPlanner, I'd start from the task assigning example and use a shadow variable to track the remaining battery level of every task. Then a simple constraint can check if it's ok to schedule that task on that machine: from(Task.class) .filter(task -> task.getRemainingBatteryLevel() < task.getRequiredBatteryLevel()) .penalize("Battery", ...

3

Without going into a ton of detail, the usual approach is to include a variable for the start time of each task, and a variable for the end time of each task. (Your binary assignment variables are also included.) Your objective (known as the makespan) is the maximum of the task end times. The end time for a task is the start time plus the processing time (...

3

As nicely mentioned above by @Kuifje, the problem can be reduced to a minimum-cost maximum flow problem if all the nodes have to be transferred. If only a subset of the nodes has to be transferred then this is a graph partitioning problem known: partitioning the vertices of a graph into two subsets such that the weight of the cut between the two subsets is ...

3

The initial gap can be an indicator but not a very good one. I have seen many problems start with a tight bound and then never improve, and I have also seen many problems start with a horrendous gap that improves very quickly. Honestly, there is no way to know in advance, we just have to try solving all formulations we can come up with, until we find one ...

3

Yes, this is correct and is the classical approach from Manne, On the Job-Shop Scheduling Problem (1960). In some modeling languages, you can also enforce these implications by using indicator constraints: \begin{align} y = 0 &\implies t_i + d_i \le t_k \\ y = 1 &\implies t_k + d_k \le t_i \\ \end{align}

3

You may also use CPOptimizer within CPLEX that contains scheduling high level concepts. And then you can directly use noOverlap constraints. In using CP; dvar interval i size 5; dvar interval k size 4; dvar sequence seq in append(i,k); minimize maxl(endOf(i),endOf(k)); subject to { noOverlap(seq); } the constraint noOverlap(seq); makes sure that i ...

3

I didn't find a way to express the transition constraints so i give a description what this does and mention what it lacks. using JuMP using Gurobi #needs Gurobi license but any other MILP solver callable from JuMP should work too## Heading ## using UnicodePlots are dependencies. I used UnicodePlots for debugging. It is neat. In Julia dependencies can be ...

3

I'm not sure there is name for your specific problem, but I think it is safe to say that it falls into the umbrella category of job shop scheduling, with the objective of minimizing makespan. If you do a web search for "taxonomy of job shop models" you will find a barely finite number of diagrams and articles on the subject. This paper, for ...

3

For what it's worth, we've been gathering a bunch of Design Patterns in chapter 20 of OptaPlanner's User Guide. Here are some of the drawings: There's also a video that explains this deeper. Besides these modeling basics, there are orthogonal features to consider (document in other places in the user guide): Pinning: allow the user to lock in a shift ...

2

It is an unrelated parallel machine scheduling problem with sequence-dependent family setup times. The tools define the families; the materials are family members. The tool that is on a machine completely defines the state of the machine. In the machine scheduling literature the problem might be denoted as Q|sij|Cmax It's unrelated parallel machines because ...

2

You can treat it as multiobjective if you treat end-to-end latency as one objective (to be minimized) and load on device 1 (which has limited capacity) as another objective (also to be minimized).

2

Model without bandwidth limitation We wish to select the most performing components to be hosted by two devices in order to have an end-to-end latency as minimum as possible. Let $x_{i,j}$ be a Boolean variable whose value is 1 if i-th component is assigned to j-th device, 0 otherwise where $i=1,2, \cdots, 10$ and $i=1,2$. The cpu limitation (equals to \$...

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