# Tag Info

## Hot answers tagged scheduling

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 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 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, ... 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 ... 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 ... 6 There are many ways to approach your problem and there is a lot of literature on similar problems. You could look at the following article: Gorissen, Bram L., et al. “A Practical Guide to Robust Optimization.” Omega, vol. 53, June 2015, pp. 124–37. ScienceDirect, https://doi.org/10.1016/j.omega.2014.12.006. A simple approach would be to add 'safety slack' ... 5 There are some linear possibilities, depending on exactly what your goal is. They all require adding some binary variables to what is already a discrete optimization problem. One is to maximize the spread between the largest and smallest assigned loads (or maybe largest and smallest nonzero loads). That may result in one large load, one minimal (zero or one ... 5 I'm not sure I understand what the questions are. In your demand constraint, you should also include a term forX_{\text{staff},\,\text{day} - 1, \,\text{overnight}}\$ on every day other than day 1. On day 1, the equivalent tweak is to adjust the demand by the staff level of the overnight shift from the last day of the previous week (which you presumably ...

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