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
vote
0answers
30 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 ...
1
vote
0answers
41 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 ...
1
vote
0answers
26 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 ...
1
vote
0answers
60 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 ...
1
vote
0answers
627 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\...
1
vote
0answers
68 views

Default scan order in SCAN and LOOK disk scheduling algorithms

I've been learning various disk scheduling algorithms in Operating systems. I wanted to know if there was any default scan order in SCAN, C-SCAN, LOOK and C-LOOK algorithms, like towards higher ...
1
vote
0answers
69 views

Virtualization: overcommitment and vCPU scheduling

I am currently writing a paper about lock-holder preemption with multiprocessors in virtualized enviornment. But I have two questions: one about overcommitment of CPU resources and about scheduling ...
1
vote
0answers
160 views

Job scheduling and packing algorithm

I was thinking about developing a daily production work plan algorithm for an enterprise. The problem is as following: There are various tasks that needs to be completed, each has a deadline, a ...
1
vote
0answers
105 views

Schedule repeating jobs of fixed length and different weights

I have a scheduling problem that I am not sure is a known variant with known algorithms. It does appear like bin packing problem at first, but after imposing the constraints, I am not sure what it ...
1
vote
0answers
113 views

What problems can I reduce Job Shop Scheduling to them [closed]

I want to know which problems are harder than Job Shop Scheduling so I can reduce JSP to them. Sorry I am new to these problems ...
1
vote
0answers
82 views

Reduction of flow-shop scheduling to a real-world computing problem

Consider the following well known flow-shop problem: We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$. Each job $J_i$ consists of a set of operations $...
1
vote
0answers
123 views

Interval scheduling with choice of interval per job

Interval Scheduling problems present several intervals that may overlap and the usual goal is to find the greater set of non overlapping intervals. Variations of the problem on wikipedia and such add ...
1
vote
0answers
231 views

Greedy Algorithm to return multiple optimal solutions

How would one go about enumerating all the optimal answers for interval scheduling? Not sure what to begin with, my guess is to use the other approaches i.e. earliest start time, shortest interval ...
1
vote
0answers
187 views

Integer programming for the courier (goods delivery) scheduling problem

Model: Consider an undirected, weighted, complete graph $G = (V, E = V \times V, w: E \to \mathbb{N}^{+}, r: V \to \mathbb{N}^{+}, d: V \to \mathbb{N}^{+})$. $s \in V$ is a source vertex. $G$ ...
1
vote
0answers
210 views

Optimality of EDF

For Earliest Deadline First, I have read that if utilization is less or equal to 1, the task set is schedulable under EDF. But does this criteria expresses the optimality for EDF? If not, how can we ...
1
vote
0answers
1k views

Algorithm for scheduling timetable for student management system

I am developing the timetable module for a student management system. I am finding it difficult to design/develop it. It can be assumed that a given teacher is capable of teaching any standard whether ...
1
vote
1answer
582 views

Is Starvation Possible in LOOK Algorithm

The LOOK algorithm (wiki) is the same as the SCAN algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any ...
1
vote
0answers
50 views

Approximation for fewest incompatibilities in a scheduling algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
1
vote
0answers
199 views

Solve a basic mutex lock problem while preventing deadlock

I am solving a problem with a bridge, where you have a one way bridge with people coming from each side. To solve this problem while preventing deadlock (two people going opposite directions on the ...
1
vote
1answer
340 views

top k selection in fixed size priority queue with dynamically changing values [duplicate]

My question is something of a scheduling problem. I'd like to know what algorithm to use to find the top k items in a fixed length queue in which the values of the items change dynamically.basically a ...
1
vote
2answers
205 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
723 views

Round-Robin Scheduler - What exactly is the quantum time used for?

Suppose you have three stages for a job: Creation stage = the job gets created Executing stage = the job is executed/served Finishing stage = the job is "marked" as finished. Now, say the quantum ...
0
votes
2answers
131 views

A specific version of a job scheduling problem

I'm looking for a solutions or book references to a given variation of a job scheduling problem: Given $n$ machines (let's denote it by $m_1, m_2, \ldots, m_n$) and $r$ tasks ($t_1, t_2, \ldots, t_r$)...
0
votes
2answers
1k views

Interval Scheduling Problem with Three Resources

So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources. Consider this example interval scheduling problem. Say there ...
0
votes
1answer
315 views

Is there a difference between the name scheduler and scheduling?

Sometimes I read about the term "scheduler" (offline-scheduler, online-scheduler,...) and then I see terms called "scheduling" (offline-scheduling, online-scheduling, preemptive scheduling, non ...
0
votes
1answer
31 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
1answer
51 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
2answers
2k views

Minimum sum of distance from entrance gate

Assumes we have N position, and 3 entrance gate. For example 10 position: 1--2--3--4--5--6--7--8--9--10 For each entrance gate, there is some people waiting to enter and fill positions, first number ...
0
votes
1answer
50 views

What is the best Approximation algorithm to schedule a task graph?

If I have a task graph T and want a schedule to optimize the make-span, what is currently the best approximation algorithm for this problem? Are there any constant approximation algorithms?
0
votes
1answer
370 views

Why can no task have a utilization rate greater than one?

Let $C_i$ be the execution time for task i, $T_i$ be the task period and utilization rate $U = \frac{C_i}{T_i}$ Then $U$ must be less or equal to $1$ for the task to be schedulable Proof: ...
0
votes
1answer
1k views

Algorithm to solve job assignment problem

Can someone suggest an algorithm to solve job assignment problem with condition? With condition means that some jobs cannot be done by some workers. For example table as shown below: In this table x ...
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 ...
0
votes
1answer
57 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
1answer
59 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,...
0
votes
1answer
453 views

Troubles understanding this Interval Scheduling question

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question. Consider the ...
0
votes
1answer
1k views

CPU Scheduling - Round Robin order on ready queue

I am attempting the question below: Assume a set of processes $P_1, P_2, P_3$ and $P_4$ arrive at different times in the ready queue. The table below shows the burst time, the priority (smallest ...
0
votes
1answer
122 views

How to schedule n jobs that come at different times on 1 machine (each taking a different time to complete the task)?

Let's say I have to do n jobs, and each job can be done at or after a time T(i) (1<=i<=n). And we have 1 machine and the machine takes a time M to do any job whatsoever. The machine once started ...
0
votes
1answer
249 views

Round Robin Scheduling: No process in Ready Queue

First post here, glad I found this exchange. I am in my Operating Systems course at university learning process scheduling. In my homework assignment we have to fill out a simulated scheduling chart ...
0
votes
1answer
458 views

Proof NP-Complete for Single machine Job Scheduling Problem specific version

Problem: given a set of n tasks with execution time Ti, due date Di, and a profit Vi (given only if is enden before due date), is there a task schedule that returns a total profit greater or equal ...
0
votes
1answer
1k views

thread scheduling in multi core architecture

In multi core architecture, let us say we have M cores and N threads (N > M) and a process once assigned to a core can't migrate to another core's ready queue. We have to design scheduling policy to ...
0
votes
1answer
420 views

Understanding the P2||CMax scheduling problem

I have a problem with understanding the $P_2 \mid \mid C_\max$ problem which is also known as Tasks Scheduling on Multiple Processors. In fact, in my case I need only one processor (but the problem ...
0
votes
1answer
714 views

Hard disk scheduling - N-set-SCAN vs FSCAN

I'm wondering which is a better scheduling algorithm to use. The only real difference I can see is that in FSCAN there are two queues, and when a scan begins all requests are put in one queue and the ...
0
votes
1answer
118 views

Scheduling optimization problem in theta(n)

I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to ...
0
votes
1answer
82 views

Process scheduling confusion

I've got a confusion in the following section of a book. Here we taking about FCFS Scheduling. I feel that calculation table is incorrect in the book. Because P3 got completed at time 7, it's ...
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
25 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
16 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
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 ...
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 $\...
0
votes
1answer
677 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 ...