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.
185
questions
1
vote
0answers
611 views
Task scheduling algorithm (minimize wait time)
Let's say that I have one task to perform $n$, $n<250000$ times and it takes $p$, $p < 700000$ time to complete it once.
I have list of time constraints ${t_1, t_2, ..., t_n}$ where $t_1\le t_2\...
2
votes
1answer
40 views
Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit
I have such a task at university:
we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+...
0
votes
1answer
23 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
1answer
46 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
1answer
47 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 ...
26
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.
...
0
votes
1answer
473 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
15 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
16 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
...
0
votes
1answer
29 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 ...
0
votes
0answers
21 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 $\...
1
vote
2answers
189 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
51 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 ...
4
votes
1answer
104 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 ...
3
votes
1answer
332 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
2answers
267 views
Scheduling / Queuing jobs with multiple different workers
I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system.
Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue).
...
3
votes
1answer
94 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
40 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
129 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 ...
0
votes
1answer
245 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 + ...
0
votes
0answers
87 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
1answer
50 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
18 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 ...
0
votes
0answers
52 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 ...
2
votes
2answers
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 ...
0
votes
0answers
86 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-...
1
vote
1answer
62 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
54 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
35 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
2answers
105 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 (...
1
vote
1answer
42 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
26 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
55 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
27 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 ...
0
votes
0answers
73 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 ...
1
vote
1answer
131 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
13 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
21 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. ...
2
votes
1answer
106 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 ...
0
votes
1answer
56 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
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 ...
1
vote
1answer
36 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 ...
1
vote
1answer
31 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
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
61 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
58 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
vote
1answer
358 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
49 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$ ...
