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.
278
questions
0
votes
1
answer
30
views
3 Processor Scheduling
A set of n independent tasks, each having integer execution times,
are to be executed using three identical processors. A task can be
executed in any of the three processors. Develop a sequential
...
- 1
0
votes
1
answer
36
views
Round-robin tournament scheduling, with teams that may share their home field
I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
0
votes
1
answer
210
views
Showing this scheduling problem is NP-hard
I've been reading up on scheduling problems and the class of them that is NP-complete. Specifically, this is a foundational text on such problems, but the reductions are not clear to me. Can someone ...
user163952
0
votes
1
answer
31
views
Should I use linear programming for my timetable generator?
I am creating a timetabling software for a school, which given parameters for teachers/class sizes will output a timetable. There will be a list of classrooms per subject and a list of teachers per ...
- 1
0
votes
0
answers
38
views
Minimize overlap in class schedule
At our school, we have a schedule that looks like the following (simplified):
Remarks:
One course can be taught multiple times a week (to different class-groups, like 1A, 1B and 2A)
Multiple lessons ...
- 11
0
votes
0
answers
42
views
Chore schedule with fair distribution of pairs and groups
I need to build a schedule that maps 7 people to 4 groups (3 pairs, 1 single) for each week.
An ideal schedule would be one where each person swaps pairs and groups in a round-robin style. If such a ...
- 101
0
votes
1
answer
38
views
Weighted interval scheduling on K-identical machines --- approximation factor
This is a follow-up for Weighted interval scheduling with m-machines ---greedy solution with approximation factor.
As suggested by @D.W., I will present the problem more comprehensively.
$\textbf{...
- 11
1
vote
1
answer
55
views
Weighted interval scheduling with m-machines ---greedy solution with approximation factor
Weighted interval scheduling with m-machines
('Weighted interval scheduling with m-machines')
I encountered the problem of weighted interval scheduling on m identical machines (as discussed in the ...
- 11
1
vote
0
answers
29
views
Scheduling jobs with the same release time and different due dates on a single machine
Consider the problem of scheduling jobs with different lengths on a single machine while the jobs have the same release times and different due dates. The goal is to schedule the maximum number of ...
0
votes
0
answers
30
views
Worst Case Response Time (WCRT) analysis the only necessary test for real time tasks?
Recently, I have taken a Computer Science exam for the course Operating Systems. One question was as follows:
Which statements about real-time operating systems are true?
I selected two options, but ...
- 1
0
votes
1
answer
46
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
280
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
72
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
30
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 ...
- 153
1
vote
0
answers
24
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.7k
0
votes
0
answers
29
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 ...
- 127
1
vote
2
answers
80
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
69
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
181
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 ...
- 315
0
votes
3
answers
111
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
15
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
42
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
1
vote
1
answer
32
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
110
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
304
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
111
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
37
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
36
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
171
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
45
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,730
0
votes
0
answers
71
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
941
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 ...
- 593
7
votes
0
answers
166
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,730
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 ...
- 709
4
votes
0
answers
17
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 ...
- 141
1
vote
0
answers
46
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
42
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.♦
- 156k
2
votes
1
answer
69
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
101
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
401
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 ...
- 791
0
votes
1
answer
122
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
31
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,758
1
vote
1
answer
51
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,730
0
votes
0
answers
186
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
43
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
910
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
258
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
35
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
100
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