Questions tagged [scheduling]
For questions about methods that assign resources to work requests (e.g. processor time to tasks) usually minimizing some cost measure (e.g. makespan).
103
questions
5
votes
0answers
31 views
Constant-factor approximation algorithms for max-min number partitioning
In the k-way number partitioning problem, the input is a set of numbers and the goal is to partition them into $k$ parts in an optimal way. The most well-studied optimization objective is to minimize ...
2
votes
0answers
84 views
Harvest planning problem
I need to model the following problem:
For a planning horizon of $P$ equal periods, one has $N$ harvesting locations and $K$ contractors who can harvest at those locations ($K < N$). Each ...
5
votes
1answer
79 views
What are (some of) the best resources for shift scheduling/rostering?
Shift scheduling/rostering is obviously very widely researched, with tons of papers around it. I found the review papers by Van den Bergh et al. [1] and Ernst et al. [2], but am looking for something ...
1
vote
0answers
54 views
Adding sequence constraints to the assignment problem- Python
This is an online assignment problem and yet can be considered as an assignment problem with a sequence. Assume that workers are coming into the system sequentially and I want to assign a task to them ...
7
votes
2answers
152 views
What strategies to use for Scheduling of Connected Sequences?
I'm given a problem in which I need to schedule multiple sequences. The goal is to minimize the makespan. I'm allowed to elongate all tasks, but I cannot reduce their width nor disconnect any of the ...
3
votes
1answer
90 views
A specific case of a resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$) - OR-Tools
I've been trying solve a specific case of the resource constrained project scheduling problem with partially renewable resources (RCPSP/$\pi$ in the literature e.g. this paper). These resources are ...
2
votes
2answers
110 views
Scheduling of planned orders while respecting certain stock levels
I am searching for the academic name of the problem of computing a valid schedule for planned order. More precisely, The problem consists of: list of orders O, available vehicle per day K, and the ...
1
vote
1answer
79 views
Formulate a constraint set to identify the number of overlapping operations
Let assume we have operation $r \in R$, machine $n \in N$ and day $t \in T$. $S_{r}$ is the service duration of operation $r$. Note that $S_{r}$ can be defined based on time slot (e.g., $S_{1}$ can be ...
1
vote
0answers
45 views
How to use gurobi to plan production and minimize the times of changeovers
Suppose we have two lines: L1 and L2.
Suppose we have 4 product types: A1, ...
3
votes
0answers
56 views
Resource scheduling problem with synchronization constraints: Weak LP relaxation
I have a resource assignment/scheduling problem which involves assigning jobs to $m$ workers. There are 2 sets of different jobs, $J^1$ and $J^2$, and a set of periods $T$.
Let $d_{jt}$ be the number ...
2
votes
0answers
99 views
Multiple Depot/Crew Office Bus Driver Scheduling Modelling
I'm working on Bus Driver Schedule with multiple add-on constraints that are complex and hence trying to figure out how this can be achieved.
Reference of Bus Driver Scheduling using OR-Tools:-
https:/...
2
votes
0answers
60 views
Maximizing the minimum machine completion time
There are $n$ jobs with different processing times, and they should be scheduled on $m$ identical machines such that the smallest completion time is as large as possible. This problem is NP-hard even ...
-4
votes
2answers
65 views
multiple cranes scheduling optimization [closed]
So i'm working on my school project and The problem is described as follow:
we have 31 baths and 4 cranes '1 axis of movement'.
figure 1: a crane imageimagen_2021-06-01_120450.png
figure 2: baths ...
3
votes
1answer
50 views
How would I model the following problem concerning customer service via FCFS vs Appointment Scheduling
I'm unfamiliar with OR, and would like to get some advice on how to "think" about this scenario:
I work for an organization that primarily has store fronts. Customer's arrive throughout the ...
2
votes
2answers
126 views
What kind of scheduling/packing problem is this?
I have the following problem which seems to be a mixture of a resource constrained scheduling and packing problem.
There is a set of activities $A_1,\ldots,A_n$ and given precedences $P$, where $(A_i,...
5
votes
2answers
431 views
How to minimize the number of breaks in sports scheduling?
I have the following sports scheduling problem.
For $n$ teams and $m$ rounds, I define the binary decision variable
$$
x_{i,j,s} = \text{1 if team $i$ plays at home against team $j$ at round $s$, 0 ...
4
votes
1answer
329 views
Assignment and scheduling problem with resource constraints
I have 10 tasks with 6 workers. Each worker can only serve one task at a time and must complete the task before moving on to the next task. Each worker has a maximum work output value and each task ...
2
votes
2answers
83 views
Relationship aware task scheduling heuristics
I have a task scheduling/assignment on machines problem (like a classic bin packing problem) with a twist in which the placement/assignment of one task affects the placement/assignment of other tasks (...
4
votes
3answers
134 views
Modelling precedence relations
I have two tasks $i$ and $k$ with durations $d_i$ and $d_k$, where $d_i$ and $d_k$ are nonnegative variables.
I would like to model that $i$ may precede $k$ or $k$ may precede $i$ and that they may ...
4
votes
2answers
185 views
Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (`python`)
I am trying to write a program to schedule a team of 8 individuals into shifts.
I want to know how to model that every individual must get at least one night shift break, and must not work two ...
2
votes
1answer
67 views
How does the RCPSP's precedence constraint work?
In [1] the authors define the RCPSP (resource-constrained project scheduling problem) as follows:
minimize
$$
\sum_{t} t x_{n t}
$$
subject to
$$
\begin{array}{c}
\sum_{t} x_{j t}=1, \quad j \in J, \\
...
1
vote
0answers
55 views
Modified bus scheduling problem question in ortools
Has been crossposted in stackoverflow. I want to solve the bus scheduling problem using ortools with some minor modifications. In my case, the max number of drivers is known. The modifications I would ...
7
votes
1answer
59 views
Real-life timetabling problems in education
I am looking for papers/resources that deal with timetabling problems in education. I want the resources to cover as much information as possible:
I don't have enough contact with people who are ...
1
vote
1answer
98 views
Job Shop Scheduling Problem: jobs are scheduled on the same machine at the same time
I want to solve a job shop scheduling problem. I got $n$ Jobs that have to be scheduled on $k$ Machines. A Job $i$ has 2 or 3 Tasks $j$, and there is a known sequence of the Tasks of a Job. One ...
4
votes
3answers
130 views
Optimization formulation has slow performance
I am formulating and solving a scheduling problem. The problem consists of scheduling items on a single machine, where the only time element is the transition from item $i$ to item $j$. For example, ...
3
votes
1answer
52 views
How to assign task, resources to trips
In a scheduling problem I want to assign the resources to tasks, each task has earliest start date, latest start date and duration. Also each resource has fixed number of available hours in a day. The ...
2
votes
2answers
95 views
Scheduling: Tasks changing the state of the executing machine
I have a scheduling problem in which machines consume their battery when executing tasks and charge their battery when not executing tasks. A single task has to be executed in one go (no recharging ...
0
votes
1answer
48 views
What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?
Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
3
votes
0answers
52 views
Where I can study some job shop scheduling by course (video )?
I am seeking the help to know where I can study the job shop scheduling Heuristics or using solver
by some course/video as I see some of books and papers hard to understand .
It is hoped that the ...
3
votes
2answers
92 views
Scheduling Problem With Identical Machines
I am working on a nonlinear scheduling problem that minimizes the electricity cost of a facility. This system includes a number of identical machines that consume power and produce a product. When the ...
2
votes
1answer
58 views
MIP for resources to task assignments
I have few tasks t1, t2, t3, t4, t5 which need to be assigned to resources r1, r2, the tasks are located across multiple ...
5
votes
3answers
565 views
Gurobi and CPLEX cannot exploit more than 32 cores of machine
I have some attempts to solve a scheduling problem using the Gurobi and doCPLEX API in python and .NET on Ubuntu-server installed on a hyper-computing cluster with 64 physical cores. Unfortunately, ...
2
votes
2answers
67 views
Parallel scheduling with precedence constraints and variable job length
I have $N$ jobs and $M$ machines and want to minimize the makespan, i.e. the total time to finish all jobs. Some jobs have precedence constraints and can only be started once other jobs are finished. ...
3
votes
1answer
103 views
What are the flow based formulations?
What are the flow-based formulations? For what optimization problems are they applied, and in which form? Which are the specificities of such a formulation?
Also, the same question for the time staged ...
3
votes
0answers
104 views
Production planning for a video game economy
I'm a software developer who likes to play a video game that has a complex economy. I realized that the type of problem I'm trying to solve mimics real life operations research problems, and I am ...
2
votes
0answers
50 views
Heuristic to compute upper bound for the simple assembly line balancing problem type 2?
I am currently working on SALBP-2 described as:
Given the number m of assembly stations, minimize the cicle time c.
I have done a bit of research and found the following approach to solve it:
The ...
3
votes
0answers
53 views
Flexible Job Shop with Preemption
I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
5
votes
3answers
656 views
How to determine if this problem is NP-HARD or NP-COMPLETE?
Suppose that I have a pool with N nodes and I have to move the nodes one by one to another pool. For each move, consider a value on the edge linking the two pools. The goal is to find a order of nodes ...
3
votes
2answers
108 views
Relaxation and complexity of two formulations
I have two different MILP formulations for the same scheduling problem with the same complexity but with different running times. Why it is recommended to compare the relaxed versions of each ...
0
votes
1answer
101 views
What kind of job shop scheduling problem is this and how do I solve it?
I have a production planning / scheduling problem, which I believe is a kind of job shop scheduling problem.
But I would like to get some input on what kind of job shop scheduling problem it is and ...
1
vote
1answer
112 views
Constraint programming and scheduling issues
I have a constraint problem that I need to resolve, but I did not how know to model the problem:
I have 11 employees, I will name them from $a$ to $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.
I have a small ...
6
votes
1answer
246 views
Multi-period linear dynamic programming with differing in-period dependencies and changes
I’m not sure if I’m wording this right but in a nutshell, my problem is:
I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the ...
2
votes
1answer
75 views
MIP for assigning tasks with prerequisite tasks
I have a modified assignment problem for which I'm having difficulty formulating the constraints mathematically.
I have a set of workers and a set of tasks which should be completed in the minimum ...
3
votes
0answers
83 views
Best known results on the flexible jobshop benchmarks
Is there a website that compiles the best known results on the flexible jobshop problem ?
I know there was a blog post/article by Quintiq, a (deleted) blog post on CP Optimizer, some more recent ...
1
vote
2answers
94 views
How this problem can be defined as MultiObjective optimisation
I need to optimize the end-to-end latency of a multi-component application.
Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
3
votes
2answers
102 views
How is this problem called in literature?
I have a scheduling problem but rather than having a fixed duration of each task, we have another "concept" that verifies the following property.
Let's say task A requires a default 200 ...
5
votes
0answers
84 views
Quantifying Feasibility
I have a scheduling model formulation ( experimental setup) that takes in product states as input (sample points) and checks the model status (response) and returns feasible or infeasible.
My plan is ...
-2
votes
1answer
178 views
Optimized Production Planning & Scheduling
I want to create an optimized schedule and production to meet demand of four different buyers. I am starting with Pulp but not able to account for continuous production variable and discrete dispatch ...
1
vote
2answers
188 views
How to correct this scheduling algorithm?
I have a scheduling problem to solve. It's a resource-constrained project scheduling problem with time-varying resource availabilities. The objective is minimizing tardiness. The full detailed model ...
2
votes
1answer
114 views
Is a convex or MILP (without big-M) formulation possible for this problem
Assume we are given a directed acyclic graph (DAG) $G(V, A)$, where $|V| = n, |A| = m$, and the graph contains a source node $\mathbf{s}$ (i.e. every node in $V \backslash \mathbf{s}$ is connected by ...
