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

184 questions
Filter by
Sorted by
Tagged with
1k views

### Selling blocks of time slots

Given $n$ time slots that $k$ people want to buy. Person $i$ has a value $h(i,j)\geq 0$ for each time slot $j$. Each person can only buy one consecutive block of time slots, which could be empty. ...
573 views

### How does variance in task completion time affect makespan?

Let's say that we have a large collection of tasks $\tau_1, \tau_2, ..., \tau_n$ and a collection of identical (in terms of performance) processors $\rho_1, \rho_2, ..., \rho_m$ which operate ...
4k views

### Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
396 views

### Is this special case of a scheduling problem solvable in linear time?

Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,...
447 views

### Job scheduling with a bottleneck problem

Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete. Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a ...
248 views

### Ordering elements so that some elements don't come between others

Given an integer $n$ and set of triplets of distinct integers $$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$ find an algorithm which either finds a permutation $\pi$...
556 views

### Find out whose turn it is to buy the croissants

A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The ...
7k views

### Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum. Now I'm not sure if a greedy algorithm will do the trick. That is, sort by ...
229 views

### Can Santa be both fair and efficient?

As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning ...
408 views

### Analyzing load balancing schemes to minimize overall execution time

Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given ...
2k views

### Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...
86k views

### What is the average turnaround time?

For the following jobs: The average wait time would be using a FCFS algorithm: (6-6)+(7-2)+(11-5)+(17-5)+(14-1) -> 0+5+6+10+13 -> 34/5 = 7 (6.8) What would the average turnaround time be?
3k views

### Weighted interval scheduling with m-machines

I am looking for some advice and direction on solving the weighted interval scheduling problem with $m$-machines to plan some experimental "wet lab" procedures. The problem is very similar to the ...
141 views

### Scheduling Algorithm for aperiodic multiprocessor tasks

I've got a System, which is defined as follows: A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the ...
362 views

### Schedule two trains whose tracks overlap so they don't crash

I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve. Recently I was asked this question and did not even know what algorithmic technique to ...
2k views

### Using dynamic programming to maximize work done

Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ ...
703 views

### Schedule tasks from a weighted list with time frame constraints

I'm attempting to create an automatic scheduler from a list of tasks I have available. Here are the key points: Each task has been given a priority beforehand and the algorithm should try to maximize ...
2k views

### Maximum Schedulable Set Zero-Lateness Deadline Scheduling

This is a homework problem for my introduction to algorithms course. Recall the scheduling problem from Section 4.2 in which we sought to minimize the maximum lateness. There are $n$ jobs, each ...
100 views

### Scheduling algorithm to minimize the number of late jobs

There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to ...
454 views

### Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
62 views

### Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...
43 views

### Misunderstanding SS22 Sequencing to Minimize Tardy Tasks

I was reading "COMPUTERS AND INTRACTABILITY. A Guide to the Theory of NP-Completeness", and I am stuck at this part (page 236, SS22): In the second paragraph, 3rd line, the authors said that: "The ...
386 views

### Problems of cyclic executive approach for scheduling of real time systems

I have a doubt on the cyclic executive approach for scheduling on real time systems. From Alan Burns's book Real-time Systems and Programming Languages. This final property represents one of the ...
98 views

Given a set of $N$ jobs and two machines A and B, each machine can process only one job at a time. Each job, if processed, must be processed by machine A before processed by machine B. The processing ...
426 views

### Variation of interval scheduling algorithm with several job categories, only one from each can be used

I have a problem similar to the interval scheduling algorithm. The differences are: The jobs have the same length. There are several categories of jobs and only one job from each category can be ...
161 views

1k views

### Find Minimum number of platforms

The questions is as follows with the answer: Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to ...
143 views

### What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
78 views

### Response time of scheduling a DAG where each vertex is a task

Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to ...
565 views

### Why does lower integer represent higher priority in scheduling literature?

I'm studying Real Time Systems, and in the textbook most of the focus is on scheduling algorithms. (Textbook: Real-Time Systems by Jane W. S. Liu) In the algorithms that involve priorities, it is ...
68 views

### Existence of Real-Time Multiprocessor Schedule

Does an algorithm exist to check for the existence of a Real-Time Multiprocessor Schedule for aperiodic hard tasks(all of which have the same Release time)? Assumptions: The processors are Uniform ...
98 views

### Who was the first to define Flow Shop / Job Shop problem?

I spent some time to search in internet who was the first to formaly define Flow Shop and Job Shop problems but with no effect. I'm especially interested in article/book so I can mention it in my ...
68 views

### How profiling is done in trace scheduling?

I'm trying to understand how trace scheduling works. The book that I'm reading, Engineering a Compiler by Keith D. Cooper & Linda Torczon, states that this method is using profiling. Profiling ...
3k views

### Can Shortest Job First Scheduling be subject to convoy effect?

Look at the below table for example : Look at the Non-Preemptive SJF table Suppose if the burst time of process $P_1$ was a very large number compared to $7$, the processes $P_3,P_2$ and $P_4$ have ...
270 views

### Arranging tasks with specific constraints (scheduling)

I have the following problem: Given a set of tasks and their duration, i need to arrange them taking in consideration some constraints; Here's an example: Suppose we are scheduling talks in a ...