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
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 ...
matteo_c's user avatar
  • 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 ...
hah's user avatar
  • 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 ...
AustinBest's user avatar
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 ...
Fish_n_Chips's user avatar
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{...
Wandering Logic's user avatar
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 ...
Samuel Bismuth's user avatar
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 ...
MrMiserMeister's user avatar
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 ...
Snowybluesky's user avatar
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 ...
Aishgadol's user avatar
  • 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 ...
saknemelmo's user avatar
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 ...
Erotemic's user avatar
  • 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 ...
Ron M's user avatar
  • 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 ...
Ajax's user avatar
  • 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.
learner's user avatar
  • 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 ...
Octane's user avatar
  • 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 ...
Wolfuryo's user avatar
  • 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 ...
user3472's user avatar
  • 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'...
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
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 ...
Incomputable's user avatar
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 ...
dpdp's user avatar
  • 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) ...
Erel Segal-Halevi's user avatar
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: ...
Adam Lee's user avatar
  • 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 ...
AspiringMat's user avatar
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$...
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
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 ...
BWG's user avatar
  • 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 ...
Joe Black's user avatar
  • 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.'s user avatar
  • 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 "...
Caesar Kabalan's user avatar
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 <...
Peter's user avatar
  • 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 ...
beroal's user avatar
  • 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 ...
Pau Chittaro's user avatar
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 ...
Optidad's user avatar
  • 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 ...
Erel Segal-Halevi's user avatar
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,...
Kapernski's user avatar
  • 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\...
FeedbackLooper's user avatar
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-...
vvaltchev's user avatar
  • 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 ...
Chenyang's user avatar
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 ...
Fabian Goldschuh's user avatar
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 ...
not.me's user avatar
  • 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, ...
Aaron Casey's user avatar
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 ...
Micrified's user avatar
  • 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 ...
bigCSm8's user avatar
  • 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 ...
EvaMGG's user avatar
  • 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 ...
asdfasdf's user avatar
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 ...
Muhammad Salman Ali's user avatar
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: ...
Vinay Yadav's user avatar
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 ...
Paweł Chorążyk's user avatar
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\...
xdavidliu's user avatar
  • 818

1
2 3 4 5 6