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.
270
questions
0
votes
1
answer
36
views
Minimal Hitting Sets Problem
Let $\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$ a collection of subset of some universe $U$.
We want to find a partition $P$ of $\mathcal{I}$ of minimal cardinality such that the intersection of each set ...
- 133
0
votes
0
answers
34
views
proof that the longest processing time rule computes an optimal schedule
I want to prove that:
Theorem 2.8: For any input to the problem of minimizing the makespan on identical parallel machines for which the processing requirement of each job is more than one-third the ...
- 29
1
vote
1
answer
45
views
Scheduling jobs with two people where part (a) of each job must be finished before part (b)
There are n jobs each consisting of two parts: a and b.
There are two people:
person ...
- 23
1
vote
1
answer
28
views
Optimum placement of zigzag trees in order to minimize the makespan
Suppose we have some trees of the following forms:
We want to place these trees in a linear fashion in a way such that the last node has the minimum distance to the first node. For instance, if we ...
- 53
1
vote
0
answers
22
views
tight lower bounds of parallel machine scheduling with gang scheduling constraint
I am interested in tight bounds for the Parallel Machine scheduling problem with a gang scheduling constraint.
In the notation of Graham, Lawler, Lenstra and Rinnooy Kan, this might be called $Pm|\rm{...
- 17.5k
0
votes
0
answers
27
views
Generalized multiprocessor scheduling with job splitting characteristic
In machine scheduling, lot streaming allows splitting some jobs to minimize the makespan. Following the same idea, Wenxun Xing and Jiawei Zhang in the paper entitled “Parallel machine scheduling with ...
1
vote
2
answers
31
views
Optimize Multiple Agents Completing Multiple Tasks in Parallel
I have an optimization problem and I am wondering if there is a better way to solve it than using a naïve brute force method. I have a number of tasks T that must be completed, and a number of agents ...
0
votes
0
answers
43
views
Can the airline scheduling algorithm (network flow) be extended to handle seating capacities?
The airline scheduling problem determines the minimum number of airplanes required to service a set of passenger flights, where a plane can service routes A$\rightarrow$B and C$\rightarrow$D if there ...
1
vote
1
answer
105
views
Single machine scheduling with profit and deadline constraints
The problem is described as such:
Given $n$ tasks $\{J_1, \ldots , J_n\}$where each task has a deadline and a ‘profit’.
So for some $i \in \{1,\ldots , n\}$, $J_i=\{t_i,p_i\}$ where $t_i$ is the ...
- 316
0
votes
3
answers
92
views
Choices in cpu-scheduling decisions
I'm reading Operating System Concepts by Silberschatz and in chapter 5, there is this text:
1.
CPU-scheduling decisions may take place under the following four
circumstances:
When a process switches ...
1
vote
0
answers
14
views
Algorithm for minimizing the number of resources simultaneously open while iterating through a series of tasks
I have a problem where I'm iterating through a series of tasks and each task requires that a specific file is loaded into memory. The files are not allowed to be unloaded until all of the tasks that ...
- 121
1
vote
1
answer
39
views
Algorithm/heuristic for large tournament matchup pairings
I'm scheduling a large invitational tournament with the following conditions
The event takes place over 8 weeks
Teams arrive and depart on different dates/times, so each day of the event will have a ...
- 113
0
votes
0
answers
57
views
Proof of optimality (and correctness) of greedy algorithm
Unable to come up with a formal proof of optimality for algorithm A for the given problem. Have convinced myself that it is possible to execute some optimal schedule O in increasing order of the ...
- 135
1
vote
1
answer
28
views
A lower bound for the makespan of heterogenous fog nodes
Why there is a sigma in the denominator of equation (8) in the picture? suppose we have n tasks and m fog nodes.
- 25
0
votes
1
answer
60
views
Why there is no user interaction between uni-programming and multi-programming systems?
I was going through my Operating Systems book and in the disadvantages, they wrote that there is no user interaction between the user and computer in uni-programming and multi-programming systems and ...
- 13
1
vote
2
answers
258
views
Topological sort of minimum costs to finish interdependent tasks
The problem that I'm trying to solve goes like this:
A project is split into tasks. Each task takes a known number of days. Some tasks can be done at any time(lets call these simple tasks), others ...
- 125
2
votes
0
answers
93
views
scheduling with profits and deadlines clrs
The following problem is on page 1104 of the CLRS textbook:
I was wondering how to show that the problem is NP-hard (i.e. part b)?
Like subset-sum, this problem is weakly NP-complete; it has a ...
- 207
1
vote
1
answer
35
views
Order List of Sets so Adjacent Sets are Disjoint
Let $n \in \mathbb{N}$ and $G := \{1,2,...,n\}$. Now let $P_2(G)$ be a power set of $G$ but only with sets of cardinality $2$, e.g. if $n = 3$ then $P_2(G) = \{ \{1, 2\}, \{1, 3\}, \{2, 3\} \}$.
Now I'...
- 47
1
vote
0
answers
23
views
Best known approximation for P2|tree;pj=1;Mj|Cmax
I am looking for the best known approximation algorithm for the scheduling problem $P2|tree;p_j=1;M_j|C_{max}$, which to my knowledge is at least $\mathbb{NP}$-hard.
A more elaborate description of ...
- 11
2
votes
0
answers
29
views
Is there a review of lock free priority queues for single consumer multiple producer?
Background
The task I have at hand is to write an event scheduler. From what I understood, it is basically a priority queue which needs to support concurrent insertions and single threaded delete ...
- 121
0
votes
0
answers
128
views
reference that minimum makespan on identical machines is NP-hard?
I need to cite a reference that the minimum makespan problem on ($>2$) identical machines is NP-hard. I've seen Garey and Johnson cited as a reference, but it I'm not sure which of the problems is ...
- 21
1
vote
1
answer
35
views
Textbook proofs for approximation algorithms for scheduling
I am planning to teach approximation algorithms for problems such as job scheduling and number partitioning. I would like to teach proofs, but the proofs I found in the original papers (e.g. this one) ...
- 5,894
0
votes
0
answers
47
views
Incorrect average turnaround time calculated for FCFS schedule?
I am trying to solve the following problem:
If all of the jobs listed below are scheduled FCFS (First Come, First Serve) with no switching overhead, the average turnaround time is going to be:
...
- 213
3
votes
1
answer
777
views
Maximum interval scheduling - Circular Variation
Consider a variant of interval scheduling except now the intervals are arcs on a circle. The goal is to find the maximum number of arcs that do not overlap. Let $C$ be the circle
on the plane centered ...
- 592
7
votes
0
answers
162
views
Finding a rainbow independent set in a circle
Inside the interval $[0,1]$, there are $n^2$ intervals of $n$ different colors: $n$ intervals of each color. The intervals of each color are pairwise-disjoint. A rainbow independent set is a set of $n$...
- 5,894
1
vote
1
answer
31
views
Why does random noise in recurring task periods result in uniform period offsets?
I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten ...
- 699
3
votes
0
answers
13
views
Task scheduling with the constraint of pairs of objects being present in a cache
I'm writing some software that involves processing a large collection of images that are arranged spatially. It basically involves loading pairs of images into caches and computing an operation on the ...
- 131
1
vote
0
answers
44
views
Puzzled by this interview problem of scheduling a computation graph on a single-processor under a memory constraint
I recently went through a interview session for a SWE/CS role at a well known company.
It wasn't specifically a "coding-round" but was titled a "domain interview" session, so I ...
- 151
2
votes
0
answers
41
views
Path that stays within a convex polyhedron
Let $\mathcal{P},\mathcal{Q}$ denote two convex polyhedra in $\mathbb{R}^d$, which can be represented by a set of linear inequalities. Let $A \subset \mathbb{R}^d$ be a finite set of vectors.
The ...
D.W.♦
- 152k
2
votes
1
answer
68
views
Calculating path for most efficient use of consumable items?
What concepts or technologies can help me with the following problem?
You have a finite inventory of resources and a list of recipes to convert a set of resources into another resource (IE "...
- 121
3
votes
0
answers
93
views
How to write a job shop problem with these constraints in alpha|beta|gamma notation?
I have a job shop scheduling problem with the following characteristics. How would I write that in alpha|beta|gamma notation (see 1,2)? I know some of the parts, but not all. I add my suggestions in <...
- 131
1
vote
2
answers
138
views
disadvantages of a long time quantum in scheduling
I'm trying to understand the example showing disadvantages of a long time quantum in Tanenbaum's book in Section 2.4.3 “Scheduling in Interactive Systems”.
To improve the CPU efficiency, we could set ...
- 781
0
votes
1
answer
93
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
1
answer
30
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,728
1
vote
1
answer
48
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 ...
- 5,894
0
votes
0
answers
148
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,...
- 101
2
votes
0
answers
42
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\...
- 225
3
votes
1
answer
742
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-...
- 133
3
votes
1
answer
198
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 ...
- 33
1
vote
1
answer
32
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
0
answers
88
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 ...
- 51
0
votes
0
answers
25
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
1
answer
77
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 ...
- 123
2
votes
1
answer
64
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 ...
- 21
1
vote
0
answers
34
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 ...
- 167
0
votes
0
answers
27
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 ...
- 1
0
votes
0
answers
53
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 ...
1
vote
1
answer
4k
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: ...
- 131
2
votes
0
answers
178
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
0
answers
232
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\...
- 818