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).

Filter by
Sorted by
Tagged with
16 votes
4 answers
2k views

Best model for precedence constraints within scheduling problem

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to ...
JakobS's user avatar
  • 2,747
14 votes
4 answers
2k views

How to model a mixed-integer linear programming formulation in Python using Gurobi?

I can remember that I spent some time in understanding how to formulate my first model. So I aimed at presenting a complete model here, wishing to save some time for students or researchers needing it....
Mostafa's user avatar
  • 2,104
12 votes
3 answers
1k views

Number of aircraft to operate in an airline company

Suppose that an airline company has X planes, in general the companies keep a number of these aircraft (say 80% of X) in reserve in case of hazards. My question is how the airline companies compute ...
user109284's user avatar
12 votes
2 answers
491 views

Job Shop Scheduling: what objectives are harder?

It is well known that job shop scheduling problems are notoriously hard from a computational point of view. Many papers exist for the makespan objective, and some report on min sum objectives (like ...
Marco Lübbecke's user avatar
12 votes
1 answer
173 views

Improving cuts from sub-problem with problem-specific hierarchical information

I'm solving an assignment-alike problem with a Logic-based Benders decomposition-alike (LBBD) method. The master problem provides an assignment, which is checked in the sub-problem. Define the set of ...
Jasper's user avatar
  • 221
11 votes
5 answers
1k views

How to implement a "generic" solver for scheduling problems?

I have been accepted for an internship for 6 months. The aim of this internship is to implement a "generic" solver for scheduling/production planning problems. This solver will bill a small prototype ...
Antarctica's user avatar
  • 2,917
11 votes
5 answers
1k views

Dealing with non-overlapping constraints

Let us consider the following problem: Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$ and a target start time $s_t$. No two tasks can be executed in parallel. The objective is to ...
Renaud M.'s user avatar
  • 2,398
11 votes
2 answers
1k views

What is the difference between job shop scheduling and resource constrained project scheduling?

I read here https://slideplayer.com/slide/3353960/ that RCPS is a generalized version of job shop scheduling. I'm new to this area and I'm trying to classify a specific variation of these types of ...
cdrootsudormstardashr's user avatar
11 votes
1 answer
380 views

Algorithm for workforce scheduling for call volumes

I am trying to solve a workforce scheduling and optimization problem. Available data: daily level forecasted call volumes, shift schedules, resource utilization at the aggregate level, AHT at ...
Lalitha Sundar Iyer S's user avatar
10 votes
5 answers
674 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 ...
BloodyOrange's user avatar
9 votes
1 answer
251 views

Scheduling events in order to maximize preparation time

Problem statement I'm given a set of events $E$, and $\forall e \in E$ also: a set of plausible dates on which the event can happen $D_e$ importance (weight) $w_e$ ideal preparation time duration $...
Eugleo's user avatar
  • 225
9 votes
1 answer
287 views

How to tackle large nurse scheduling problem?

I have a nurse-scheduling type of problem with a time span of a year and many employees. Formulation My main variables are: \begin{align}x_{e,t} &= \begin{cases}1 \text{ if employee } e \text{ ...
Stradivari's user avatar
  • 1,414
8 votes
3 answers
400 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 ...
LouisPopovic's user avatar
8 votes
3 answers
1k views

Maximize assigned tasks to each worker

In a scheduling problem I want to assign the maximum number of tasks to one worker before assigning it to another. For example, if I have $10$ tasks and $2$ workers, the best assignment would be $(10, ...
Stradivari's user avatar
  • 1,414
8 votes
1 answer
447 views

Finding minimum time for vehicle to reach to its destination

Given a set of Vehicles with source and destination I need to find the minimum time of travel for all the vehicles, there are also some charging stations and its necessary for vehicles to charge 1 ...
ooo's user avatar
  • 1,589
8 votes
2 answers
856 views

What is this type of scheduling problem called?

I am currently working on software that deals with a specific type of scheduling problem, and I want to improve the scheduling algorithms that it uses. However, when I tried to research algorithms ...
2012rcampion's user avatar
8 votes
1 answer
247 views

Workforce Scheduling problem - Modelling to minimize resources

I am working on a scheduling program for a service desk. I want to decide the number of people required to come in at each shift. The data I have is: There are 4 overlapping shifts Arrival pattern at ...
Lalitha Sundar Iyer S's user avatar
8 votes
1 answer
107 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 ...
Best_fit's user avatar
  • 567
8 votes
1 answer
198 views

How to model 24 hours demand into a daily shift schedule?

I am working on a weekly staff scheduling optimization problem with 24/7 demand. The binary decision variable is: $X_{\text{staff},\,\text{day},\,\text{shift}}$ whether to assign the staff $s$ to day ...
janicebaratheon's user avatar
8 votes
1 answer
233 views

How to classify and model this problem?

I was given the task to model the following problem and find a solution for it, but as I do not have any experience in this field, I already have trouble classifying it. There are a number of ...
DocRobson's user avatar
8 votes
1 answer
177 views

Extract info from Gurobi binary variables during run-time

Actually the question below is not specific to Gurobi, but that's the tool I am using. Consider a scheduling problem where a 2D array of binary variables $Z(i,v)$ is defined, where $i$ is index of ...
user22363's user avatar
  • 281
8 votes
1 answer
168 views

What class of scheduling problem models jobs which require multiple machines simultaneously?

In the Flow/Job Shop problems, and other related scheduling problems, a common assumption is that at any given time, a particular job will be being processed on at most one machine (usually... none). ...
Brendan Hill's user avatar
8 votes
0 answers
101 views

Examples for a kind of "set family hitting" problem

Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the ...
Thomas Kalinowski's user avatar
7 votes
3 answers
323 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 ...
Clement's user avatar
  • 2,224
7 votes
1 answer
1k views

How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour

I would like to know of a method in which if provided say 10 routes with details regarding which route intersects with which another route, we can use the least number of colours to colour the routes, ...
Burhanuddin Samiwala's user avatar
7 votes
2 answers
403 views

Why most of constraint solvers do not support optional intervals?

Optional interval is a great idea of optional interval/task that can be active or inactive based on boolean variable. I found it very useful in complex scheduling problems. It was introduced in IBM Cp ...
gregy4's user avatar
  • 189
7 votes
2 answers
284 views

CPLEX CP Optimizer Java API function missing

I can not seem to find the needed functions to model the following problem through the Java API (CP Optimizer): a machine that has downtime and sequence-dependent setup times, with the extra ...
Maarten's user avatar
  • 295
7 votes
2 answers
253 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 ...
Barry S.'s user avatar
7 votes
2 answers
1k views

Finding an Objective Function for Assigning Employees to Sequence Dates

I am using a mixed-integer-program to schedule employees to projects. These projects can have a time window to get completed from a few weeks to a few months. At the moment I am working in a ...
Georgios's user avatar
  • 1,193
7 votes
1 answer
116 views

CVRP with vehicles blocking each other

I have a standard CVRPTW (capacitated vehicle routing problem with time windows). The instance is given by a (not complete) graph $G$ with weighted $w$ directed edges $e \in E$, and I have a limited ...
PSLP's user avatar
  • 2,401
7 votes
1 answer
166 views

How to solve this variant of RCPSP

We have $m$ projects in parallel that require shared resources the resources has time varying capacities (i.e $B_{rt}$ is the units of resource $r$ available in period $t$). For each project there is $...
Joffrey L.'s user avatar
7 votes
1 answer
227 views

Variant of job shop scheduling problem

I'm looking to identify a problem in the literature that I'm currently solving. I have a set of jobs each having a set of operations. Each operation has a duration. An operation may be done by a ...
Stephen Hill's user avatar
7 votes
0 answers
91 views

Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
dassouki's user avatar
  • 153
6 votes
3 answers
491 views

Scheduling problem data generation

I compare the strengths and weaknesses of paradigms and approaches within those paradigms for solving machine scheduling problems. The amount of real-world data I have is limited and (random) ...
Maarten's user avatar
  • 295
6 votes
1 answer
653 views

Doubles Round Robin Sorting Algorithm

Background: I have a group of 6 guys that get together and play pickleball every week. We play 2v2 and 2 players sit each game. We play 2 sets of 6 games each week (12 total games) - in each set, ...
WoodGuyPurdue's user avatar
6 votes
1 answer
235 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 ...
BloodyOrange's user avatar
6 votes
1 answer
844 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 ...
t25's user avatar
  • 63
6 votes
1 answer
372 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 ...
dassouki's user avatar
  • 153
6 votes
1 answer
140 views

Optimal Energy Charging/discharging Scheduling Problem

I'm new to IBM CP optimizer. I want to make charging / discharging scheduling based on cost (value will change on time) and my objective function is $$\sum_{t=1}^{24}\sum_{j=1}^5x(1)^{(t,j)}x(2)^{(t,j)...
JG.K's user avatar
  • 61
6 votes
0 answers
162 views

Modelling issue with precedence constraint in OR-Tools

I'm trying to solve an RCPSPDc model It is infeasible, although Ilog Cplex solves it, so I think I have a modelling issue. I have more constraints but the precedence is the one that makes it ...
Diego R. Troncoso's user avatar
5 votes
3 answers
2k 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, ...
Mohammad Namakshenas's user avatar
5 votes
2 answers
520 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 ...
Ronaldinho's user avatar
5 votes
3 answers
720 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. ...
Lopez's user avatar
  • 205
5 votes
3 answers
747 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 ...
fathese's user avatar
  • 423
5 votes
3 answers
198 views

Trouble with scheduling problem assumptions

Reading the famous book by Pinedo, I came across : Usually, the subscript $j$ refers to a job while the subscript $i$ refers to a machine. If a job requires a number of processing steps or ...
Antarctica's user avatar
  • 2,917
5 votes
2 answers
200 views

How to combine MIP solver with a CP one?

I am working on the scheduling problem in the class of parallel resource scheduling models. When I have studied some papers regarding that, I see the method that combines an MIP with a CP. The ...
A.Omidi's user avatar
  • 8,737
5 votes
1 answer
485 views

Is it possible to solve VRP using OR-Tools CpModel, instead of RoutingModel?

Is it possible to solve VRP using OR-Tools CpModel, instead of RoutingModel? I want to do synchronized VRP, which is combining vehicle routing and scheduling constraints
Rizky Luthfianto's user avatar
5 votes
1 answer
275 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 ...
Richard's user avatar
  • 3,459
5 votes
1 answer
350 views

Scheduling with transition costs - DOCPLEX

I am dealing with a kind of scheduling problem. I have a set of tasks to be executed by a set of machines. It is known that different machines are able to execute the same task, but each machine can ...
campioni's user avatar
  • 1,133
5 votes
0 answers
50 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 ...
Erel Segal-Halevi's user avatar