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
27
votes
2answers
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. ...
16
votes
2answers
576 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 ...
13
votes
1answer
5k 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 ...
12
votes
2answers
404 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,...
11
votes
2answers
460 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 ...
10
votes
2answers
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$...
9
votes
3answers
564 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 ...
8
votes
4answers
8k 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 ...
8
votes
1answer
232 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 ...
7
votes
1answer
414 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 ...
6
votes
1answer
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, ...
6
votes
5answers
94k 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?
6
votes
1answer
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 ...
6
votes
1answer
147 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 ...
5
votes
2answers
372 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 ...
5
votes
0answers
44 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 ...
4
votes
1answer
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$ ...
4
votes
2answers
730 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 ...
4
votes
1answer
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 ...
4
votes
1answer
116 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 ...
4
votes
1answer
484 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 ...
4
votes
0answers
72 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 ...
4
votes
0answers
416 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 ...
4
votes
0answers
101 views

job scheduling with deadline and two cascaded machines

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 ...
4
votes
0answers
447 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 ...
3
votes
1answer
33 views

Scheduling task optimization

I have the acyclic directed graph of tasks I want to perform. Each edge of the graph is a dependency, e.g. task 4 could be performed only after 1 and 2 completed. ...
3
votes
1answer
163 views

NP-hardness of a scheduling problem

Problem: Given an undirected, weighted, complete graph $G = (V, E, w, c)$. $w$ is the time weight function on edges, $w:E \to \mathbb{N}^{+}$; $w(e)$ represents the time it takes to travel along edge $...
3
votes
2answers
2k views

Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler

Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are ...
3
votes
1answer
204 views

Single machine job scheduling

Given $n$ jobs, schedule them such that the weighted sum is minimum. weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by : $S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
3
votes
1answer
231 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
3
votes
1answer
74 views

DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

Problem In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has ...
3
votes
1answer
67 views

Lower bound on competitive ratio of $m$-machine scheduling

Given a sequence of positive reals $a_1, a_2, \dots, a_n$ and an integer $m$, for each $j$ assign $a_j$ to a machine $i$, $1< i < m$, so as to minimize the maximum, over $i$, of the sum of all ...
3
votes
1answer
988 views

Time quantum assignment to processes

In a book I am reading it is stated that an input/output intensive process should receive a higher time quantum whereas a computing intensive process on the other hand should receive a lower one. Here ...
3
votes
1answer
574 views

A variant of job assignment (scheduling) problem with variable time span

The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take ...
3
votes
1answer
252 views

Minimize the total execution time of jobs executed by 3 processors in sequence

There are 3 processors: $P_1$, $P_2$, $P_3$. $P_1$ can execute only one job while the other two can execute any number of jobs in parallel. Each job consists of 3 parts, and each part is processed by ...
3
votes
1answer
102 views

Students in classroom problem - Flow in network

I have room, which is opened some days in week, in different hours each day. I have multiple students, each has time some days in week, in different hours. Each student have to visit the room ...
3
votes
1answer
9k views

Disk scheduling algorithm - SCAN and C-SCAN

I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a ...
3
votes
2answers
111 views

Scheduling a tournament with variable game lengths

I want to solve the following scheduling problem: We have $N$ resources and $\binom{N}{2}$ tasks, such that every task requires exactly two resources and every pair of resources is required by exactly ...
3
votes
1answer
105 views

Offline scheduling fully determined arbitrary jobs in multiprocessor setting

Let $\mathcal{J} = \{J_1,...,J_n\}$ be a set of jobs with each $J_i = [a_i,r_i,d_i]$ where the job becomes available at its arrival time $a_i$, requires $r_i$ execution time and needs to be finished ...
3
votes
1answer
416 views

Task calendar scheduling algorithm

I want to write a scheduling algorithm for the following scenario: There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is ...
3
votes
0answers
37 views

Scheduling problem of average sums with condition

Take a multiset $S=\{s_1,\ldots,s_n\} \subset \mathbb{N}$ and some $k \in \mathbb{N}$. Take $T$ to be the set of all sequences of the form $s_{\pi(1)},\ldots,s_{\pi(i)}$, such that $\sum_{j=1}^{i-1} ...
3
votes
2answers
2k 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 ...
3
votes
0answers
144 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 ...
2
votes
2answers
87 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 ...
2
votes
3answers
629 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 ...
2
votes
1answer
71 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 ...
2
votes
1answer
102 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 ...
2
votes
1answer
69 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 ...
2
votes
1answer
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 ...
2
votes
1answer
275 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 ...