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.
217
questions
1
vote
1answer
25 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 ...
-1
votes
2answers
4k views
SCAN and CSCAN algorithms of disk scheduling
I am having hard time understanding the working of SCAN and CSCAN algorithm of disk scheduling.I understood FCFS,Closest Cylinder Next but heard that SCAN resembles elevator mechanism and got confused....
1
vote
1answer
88 views
Default scan order in SCAN and LOOK disk scheduling algorithms
I've been learning various disk scheduling algorithms in Operating systems. I wanted to know if there was any default scan order in SCAN, C-SCAN, LOOK and C-LOOK algorithms, like towards higher ...
2
votes
1answer
49 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 ...
4
votes
2answers
11k views
Disk scheduling algorithm - SCAN and C-SCAN
I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a ...
2
votes
1answer
30 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
2answers
372 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
87 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
42 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 ...
3
votes
1answer
548 views
Task calendar scheduling algorithm
I want to write a scheduling algorithm for the following scenario:
There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is ...
2
votes
2answers
377 views
Scheduling / Queuing jobs with multiple different workers
I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system.
Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue).
...
0
votes
2answers
24 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 ...
0
votes
0answers
28 views
How to compute this CPU scheduling exercise?
How can I compute this type of problem? My doubts are one the number of jobs, I have tried drawing a Gantt chart, but it becomes huge and unmanageable.
How am I supposed to represent the results?
...
0
votes
1answer
379 views
Find optimal quantum at Round Robin Scheduling algorithm
In this process list situation
How can I find the quantum time ( time slice ) at 80% of CPU time ?
I found only for 100% of CPU time, so I don't know if it's the same for 80% case
B.T.Q= [mean + ...
1
vote
1answer
40 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
40 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
13 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
2answers
58 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 ...
9
votes
1answer
195 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
0answers
23 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 ...
2
votes
1answer
65 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 ...
0
votes
0answers
21 views
How should I make this algorithm / What algorithms are avaiable for scheduling tasks
As part of a school assessment task, I am required to create a solution which incorporates a complex algorithm.
I have an idea for the algorithm and it goes as followed; A complex algorithm which ...
1
vote
0answers
13 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
78 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 ...
0
votes
0answers
20 views
Preemptive priority scheduling problem with same priority
So if T1(priority 3, arrived first) was preempted it is put back to the runqueue. If there is already T4(priority 3, arrived fourth) inside the runqueue, which one of these two will be handled first?! ...
1
vote
1answer
57 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
0answers
16 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 ...
0
votes
1answer
4k 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
1answer
34 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
23 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
149 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
385 views
Correctness proof for greedy algorithm based on ratio
I've an issue stated as follows:
We have 10000 jobs to do, each with some length $l_i$ and weight
(importance) $w_i$. Our goal is to arrange the schedule of doing these
jobs (in other words, ...
4
votes
1answer
262 views
Single machine job scheduling to minimize weighted sum of completion time
Given $n$ jobs, schedule them such that the weighted sum is minimum.
weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :
$S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
0
votes
0answers
32 views
Scheduling jobs on a single machine - minimising the weighted sum of completion times
Consider the following problem:
there are $n$ jobs $\{1,...,n\}$, each has a processing time, $p_i$, a weight $w_i$, and an arriving time $r_i$. The goal is to minimise the weighted sum of completion ...
0
votes
0answers
17 views
Can't Understand the formula for processing speed of each job
I am trying to understand the formula for processing speed of each job. I got the formula from the following link:
Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines
The other ...
2
votes
1answer
48 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
0answers
547 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
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 ...
0
votes
2answers
325 views
Round Robin Scheduling: No process in Ready Queue
First post here, glad I found this exchange. I am in my Operating Systems course at university learning process scheduling. In my homework assignment we have to fill out a simulated scheduling chart ...
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 ...
0
votes
0answers
107 views
Advantages of Preemptive Scheduling
I'm currently studying for an exam which includes operating systems. I'm solving the exams from previous years and I'm stuck on a particular question:
"One of the advantages of preemptive scheduling ...
1
vote
0answers
17 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 ...
3
votes
1answer
46 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.
...
1
vote
1answer
30 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 ...
0
votes
1answer
66 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
28 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 ...
7
votes
5answers
102k views
What is the average turnaround time?
For the following jobs:
The average wait time would be using a FCFS algorithm:
(6-6)+(7-2)+(11-5)+(17-5)+(14-1) -> 0+5+6+10+13 -> 34/5 = 7 (6.8)
What would the average turnaround time be?
1
vote
0answers
225 views
Job scheduling and packing algorithm
I was thinking about developing a daily production work plan algorithm for an enterprise. The problem is as following:
There are various tasks that needs to be completed, each has a deadline, a ...
0
votes
0answers
31 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$....
