# Tag Info

14

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 before). In that case, your precedence constraint can be formulated as $$s'_{j_2,t} \leq s'_{j_1,t-d_1}$$ Notice that you can do a change of variables ($s_{j,1}... 14 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 number of exact and approximate algorithms. Specifically, you're trying to find a constructive algorithm for determining the chromatic number. For 10 routes ... 12 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 generated to meet the traffic demand The productivity of the aircraft (ASK per day) results in the number of aircraft to be acquired and its financial impact (Costs) ... 12 Here is the complete implementation for the above-mentioned model. from gurobipy import * import numpy as np # Parameters needed are: # (1) the total number of jobs (n). Here I denote it by "NumofJobs" # (2) the total number of machines (m). Here I denote it by "NumofMachines" # (3) the processing times. Here I use a numpy matrix: "... 12 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. In one approach, you create continuous variables for each vehicle representing the time the vehicle begins charging, the time it ends charging, and the time it ... 11 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}+\sum_{t\le t_2}s_{j_2,t}\le 1.$$ 9 Why quadratic? just use a larger (linear) weight for tasks assigned to worker 1. 8 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 money. An airline will determine the fleet size needed to serve the anticipated demand (see Oguz's answer for literature on how they do this), and will cover ... 8 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) are unitary, i.e. one machine can process only one task at a time. In the RCPSP, resource consumption of tasks and capacities of resources may not be unitary, ... 8 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 scheduling problems. (E.g. vehicle routing problem variants). Planning and Scheduling, specifically in the real application, will need to survey from some ... 8 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 function of the goals of the project, the help & know-how of the people who employ you and, crucially, what you can realistically do in 6 months. Keep in ... 8 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 industry experience). For example, there is a compendium by Oleg Shylo of experimental results for job shop problems at http://optimizizer.com/jobshop.php. 8 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 fit in Excel, but the dimensions of the problem might be a bit much for the version of Solver included in Excel. There are some solver alternatives for Excel (... 8 Introduce a binary variable$x_{d,s}$and change the right hand side to$1+2x_{d,s}$. 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 teami$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 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 might look at modeling demand and labor in a cumulative manner. For each hour of the time horizon, total the worker-hours required to fix all defects that must be ... 7 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 both valid solutions, is their average always a valid solution?" If the problem is convex, the answer must be yes, since that's the definition of convexity. In ... 7 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 some sort of binary variable in formulating, but there may be other ways than the method you give. 7 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 example of how to check solve output after you solve. Part I: Eliminated extra imports + added comment characters import gurobipy as grb # Parameters needed ... 7 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 "alldifferent" constraint, for which every CP solver I've heard of has an implementation. Your second constraint just becomes the definition of the domain for ... 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 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 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 ... 7 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. 7 within CPLEX you could try CPOptimizer and use intervals. In OPL (One of CPLEX API) you could write using CP; int sizeT=10; range T=1..sizeT; int d[i in T]=i; dvar interval t[i in T] size d[i]; {int} T1={i | i in T : i <=(sizeT div 2)}; {int} T2=asSet(T) diff T1; subject to { forall(i in T1,j in T2) overlapLength(t[i],t[j])==0; } and then see This ... 6 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 of the time spent on it, that contributions are additive (the value of partially doing task 1 does not in any way depend on what is done with task 2), that the ... 6 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: m.setParam('TimeLimit', 600) To retrieve the objective function of the problem: Objective_Of_The_Problem = m.objVal To retrieve the status of the problem: Status_Of_The_Problem = m.status To ... 6 You can model the disjunction by introducing binary variables$x_{l,l^\prime}\$ and the following linear constraints: \begin{align} \xi_l+\xi_{l^\prime}-1 &\le x_{l,l^\prime} + x_{l^\prime,l}\\ T_{r,l}+t_l&\geq x_{l^\prime,l}(T_{e,l^\prime}+t_{l^\prime}) \\ T_{r,l^\prime}+t_{l^\prime}&\geq x_{l,l^\prime}(T_{e,l}+t_{l}) \\ \end{align} The first ...

6

Generally speaking the most generic scheduling problem is the RCPSP. However, even that tends to need extensions for many practical problems. See Hartmann, Sönke, and Dirk Briskorn. "A survey of variants and extensions of the resource-constrained project scheduling problem." European Journal of operational research 207.1 (2010): 1-14. for a structured ...

6

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, use a (well-crafted) third-party library to do the actual metaheuristic computations, rather than writing your own. It's likely to be faster than what you would ...

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