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.
237
questions
2
votes
1answer
56 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 ...
3
votes
2answers
438 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
135 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
140 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
0answers
91 views
Dynamic job scheduling with earliest time and deadline
I have a real life algorithmic problem and I'm trying to find out if there is any similar widely known algorithmic problem with known solutions that I could adapt to my particular use case.
I want to ...
2
votes
1answer
498 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
56 views
Algorithm favours CPU bound or I/O bound processes
Some scheduling algorithms favour CPU bound processes while others favour I/O bound processes.
Which algorithm favours which type of process?
My answers:
SJF favours I/O bound processes.Explanation: ...
0
votes
0answers
18 views
What is the significance of Bellman-Ford and linear programming for scheduling and makespans?
CLRS exercise 24.4-9 says the following:
Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
3
votes
1answer
674 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 ...
0
votes
0answers
18 views
Extending the token bucket algorithm
I've been looking at implementing a local rate limiting solution satisfying certain guarantees. I've found surprisingly little literature on the extensions of the token bucket algorithm to hierarchies....
2
votes
2answers
436 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
1answer
440 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
31 views
Optimal Selection of Non-Overlapping Jobs
I'm trying to find what the family of problem is - as well as an approach - for the following:
I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri.
Each task ...
2
votes
1answer
78 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
1answer
62 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 ...
2
votes
1answer
80 views
Early Deadline First (EDF) scheduling in real-time systems feasibility test proof
I am trying to prove Theorem 6.2 on page 127 of the book Real-Time Systems by Jane W. S. Liu: http://www.cse.hcmut.edu.vn/~thai/books/2000%20_%20Liu-%20Real%20Time%20Systems.pdf
It is based on Early ...
0
votes
0answers
18 views
Operating System that had the convoy effect
I read some things about the convoy effect (or problem), and at one source there was mentioned, that it was "implemented" in "historic" or very old outdated operating systems. I ...
0
votes
0answers
16 views
Algorithm for assigning 2 list of different objects into connected slots optimally
I would to optimally assign objects into slots. There are 2 lists of 2 different elements that have to be assigned. An element from list 1 must be grouped with an element from list 2 into one slot.
...
0
votes
0answers
8 views
Why the proof of the hyperbolic bound for rate-monotonic scheduling works?
Recently I'm trying to prove the hyperbolic bound for rate-monotonic scheduling (RMS).
[original paper] http://retis.sssup.it/~giorgio/paps/2001/ecrts01-hb.pdf
[more formal paper] https://ieeexplore....
0
votes
1answer
5k 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 ...
1
vote
1answer
97 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 ...
0
votes
1answer
35 views
Interval Scheduling problem with more than 1 machine
There are 2 machines.
Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine
The list of n ...
0
votes
1answer
61 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 ...
2
votes
0answers
28 views
Maximize the minimum gap while scheduling within intervals?
Problem
There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals?
For ...
0
votes
0answers
45 views
Gantt chart for Round Robin Scheduling using only arrival and completion time
I had the following question in my Operating System 'CPU- Scheduling' assignment-
4 processes A,B,C,D have estimated time of completion of 5,7,9,11 ns each. They are scheduled in a round-robin fashion ...
0
votes
0answers
23 views
About a fair scheduler
Is there any difference between having a fair scheduler (an adversary cannot reorder messages sent by correct processes) and having a reliable point-to-point FIFO link among processes?
0
votes
0answers
19 views
How to justify the choice of using a specific metaheuristic?
For a problem how to justify the use of a metaheuristic upon another?
For exemple for scheduling problem, could the same heuristic be efficient for different variants of the problem?
What are the ...
0
votes
0answers
30 views
Operating system scheduling doubt
Consider a uniprocessor system executing three tasks T1,T2 and T3 each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 ...
1
vote
1answer
141 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 ...
0
votes
0answers
32 views
How does the Fetch-Decode-Execute-Reset (FDER) cycle work?
How is this different to the Fetch-decode-execute (FDE) cycle?
I have an understanding of the FDE cycle and how the CPU works, although I came across a FDER cycle, when reading about the CPU ...
1
vote
0answers
118 views
What are the differences between Earliest Deadline First (EDF) and Earliest Due Date (EDD)?
From my understanding, the EDF (Earliest Deadline First) rule is essentially an iterative "version" of the EDD (Earliest Due Date) rule, which allows for preemption. At every point in time, ...
3
votes
0answers
46 views
I'ld like a better algorithm for scheduling tutors to fill a set of shifts
My problem is as follows:
I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room A on M, W, F from 9-11am and Sa from 12-3 pm.
...
0
votes
0answers
44 views
Scheduling jobs online on 3 identical machines - a lower bound of 5/3
Consider the Online Scheduling Problem with $3$ identical machines. Jobs, with arbitrary size arrive online one after another and need to be scheduled immediately on one of the $3$ machines without ...
0
votes
1answer
399 views
Greedy sequential/parallel task scheduling
We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and ...
1
vote
0answers
19 views
Understanding proofs Lemma 11 & 10 in this specific Computer Science Scheduling Paper
I'm having a hard time wrapping my head around the proofs Lemma 11 and Lemma 10 (Pages 10 and 11) in this paper called: Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling.
Generally the ...
0
votes
0answers
34 views
Scheduling algorithm for overlapping jobs - single resource?
I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are ...
0
votes
1answer
30 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
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....
2
votes
1answer
57 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 ...
0
votes
2answers
52 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
29 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?
...
1
vote
1answer
68 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
46 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
16 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
103 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
244 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
27 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 ...
0
votes
0answers
22 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 ...
