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
-1
votes
0answers
13 views

Round Robin (RR) versus Weighted Fair Queuing (WFQ)

I am trying to understand the difference between RR and WFQ. Both of them alternate between classes of packets. But WFQ uses a differential weightage technique. This is given in the book (Network ...
0
votes
1answer
26 views

Grouping n points into groups of size m with objective to have least traveling distance in each group

Assumptions: There are "n" jobs which are distributed over the city. Company has "k" available workers. Each worker can do "x" jobs per day. "x" is dependent to the worker skills and the distance ...
3
votes
1answer
34 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. ...
0
votes
0answers
27 views

Job assignment where each worker handles two non-consecutive jobs

There are $N$ workers and $2N$ jobs, named from $J_1$ to $J_{2N}$. There's a matrix $M$ denoting the subset of jobs can be handled by each worker: If $M_{i, j}$ is true, then worker $i$ can do job $j$....
1
vote
0answers
39 views

coloring of an interval graph with constraints

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
1
vote
1answer
19 views

What is Round Robin's behavior when a process comes at the same time that the old process is swapped out?

Let's say there are two processes: p1 and p2, their arrival time and service time are 0,2 and 3,1 respectively. The time quantum is 2s. After excuting for two seconds, will the processor excute p2 ...
3
votes
1answer
77 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 ...
1
vote
1answer
21 views

How to schedule events optimally given when the events are available?

Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example: $$ \begin{align} \textrm{Event 1} &\rightarrow \textrm{[1, 2, 3]} \\ \textrm{Event 2}...
0
votes
0answers
9 views

How to do Distributed Job Scheduling after the Leader was elected and slaves are known - (bully)

I'm building a system that processes key,value pairs on a continuous basis in a loop, until terminated. How do I schedule tasks on the leader and make slaves execute them? This is a realm of ...
0
votes
1answer
28 views

Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
0
votes
0answers
25 views

In Tomasulo's algorithm, how do reservation stations recognise which results are directed to them, especially where functional units are pipelined?

I am currently researching instruction level parallelism in CPUs and have come across Tomasulo's algorithm for dynamic scheduling. As I understand it so far, once a functional unit computes a result,...
0
votes
1answer
18 views

Scheduling algorithm with defined starting intervals and processing times

I need to design an algorithm for opening and closing some valves at regular times. The input schedule will look something like this: Every 5 minutes, open each of valves 1, 2, and 3 for 5 seconds ...
1
vote
1answer
51 views

Designing a rationing algorithm for a store

Suppose I have a store and I have n units of item x. I want to sell all n units at the end of the day. I do not know how many customers will be coming in today. One customer could theoretically come ...
0
votes
0answers
23 views

Weighted interval scheduling: index out of range

Let's say these jobs are given: where $p$ determines the last not overlapping job. Now I create a Memorization Array $M$ and calculate for every index $j$: $\omega_j + M[p(j)]$ and $M[j-1]$ where $\...
0
votes
1answer
36 views

Difference between greedy and work conserving scheduler for DAG

For both schedulers I have found the definition, that no processor stays idle, if there is more work it can do. However, I found two different upper bounds on the computation time of $T$. For the ...
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 ...
1
vote
0answers
29 views

How to justify using available code (in different language) for comparing algorithms [closed]

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
0
votes
1answer
2k views

How to calculate average waiting time for round robin cpu scheduling?

I have tried to calculate average waiting time for the below details there are two answers I'm getting using two methods I'm not understanding which one is correct? The time quantum is 2 This is the ...
0
votes
0answers
45 views

Interval scheduling with shared resources between steps

I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each ...
1
vote
2answers
266 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
0
votes
1answer
58 views

Calculating minimum processing time for many recipes and tools

I originally asked this question on StackOverflow but a comment was made to the effect that my problem pertains to Job Shop Scheduling and that it was more of a comp sci problem than a programming ...
0
votes
1answer
59 views

How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$. Since the problem ...
0
votes
0answers
129 views

Calculate makespan of job shop solution?

I have a job shop problem with n jobs and m machines, a job shop means that not all jobs have to go through every machine. A job shop problem can be written as such : ...
0
votes
0answers
19 views

Finding an optimal machine assigning

I have $m$ machines and $n$ jobs. Each machine has a load capacity. Each job can be only handled by either one or two machine, and each job takes some time to finish. After it finished, new jobs can ...
0
votes
0answers
8 views

Job shop scheduling variant with non-sequential process plans

As the title says, I am looking for a variant of the job shop scheduling problem which allows for non-sequential process plans. For example, I might have a job whose task-order constraints look like ...
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 ...
0
votes
0answers
175 views

Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below: Regular chores with a start time and end time (a real-...
0
votes
0answers
54 views

A scheduling problem on an oriented graph with multiple constraints

The problem is the following : Data An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a ...
1
vote
1answer
82 views

Approximation ratio of greedy algorithm for makespan

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3. ...
1
vote
1answer
74 views

Can a schedule be conflict serializable but not serializable?

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then, My question is: Can a schedule be conflict serializable but ...
1
vote
0answers
36 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
65 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
28 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
93 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
93 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
29 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
149 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
15 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
34 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
106 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
191 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
34 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
72 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
49 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
3answers
422 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
17 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
64 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
586 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
56 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
294 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 + ...