# 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.

261 questions
Filter by
Sorted by
Tagged with
27 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 ...
18 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) ...
12 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: ...
105 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 ...
54 views

### Sequential Tasks with Greedy Algorithm

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 therefore only one task can be ...
2k views

### HackerRank August 2021 Coding Challenge - Minimum Time Needed to Finish All Tasks

I was doing the HackerRank Coding Challenge and ran into this problem. I thought through it a bit but wasn't able to come up with a concrete solution, and going through the solution was not very ...
148 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$...
17 views

### Is job shop scheduling J|pij=1|Cmax is still NP complete?

Is the job shop scheduling, where the processing time is 1 time-unit for all operations ($J|p_{ij}=1|C_{max}$), still NP complete or not? Are there any literatures that have a proof?
25 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 ...
11 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 ...
32 views

### Is weighted interval scheduling where the weights are the interval lengths simpler/faster

In weighted interval scheduling arbitrary weights are given to the intervals. A clean dynamic programming solution runs in $O(n \log n)$ time. If the weights of the intervals are their integer lengths,...
38 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 ...
36 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 ...
52 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 "...
35 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 <...
27 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 ...
19 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 ...
25 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 ...
43 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 ...
22 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 ...
56 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,...
38 views

21 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....
22 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 ...
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. ...
104 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 ...
19 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....
65 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 ...
54 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 ...
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. ...
54 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 ...
343 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, ...
43 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 ...