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
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 ...
Sachin's user avatar
  • 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 ...
Matteo Battaglio's user avatar
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 ...
user avatar
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 ...
Freddie's user avatar
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 ...
Sam's user avatar
  • 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 ...
Juraj Fiala's user avatar
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{...
EddieG's user avatar
  • 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 ...
EddieG's user avatar
  • 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 ...
Soroush Vahidi's user avatar
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 ...
Daniel's user avatar
  • 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 ...
matteo_c's user avatar
  • 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 ...
hah's user avatar
  • 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 ...
AustinBest's user avatar
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 ...
Fish_n_Chips's user avatar
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{...
Wandering Logic's user avatar
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 ...
Samuel Bismuth's user avatar
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 ...
MrMiserMeister's user avatar
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 ...
Snowybluesky's user avatar
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 ...
Aishgadol's user avatar
  • 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 ...
saknemelmo's user avatar
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 ...
Erotemic's user avatar
  • 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 ...
Ron M's user avatar
  • 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.
learner's user avatar
  • 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 ...
Octane's user avatar
  • 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 ...
Wolfuryo's user avatar
  • 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 ...
user3472's user avatar
  • 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'...
rn42v's user avatar
  • 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 ...
rxjs's user avatar
  • 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 ...
Incomputable's user avatar
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 ...
dpdp's user avatar
  • 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) ...
Erel Segal-Halevi's user avatar
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: ...
Adam Lee's user avatar
  • 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 ...
AspiringMat's user avatar
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$...
Erel Segal-Halevi's user avatar
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 ...
Jonas Kölker's user avatar
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 ...
BWG's user avatar
  • 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 ...
Joe Black's user avatar
  • 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.'s user avatar
  • 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 "...
Caesar Kabalan's user avatar
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 <...
Peter's user avatar
  • 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 ...
beroal's user avatar
  • 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 ...
Pau Chittaro's user avatar
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 ...
Optidad's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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,...
Kapernski's user avatar
  • 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\...
FeedbackLooper's user avatar
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-...
vvaltchev's user avatar
  • 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 ...
Chenyang's user avatar
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 ...
Fabian Goldschuh's user avatar
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 ...
not.me's user avatar
  • 51

1
2 3 4 5 6