# 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
Filter by
Sorted by
Tagged with
38 views

### Greedy solution for minimum weight where all tasks are allocated

I'm trying to solve exercise 13 from Chapter 04 of Algorithms Design (Eva Tardos) books. The problem is the following: The way I solved: was to have a greedy solution, where I always choose, for an i,...
131 views

### Interval scheduling; sort by ending times

You have $n$ events on your calendar, deﬁned as intervals with a start time $s_i$ and a ﬁnish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$...
1 vote
39 views

### Iteration scheduling vs processor scheduling

In parallel programming the iteration scheduling is defined as the determination of the logical execution time for each loop iteration, while in operating systems, the processor scheduling (FCFS etc) ...
1 vote
27 views

### Schduling theory with weekends and holidays

My wife has a small workshop where she fixes dolls. She works alone without any external help. She has N orders from her clients, she estimates each order and she has deadline for each order. She ...
64 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 vote
63 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 ...
1 vote
666 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 ...
53 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 ...
60 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
44 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
51 views

• 17.8k
1 vote
201 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 ...
1 vote
235 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 ...
• 355
133 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
16 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 ...
• 123
1 vote
46 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
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
138 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
395 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
130 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
41 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
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
45 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
221 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
59 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) ...
• 6,132
83 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
2k 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 ...
• 613
171 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$...
• 6,132
1 vote
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 ...
• 729
20 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
47 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
44 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 ...
• 162k
73 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 "...
108 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
599 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
207 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 ...
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,788
1 vote
54 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 ...
• 6,132
201 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