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
2 votes
0 answers
36 views

Assignment/scheduling how to formulate considering job time and job cost

I have the following problem that I do not know how to formulate. There are a fixed number of workers $w_i \in W$ for $i \in [1…N]$. Also, there are a fixed number of jobs that must be assigned to ...
user avatar
1 vote
1 answer
62 views

How to formulate fleet Assignment Problem?

I do want to formulate a fleet assignment problem. The following table is available It shows the departure/arrival location and time I am trying to find the min number of required planes to assign to ...
user avatar
1 vote
0 answers
44 views

Minimize cost given working days/hours/required hours per job/start & end dates

I am trying to solve an optimization problem on Excel or Python. My constraints are the available number of employees (=20), the number of working days/month (=20), the number of working hours/day (=8)...
user avatar
4 votes
0 answers
72 views

Accelerating an integer programming model

I am working on a scheduling problem, where I am solving it through column generation. The pricing problem of this algorithm is an integer programming model as follows: \begin{equation} F_1 \Big\{V^...
user avatar
  • 343
3 votes
2 answers
371 views

What is the difference bewteen CP and MILP approaches in Job Shop Scheduling?

My understanding is Constraint programming (CP) is a sub-set of MILP but in MILP we not only try to find a feasible solution (like CP) but also we should optimize an objective function. I do have a ...
user avatar
2 votes
0 answers
70 views

Scheduling optimization, Adding 4 day same shift and 3 day off weekly constraint

Am writing a small scheduling program in C# for a group of 7 staff who will be working in three shifts daily for 4 weeks. Am using the google OR-Tools Template, but i have modified it abit This is the ...
user avatar
  • 121
2 votes
1 answer
105 views

Np-hard sequencing or packing problems with total ordering between elements

I would like to know if anyone is aware of any Np-hard problems in scheduling or packing where there is total ordering between tasks or items to be packed together. The objective can be anything. For ...
user avatar
4 votes
4 answers
240 views

Visualizing results to the RCPSP

Bot for getting better insight and reporting purposes, I am looking for a way to visualize results to the Resource-Constrained Project Scheduling Problem (RCPSP). I am aware that such results are most ...
user avatar
  • 115
2 votes
1 answer
178 views

How to model this user packing problem?

I have a system with $N$ resources. There are $K$ users in the system demanding these resources. The demand of resources for a given user $k$, $d_k$ follows $d_k\in\{1,3,6\}$ The constraints for this ...
user avatar
4 votes
2 answers
210 views

Identifying problem: Assignment + Job Shop Scheduling

I am new to OR. Hence, I want your advice on the problem I am trying to solve: Given: $O_1 \rightarrow O_2 \rightarrow O_3 \rightarrow ... \rightarrow O_n$: the sequence of operations to produce $1$ ...
user avatar
3 votes
1 answer
132 views

Project task scheduling based on available budget per period

I have a challenge that is a bit backwards from the usual labour resource leveling problem. In my case I have a fixed budget pool over a period to deliver some of the work packages (not enough per ...
user avatar
  • 133
2 votes
1 answer
121 views

Job scheduling for a 2 stage job with 2 machines available for each stage

I am trying to solve a problem where I am provided a list of jobs that need to be scheduled to minimize the processing time. Every job has to be performed in 2 stages where the second stage can be ...
user avatar
  • 21
4 votes
2 answers
145 views

crew scheduling problem with shift priority hard constraints

I am working on a crew scheduling problem formulated as a MIP binary optimization where each employee is represented by a binary variable $X_{ids}$ s.t. $i \in I$ is $i$th employee, $d \in D$ is the ...
user avatar
3 votes
0 answers
151 views

Circuit constraints in ortools

I am looking to assign tasks to people. Each successive task should be started after the first one is finished and should be started at the same location as the preceding task. While the time ...
user avatar
-4 votes
1 answer
58 views

MIP gives out zero as best solution when trying to optimize MIP model for flexible job-hop

I have implemented an existing MIP Model into python with the python-mip solver and somehow I only get '0' as a solution to my minimization problem. What could be the problem? I am fairly new to LP ...
user avatar
3 votes
1 answer
59 views

Determining constraint relevance in crew scheduling problem

I am working on a crew scheduling problem formulated as a MIP binary optimization where each employee is represented by a binary variable $X_{ids}$ s.t. $i \in I$ is $i$th employee, $d \in D$ is the ...
user avatar
4 votes
1 answer
140 views

Mathematically formulating formal problem of a cloud service scheduler

So, I have been tasked to create a formal mathematical description of problem statement on a cloud service scheduler for my team's university project, which is, honestly, a little weird of a thing to ...
user avatar
  • 79
2 votes
1 answer
108 views

opposite of no_overlap constraint in docplex for CP

I am using python for CP solving. I would like to know if there is constraint that does the opposite of no_overlap. This will be like overlap(interval, arr, n) interval - single interval variable arr -...
user avatar
2 votes
1 answer
42 views

RCPS with time buckets for resource capacity constraints

Goal: My goal is to come up with a Resource-Constrained Project Scheduling (RCPS) model where the resource capacity constraints are aggregated and verified on time buckets, which can be of varying ...
user avatar
  • 115
3 votes
1 answer
117 views

"Complex" scheduling problem model structure

So, I'm modelling a job assigning problem in OR-Tools CP-SAT. I want to maximize rescheduled jobs based on some constraints. Right now jobs in my model look like this: ...
user avatar
  • 51
3 votes
1 answer
111 views

Dichotomic search for biobjective linear program, max flow problem for hospital patients

I recently asked this question about formulating a max flow diagram for hospital patients. I am now considering a secondary objective which is to maximize the effetiveness of the scheduled treatment. ...
user avatar
1 vote
3 answers
241 views

optimize days between work shift

For a work shift optimization problem, I've defined a binary variable in PuLP as follows: pulp.LpVariable.dicts('VAR', (range(D), range(N)), 0, 1, 'Binary') where ...
user avatar
  • 19
2 votes
0 answers
70 views

Minimizing the number of machine starts

Please, if somebody has another approach to a similar MIP problem... Assume we have some machines $m$ and their activity could be interpreted by the boolean decision variable $x_{i,j} \ i \in m, j \in ...
user avatar
  • 83
1 vote
1 answer
114 views

Circuit constraint respecting the order of the next n jobs / jobs on each machine starting at 0

I am working on a scheduling problem in OR-Tools using the CP-SAT solver. I'm working with python but I managed to rebuild this solution as starting point: Optimal way to ensure optional intervals are ...
user avatar
3 votes
3 answers
243 views

Scheduling for the shortest days using ILP

I've tried Or-Tools and MILP solvers a couple of different ways on this, but they take a surprisingly long time to realize that the solution they generated fairly quickly is in fact minimal. Is there ...
user avatar
6 votes
1 answer
378 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 ...
user avatar
  • 63
2 votes
1 answer
60 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$ ...
user avatar
1 vote
1 answer
102 views

Need help with writing short proof related to Critical-Path-Method in scheduling with variable activity duration

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 (Activity-on-Node-...
user avatar
4 votes
1 answer
199 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+...
user avatar
7 votes
3 answers
265 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 ...
user avatar
3 votes
1 answer
169 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, ...
user avatar
  • 141
1 vote
2 answers
361 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 (...
user avatar
  • 119
5 votes
3 answers
462 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. ...
user avatar
  • 205
6 votes
1 answer
220 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 ...
user avatar
1 vote
0 answers
84 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) ...
user avatar
10 votes
5 answers
598 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 ...
user avatar
5 votes
0 answers
45 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 ...
user avatar
3 votes
0 answers
116 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 ...
user avatar
5 votes
1 answer
152 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 ...
user avatar
  • 3,359
1 vote
0 answers
205 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 ...
user avatar
7 votes
2 answers
186 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 ...
user avatar
2 votes
1 answer
155 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 ...
user avatar
3 votes
2 answers
141 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 ...
user avatar
  • 119
1 vote
1 answer
86 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 ...
user avatar
  • 343
1 vote
0 answers
97 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, ...
user avatar
  • 141
3 votes
0 answers
69 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 ...
user avatar
2 votes
0 answers
115 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:/...
user avatar
2 votes
0 answers
85 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 ...
user avatar
-4 votes
2 answers
76 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 ...
user avatar
3 votes
1 answer
57 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 ...
user avatar
  • 33