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 about scheduling in operating systems.

1
vote
0answers
31 views

$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost

I have this problem A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
1
vote
1answer
28 views

Matching schedules between users and providers

I have a problem I've been dealing for the past few days, and I'm pretty stuck. Each user has a schedule for a given week, such as ...
0
votes
0answers
19 views

If the string of N requests is repeated many times, which of the following is/are true?

If the string of N requests is repeated many times, which of the following is/are true? I. The fewest page faults occur when M ≥ N. II. LRU (least-recently-used) and FIFO (first-in-first-out) will ...
0
votes
1answer
27 views

Round-Robin fashion exercise

In my Operating Systems class I have an exercise to sketch out how a round-robin algorithm would apply to a specific scenario, which is the following: Now the correction that I was provided with by ...
0
votes
0answers
13 views

Algorithm for Team Meetings scheduling optimization

Consider persons P (about 100) and teams T (ca 20), where each person is member of 2-3 teams. Schedule succession of meetings M of teams where each P can attend and optimize waiting time by running M ...
0
votes
0answers
25 views

Definition of multiprogramming [duplicate]

Which combination of the following features will suffice to characterize an OS as a multi-programmed OS? a. More than one program may be loaded into main memory at the same time for execution b. If ...
1
vote
1answer
112 views

Proccess scheduling arrival time

If I have a set of processes, let's say 9 and I know the burst time and the waiting time for SJF algorithm and also know that processes arrive in groups of 3 processes at M1 moment, M2 moment, M3 ...
1
vote
0answers
11 views

Disk Scheduling for a Fragmented Hard-Drive

Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule I/O requests depending on which ...
0
votes
0answers
17 views

University timetable optimisation - with a twist

I've made a website that helps students at my university optimise their student timetables. Currently, for subjects with not many classes - I can generate and optimise the timetables quite fast. ...
1
vote
2answers
95 views

How to generate an instance for an NP_hard proof, where each element has two inputs?

I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
2
votes
1answer
35 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
27 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
39 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
21 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 ...
1
vote
2answers
45 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
48 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 ...
1
vote
1answer
174 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
28 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
109 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
20 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
17 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
189 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
43 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
40 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
68 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
23 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
30 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
154 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
67 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
180 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
25 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
49 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
82 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
38 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
21 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
36 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
35 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
14 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
104 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
76 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
212 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
36 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 ...