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
9 views

Under which circumstances a process in ready state can switch to exit without transition into any other intermediate state?

I was studying for an exam when I stumbled across this true or false statement: In a system of 7 states diagram, a process could switch from ready state to exit state directly. The answer to this ...
0
votes
1answer
19 views

Efficient structure for pruning on job scheduling

This is an issue I encountered on several applications with different variants. But here is the common base for which I suspect to miss a more efficient approach. There are $K$ different tasks to ...
1
vote
1answer
39 views

Terms related to optimal scheduling

I am studying a certain theoretical optimization problem related to scheduling, and I am confused by the different terms used in the literature for such problems. In particular, I found the following ...
0
votes
0answers
20 views

Optimisation of workforce allocation

I am looking at a problem of cost optimisation by dynamic staff allocation.This could be for any public space like Airport/Railway Station etc. where the maintenance work is outsourced to other ...
0
votes
0answers
25 views

Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem. I understand how the solution is implemented but,...
2
votes
0answers
38 views

Efficient solution to this scheduling problem or integer optimization problem

Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to $$ P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)} $$ where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
3
votes
1answer
108 views

A task-scheduling problem as a matroid (CLRS book)

I don't understand very well section 16.5 of the 3rd edition of the famous Introduction to Algorithms book, known as CLRS. It defines the problem of scheduling unit-...
3
votes
1answer
63 views

CPU scheduling Decisions

Operating System - CPU scheduling Decisions The question above talks about why CPU scheduling does not take place when ready to running. But I wonder why CPU scheduling does not take place when new ...
1
vote
1answer
28 views

Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases

I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v_1, v_2)$ signifies, that tasks $v_1$ and $v_2$ can ...
5
votes
0answers
41 views

2-Dimensional interval scheduling problem

I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format: Cars with the start and ...
0
votes
0answers
15 views

Scheduling Repeating, Flexible Intervals with Restrictions on Overlap

I work in 52:17 work:break intervals, as there's some evidence showing it's an effective way to structure the day. However, meetings or planned breaks often require shifting that schedule, moving, ...
2
votes
1answer
23 views

Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?

Intro The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its ...
2
votes
1answer
12 views

Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment. Say that ...
1
vote
0answers
28 views

Cyclic finite scheduling algorithm

I have a scheduling problem with the following specifications: A single machine is used. $n$ jobs $\mathbb{J} = \{J_1,...,J_n\}$ are available from the start $t = 0$. Each job can be executed several ...
0
votes
0answers
20 views

Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?

I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
0
votes
0answers
23 views

Test data for tasks that communicate over network

I am working on a load balancer that schedules tasks that communicate over network. I want to test its performance, but I'm struggling to find test data for it. Currently I try to extract relevant ...
0
votes
0answers
22 views

How to place the deadlines in “Earliest deadline first scheduling” in this question?

So I followed this tutorial to get the concept of "Earliest deadline first scheduling". I have to implement this task >>> TASK. Now the thing which I am not getting in this Task is ...
0
votes
0answers
18 views

What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
1
vote
1answer
700 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: ...
2
votes
0answers
98 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 ...
0
votes
0answers
54 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\...
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....
0
votes
0answers
21 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. ...
2
votes
1answer
93 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
12 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....
2
votes
0answers
46 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
74 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
1answer
42 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
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
31 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 ...
0
votes
0answers
34 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 ...
3
votes
0answers
47 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
51 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 ...
1
vote
0answers
226 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, ...
2
votes
1answer
39 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 ...
0
votes
1answer
509 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
47 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
34 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
154 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
60 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
110 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
72 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
99 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
48 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
352 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
20 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
2 3 4 5