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).
115
questions
4
votes
1answer
127 views
Python "Coffee Shop Scheduling Problem" - Scheduling Lunches/Breaks
I'm working on an employee scheduling program in python. Having never done this before, I've been researching different libraries that can be used to accomplish the task.
Unfortunately, none of the ...
2
votes
1answer
41 views
How to model a cumulative resource constraint with same family condition?
Assume that we have 3 tasks to schedule : $x_{a1}, x_{a2}, x_{b3}$. They all use the same cumulative resource : $r_1$. Each activity increases $r_1$ by $1$ at it starts time and decreases $r_1$ by $1$ ...
1
vote
1answer
73 views
Need help with writing short proof related to Critical-Path-Method in scheduling with variable activity duration
stackexchange community,
I am currently working in the area of operations research / scheduling and am attempting to write a short proof. We are working with a directed acyclic graph of activities (...
-5
votes
0answers
70 views
why in coding constraints you don't get the right answer?
From "A new unrelated parallel machine scheduling problem with tool changes to minimize the total energy consumption" Zhang et al. 2020 paper. A scheduling problem that schedules $n$ jobs on ...
4
votes
1answer
177 views
How do constraints become redundant in a Big-M conjunction?
The following Big-M conjunction appears on page 14:3 of The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management:
\begin{align*}
\text{(i)} \quad t_{(g, \; s)} - t_{(f, \; s+...
7
votes
3answers
211 views
How to model a non-overlap constraint between 2 groups of tasks?
Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$.
Let $T_1 \subset T$ and $T_2 \subset T$ such as $T_1 \cap T_2 = \emptyset $
How can I model the following constraint : all tasks ...
3
votes
1answer
161 views
How to merge tasks or do batching in a quality control lab
Background information:
In the Quality Control labs of pharmaceutical companies, analysts inspect products or raw materials in the units of ‘batches’ (which is essential a physical sample of bill, ...
1
vote
2answers
329 views
How to include material flow in job shop scheduling problem (as constraint?)?
I am reading about https://en.wikipedia.org/wiki/Job-shop_scheduling and https://en.wikipedia.org/wiki/Optimal_job_scheduling. Such scheduling is possible if we know the number (amount) of operations (...
5
votes
3answers
314 views
Minimizing cost of transportation and storage of items
I am looking for an optimization algorithm to minimize the cost of transportation and storage cost in warehouse.
Let's assume the following table gives us the weekly forecast of Demand.
...
6
votes
1answer
185 views
How to cope with the rigidity of solutions?
Consider the following problem of Technician Routing and Scheduling Problem.
We have:
A set of customers where each customer needs the intervention of a technician to do some job. Each customer has a ...
1
vote
0answers
64 views
vehicle routing optimization, Big M method of reformulation of constraints
Please excuse me for the long question, if I dont prrovide this info. my post gets removed!
The following optimization problem is called Mixed-Integer Quadratically Constrained Programming
(MIQCP) ...
10
votes
5answers
562 views
What is the state-of-art (in industry and academy) of this scheduling + routing problem?
I have a startup idea and I am coming from a CS background.
The startup tries to solve the following problem. A company having a set of employees that needs to visit several "customers" each ...
5
votes
0answers
38 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 ...
3
votes
0answers
99 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
86 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
97 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
159 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
97 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
112 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
80 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
55 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
61 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
101 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
67 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
66 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
51 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
132 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
444 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
338 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
88 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 (...
5
votes
3answers
177 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
242 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
70 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
68 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 ...
8
votes
1answer
65 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
139 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
136 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
55 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
99 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
53 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
54 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
94 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
61 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
661 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
70 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
110 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
105 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
58 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
662 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 ...