Questions tagged [scheduling]

Questions about the optimisation problem of ordering a set of tasks so that some objective function (e.g. makespan) is minimised. The set of constraints is crucial; in particular, there is a large body of research covering online variants. Use the process-scheduling tag for questions specifically about scheduling in operating systems.

Filter by
Sorted by
Tagged with
0
votes
1answer
59 views

Scheduling problem

I am trying to find in the literature how to solve the following problem: Suppose we have a list of $n$ jobs. Some of the jobs should be scheduled after other jobs (i.e., job a should be done after ...
1
vote
1answer
175 views

What's the name of this DFS variation

Classical DFS: A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic. A DFS ...
2
votes
1answer
68 views

How to represent sums of piecewise quadratic functions for efficient optimisation?

I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has ...
0
votes
2answers
177 views

Weighted interval set scheduling problem

Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is ...
2
votes
1answer
171 views

Greedy algorithm for job scheduling

Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime. How to prove that this algorithm has an approximation ratio of ...
1
vote
1answer
131 views

interval scheduling variant: 1 machine with 2 tasks need to complete only

I am looking for an optimal solution of an interval scheduling variant. Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum ...
3
votes
0answers
50 views

Scheduling is NP-Hard via vertex cover

Are there any existing proofs involving a reduction of the single machine scheduling problem (in any of its forms really) from vertex cover in order to prove its NP-hardness? Particularly looking for ...
0
votes
1answer
460 views

Questions regarding CPU scheduling algorithms ( Round Robin and Priority scheduling )

Consider the following processes : 1) My First Question is if we need to schedule them using preemptive priority scheduling with Round-Robin for equal processes priorities with a quantum of 3. Here ...
0
votes
1answer
26 views

How can the 4-bit page number and 8-bit offset as well as the page table be used to a answer a question like, "how big is each page"? etc

No more information required. I would just like to know how to use the information provided.
0
votes
0answers
12 views

Does anyone know the answer the following questions on converting logical - physical addresses

Due to the unforeseen pandemic, I am unable to speak to my tutor about the following question. I have emailed him, but I have not had an answer for weeks. Can someone please enlighten me. Image and ...
1
vote
0answers
28 views

"Job" scheduling with skill restrictions

I was given this real life problem and was asked if there would be a way to optimize this, I realize that this is akin to a job scheduling problem, but I can't seem to grasp how to make it work with ...
1
vote
0answers
16 views

Shortest sequence of jobs, with dependencies, subject to capacity constraints

Suppose I have $n$ courses, some with some prerequisites, and I can take up to $k$ courses in a semester. I want to compute the least number of semesters needed to complete all courses, while ...
0
votes
1answer
168 views

taking school courses efficiently

I want design algorithm that allows a student to take important courses quickly up until graduation. no time, room number, professors needed here. just my selected courses I know will allow me to ...
1
vote
2answers
298 views

Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines

I'm trying to prove a greedy algorithm works for a specific problem: You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run ...
0
votes
0answers
19 views

algorithm for scheduling tasks based on constraints and feedback loop if possible

I have a list of recurring tasks (1k+ tasks) and I am trying to find a optimal scheduling given a shared constrained resource. In other respects the tasks are independent of each other Each task is ...
2
votes
1answer
99 views

Schedule X Classes In N Classrooms

I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...) I am really out of thoughts I have X number of classes ...
1
vote
0answers
58 views

Unconditionally fair, weakly fair, and strongly fair scheduling

I am trying to understand the difference between weakly fair and strongly fair scheduling. For example, what scheduling policy would ensure that a process delayed at its first await statement will ...
2
votes
1answer
191 views

Hardness of a scheduling/assignment problem

I am trying to prove the hardness of the following problem. This problem is from google hashcode, qualification-round, 2020. Hier is a brief description of the problem. Given a list or libraries and ...
2
votes
1answer
55 views

Algorithm to enumerate all complete schedulings of finals tests?

I'm creating an app that receives some map between finals and the respective periods during which they are held and a student's required finals. I was wondering if there was an algorithm to enumerate ...
0
votes
1answer
12 views

Schedule management optimizer

I had this idea of program tohelp me in my everyday life. We both work and don't live in the same city. I was wondering how to make a program that calculate, depending on the work scheduleand the ...
1
vote
1answer
80 views

Tournament Scheduling Problem

I am trying to design an algorithm to compute the solution to this problem. Given a list of n tournaments with a name, start_date, end_date, latitude and longitude, find the list of p tournaments in ...
1
vote
0answers
15 views

Criteria based estimation of a task's due date

Basically we have a ticket system, each day we get multiple tickets with different categorization (Question,Change,Error) and importance (High,Mid,Low) for different customers (A,B,C). My job is to ...
1
vote
0answers
20 views

How do programs like Apache Airflow/ Luigi determine shortest path and how does that relate to graph theory?

I am looking for a simple layman's term explanation on how do programs like Apache Airflow or Luigi (or any Task/ETL schedulers) determine the shortest path to complete a certain task and make it ...
1
vote
1answer
45 views

Upper bound on the average number of overlaps for an interval within a set of intervals

Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded ...
9
votes
1answer
322 views

2D interval scheduling problem

Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
1
vote
1answer
48 views

Grouping n points into groups of size m with objective to have least traveling distance in each group

Assumptions: There are "n" jobs which are distributed over the city. Company has "k" available workers. Each worker can do "x" jobs per day. "x" is dependent to the worker skills and the distance ...
3
votes
1answer
95 views

Scheduling task optimization

I have the acyclic directed graph of tasks I want to perform. Each edge of the graph is a dependency, e.g. task 4 could be performed only after 1 and 2 completed. ...
0
votes
0answers
47 views

Job assignment where each worker handles two non-consecutive jobs

There are $N$ workers and $2N$ jobs, named from $J_1$ to $J_{2N}$. There's a matrix $M$ denoting the subset of jobs can be handled by each worker: If $M_{i, j}$ is true, then worker $i$ can do job $j$....
1
vote
0answers
51 views

coloring of an interval graph with constraints

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
1
vote
1answer
148 views

What is Round Robin's behavior when a process comes at the same time that the old process is swapped out?

Let's say there are two processes: p1 and p2, their arrival time and service time are 0,2 and 3,1 respectively. The time quantum is 2s. After excuting for two seconds, will the processor excute p2 ...
2
votes
1answer
1k views

DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Problem : In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ ...
1
vote
1answer
36 views

How to schedule events optimally given when the events are available?

Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example: $$ \begin{align} \textrm{Event 1} &\rightarrow \textrm{[1, 2, 3]} \\ \textrm{Event 2}...
0
votes
1answer
79 views

Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
0
votes
1answer
38 views

Scheduling algorithm with defined starting intervals and processing times

I need to design an algorithm for opening and closing some valves at regular times. The input schedule will look something like this: Every 5 minutes, open each of valves 1, 2, and 3 for 5 seconds ...
1
vote
1answer
78 views

Designing a rationing algorithm for a store

Suppose I have a store and I have n units of item x. I want to sell all n units at the end of the day. I do not know how many customers will be coming in today. One customer could theoretically come ...
0
votes
1answer
157 views

Difference between greedy and work conserving scheduler for DAG

For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do. However, I found two different upper bounds on the computation time of $T$. For the ...
4
votes
1answer
334 views

Scheduling algorithm to minimize the number of late jobs

There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to ...
1
vote
0answers
31 views

How to justify using available code (in different language) for comparing algorithms [closed]

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
0
votes
1answer
7k views

How to calculate average waiting time for round robin cpu scheduling?

I have tried to calculate average waiting time for the below details there are two answers I'm getting using two methods I'm not understanding which one is correct? The time quantum is 2 This is the ...
0
votes
0answers
58 views

Interval scheduling with shared resources between steps

I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each ...
3
votes
2answers
563 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
0
votes
1answer
316 views

Calculating minimum processing time for many recipes and tools

I originally asked this question on StackOverflow but a comment was made to the effect that my problem pertains to Job Shop Scheduling and that it was more of a comp sci problem than a programming ...
0
votes
1answer
109 views

How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$. Since the problem ...
0
votes
0answers
3k views

Calculate makespan of job shop solution?

I have a job shop problem with n jobs and m machines, a job shop means that not all jobs have to go through every machine. A job shop problem can be written as such : ...
0
votes
0answers
29 views

Finding an optimal machine assigning

I have $m$ machines and $n$ jobs. Each machine has a load capacity. Each job can be only handled by either one or two machine, and each job takes some time to finish. After it finished, new jobs can ...
2
votes
2answers
114 views

Response time of scheduling a DAG where each vertex is a task

Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to ...
0
votes
0answers
384 views

Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below: Regular chores with a start time and end time (a real-...
0
votes
0answers
59 views

A scheduling problem on an oriented graph with multiple constraints

The problem is the following : Data An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a ...
2
votes
1answer
308 views

Approximation ratio of greedy algorithm for makespan

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3. ...
1
vote
1answer
279 views

Can a schedule be conflict serializable but not serializable?

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then, My question is: Can a schedule be conflict serializable but ...