Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

2
votes
1answer
23 views

Variant of interval scheduling (multiple machines with given availability)

I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks ...
1
vote
0answers
23 views

Sort-of interval scheduling

The Problem I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize... the number of pairwise ...
0
votes
1answer
31 views

Distribute a number of tasks into multiple days (scheduling)

This is about scheduling. I have N tasks of different length and I have to schedule them into M days. Indeed, each day has a max capacity (usually they are the same). Parameters are tight in the sense,...
1
vote
1answer
17 views

Rate Monotonic maximum execution time

There are several periodic tasks (Period, Execution time), e.g.: A = (20, 9) B = (12, 4) C = (4, X) What methods/tests can be used for finding the maximum execution time X for which the task ...
0
votes
0answers
25 views

Scheduling with minimum staffing requirements and preferences

I'm interested in the following scheduling problem: Time is divided in $T$ slots as represented by the left circle below (where $T = 8$). A minimum number of employees $b_t \geq 0$ need to be present ...
0
votes
0answers
13 views

Forming an algorithm for assigning priority weights

I'm trying to develop/research an algorithm in which I can use to assign weighted values (priorities) to a list of jobs that need to be done. I've come up with some kind of arbitrary weights, but I'm ...
1
vote
2answers
36 views

What algorithms are there for scheduling tasks

The scenario is something like this I have tasks that get requested, with a category and a priority For simplicity let's assume that rate of incoming tasks and completion is about the same, with some ...
1
vote
0answers
11 views

Time dependent scheduling with profit

I have a problem. I want to know how to solve this in polynomial time (is it possible?). There are $n$ customers that must be served by single machine. For every customer $C_i$, it has a profit $P_i =...
1
vote
1answer
41 views

Variant of interval scheduling with varying task durations

I am probably just missing the correct term for my problem to find the solution but here it goes: I have a set of tasks with a given duration and an interval for each task in which it has to be ...
0
votes
0answers
19 views

Maximizing benefits of performed tasks by purchasing less reusable devices

Suppose to accomplish a task $t_i$ from a finite task set $T=\{t_1, \ldots, t_n\}$, we need a set of reusable devices $D(t_i) = \{d_1, \ldots, d_m \}$ from a finite device set ${\cal D}$ such that 1) ...
1
vote
1answer
108 views

How does the problem of “Scheduling to Minimize Lateness” exhibit optimal substructure?

The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos): Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ ...
1
vote
0answers
26 views

Dynamic Scheduling Problem

Consider the following setup: Input: An array of tasks $T=[t_1,t_2,...,t_k]$ where each task $t_i$ is an object that has the following features: start time $s,$ finish time $f$ and coordinates $x$ ...
0
votes
1answer
37 views

Find optimal quantum at Round Robin Scheduling algorithm

In this process list situation How can I find the quantum time ( time slice ) at 80% of CPU time ? I found only for 100% of CPU time, so I don't know if it's the same for 80% case B.T.Q= [mean + ...
1
vote
0answers
19 views

Job shop scheduling with events that should be completed simultaneously

I'm working on a scheduling algorithm that schedules a set of events with an event duration to a set of agents with various working times. However, some events require more than one agent to be ...
4
votes
0answers
56 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 ...
0
votes
0answers
16 views

Fixed Job shop problem variation

Given the following constraints: Fixed set of jobs Each job has a fixed start and end time in the example, for r1 it's [0,3], <...
3
votes
1answer
123 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 ...
2
votes
0answers
14 views

Job Shop Problem with dynamic jobs

I've got a problem at hand that's about scheduling tasks to different ressources, basically a simple job shop problem. But: my tasks "branch" dynamically, that is, there are tasks that not only have a ...
0
votes
0answers
13 views

Worst turn around time

This is a question I found in a previous year's exam: Can RR ever be the worst possible CPU scheduling algorithm in terms of turn around time? If so, under what circumstances? I don't quite ...
2
votes
0answers
42 views

Scheduling m independent jobs on n workers to optimize total run time

I have a scenario, in which I have m independent jobs to be schedule on n workers parallely. Time required by each of these jobs ...
0
votes
0answers
36 views

Scheduling in multi core processor

I have an exercise. Let's say we have a system with two computing cores A and B. There are four processes P1(10,A), P2(5,A), P3(13,A), P4(2,B). The number is the next extinction in CPU and the letter ...
0
votes
0answers
35 views

$2$-partition reduction for weighted completion time in scheduling

I've read about the reduction from $2$-partition for the problem of minimizing weighted completion time with release dates but I'm not very experienced in doing reductions so I want to verify that my ...
-1
votes
1answer
60 views

Scheduling Algorithm for Video Player

Background: In a nutshell. I coded a video player application (on linux). I used a proprietary library/API, with this, video and audio frames comes with well defined format. After decoding (via API), ...
0
votes
0answers
10 views

Techniques used in customizing Task Scheduling

I am just learning about Scheduling, in particular the Completely Fair Scheduler. In thinking of specific cases of the types of things that would need to be "prioritized" against each other, there ...
0
votes
0answers
22 views

Algorithms for discrete scheduling problems?

I was wondering what the go-to algorithms are for discrete/combinatorial scheduling problems? An example of the type of problem I'm interested in is optimally routing agents from their starting ...
0
votes
0answers
29 views

Is there any proof that Scheduling with a resource constraint works with two resources?

I've been reading this paper: https://ac.els-cdn.com/S0304397511002623/1-s2.0-S0304397511002623-main.pdf?_tid=bc074517-2b81-4d37-bc92-a5c20dba6b23&acdnat=...
0
votes
1answer
135 views

Does an algorithm exist for scheduling jobs on two processors?

I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found ...
0
votes
0answers
61 views

How to approach solving this variation of the Job Scheduling Problem?

Question: Given N processes with Arrival times and Processing times, calculate and print minimum number of CPUs required if maximum allowed Turnaround time for each process is 10 units. Turnaround ...
1
vote
1answer
157 views

3-SAT reduction to jobs scheduling problem (np-completeness)

In this paper with the title of "NP-Complete Scheduling Problem" by J. D. Ullman, I am trying to understand the reduction from 3-SAT problem to a scheduling problem in order to prove the later is also ...
1
vote
0answers
23 views

Polynomial time algorithm for a simple machine scheduling problem

Think about a setting where there are $n$ tasks and $m$ machines. We are interested in task-machine assignment. Let $p_i$ be a non-negative completion time of job $i$. Also, $x_i$ denotes the machine ...
0
votes
0answers
47 views

3-SAT Reduction to a scheduling problem

In this paper, with title of "NP-Complete Scheduling Problems" by "J. D. ULLMAN", they illustrate a reduction from 3-SAT problem to a scheduling problem that is defined as follows: The relation < ...
3
votes
1answer
79 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 ...
0
votes
0answers
25 views

Scheduling problem with time varying number of machines?

Are there any standard problems in the job scheduling literature where the number of parallel identical machines varies with each time step? I have a problem of scheduling a set of Jobs with defined ...
0
votes
0answers
29 views

Reduction - Scheduling problem

In paper NP-Complete Scheduling Problems,in order to prove that Single execution time scheduling (let's call it p2) is NP-complete, we introduce a slightly more complex problem Single execution time ...
0
votes
0answers
27 views

Polynomial Transformation of one scheduling problem to another

In paper NP-Complete Scheduling Problems,in order to prove that Single execution time scheduling (let's call it p2) is NP-complete, we introduce a slightly more complex problem Single execution time ...
1
vote
0answers
19 views

Scheduling loop

I do not understand how do you write schduled loop from unscheduled one. The unscheduled loop straightforward if you follow the stall rules. The rules say you are supposed to stall after L.D but in ...
0
votes
1answer
33 views

EDF vs Rate Monotonic context changes

I'm studying real time scheduling algorithms. In particular EDF and Rate monotonic. I have an intuition that using EDF we have less context changes than using Rate Monotonic. But i dont know how to ...
0
votes
0answers
32 views

Algorithm to check if exists a valid streaming sequence in O(n)?

Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
0
votes
0answers
13 views

Real time scheduling activation time

I'm studying the real time scheduling of periodic tasks and some algorithms as EDF,Rate Monotonic and Deadline monotonic. In the all the examples i found,if we have tasks $\tau _{1},...,\tau _{n}$, i ...
0
votes
0answers
87 views

Deadline Monotonic vs EDF

The deadline monotonic algorithm is used then the deadline is < of the period of the task. In this case, it's also possible to use EDF , or we can use EDF only for periodic tasks for which the ...
0
votes
0answers
61 views

Utilization Factor, periodic tasks and schedulability

We have 2 periodic tasks that start at the same moment in a monocore processor. Why can happen that, even if the utilization factor is <= 1, the 2 periodic tasks are not schedulable ? For example, ...
2
votes
1answer
154 views

Interval scheduling problem with priorities

I have a problem that is similar to the interval scheduling algorithm but it involves priorities. My data sets consist of the following data: Cars with the start and end time of parking, along with ...
0
votes
0answers
27 views

Difference between local and global instruction scheduling

I am still unaware why would I use global scheduling for the instructions over the local one. From what I know, the difference between the two is, that the local scheduling is performed in the basic ...
1
vote
0answers
54 views

Appropriate algorithm or heuristic for task scheduling

I'm sure this problem has been addressed before, but I'm unable to find an exact description of it. I have $m$ machines, and $n$ tasks that need processing. Each task takes a variable amount of ...
0
votes
0answers
44 views

Scheduling algorithm with waiting time and priority

I have gone through a list of scheduling algorithms and their implementation, however couldn't find any reference to implement an algorithm that solves the following problem. Given an array of ...
1
vote
1answer
102 views

Work-stealing: where and how many to steal

If one ignores the conflicts when accessing the dequeue in Work-Stealing algorithms, does it matter (and in what ways) if one steals from the top or bottom (or anywhere randomly) of the dequeue? Does ...
2
votes
0answers
49 views

long-lived scheduling using max-flow & push/relabel

I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now ...
1
vote
1answer
55 views

What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?

What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty (or randomness of some kind)? What are some examples in which the problems ...
1
vote
1answer
32 views

Find a schedule with lowest total penalty

Given a set of n jobs with [arriving time, service duration time, penalty per unit of time] find a schedule with lowest total penalty. Notes: Arriving time is the time when objects aarivies to ...
0
votes
0answers
83 views

Time Management Scheduling Problem

I am interested in solving a problem related to time management. Suppose you are given $N$ intervals, where the $i$th interval has start time $s_i$ and end time $e_i$, as well as amount $a_i$. Each ...