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
1answer
424 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
39 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 ...
3
votes
1answer
93 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 ...
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 ...
0
votes
1answer
44 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
36 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
125 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
322 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 ...
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 ...
0
votes
0answers
71 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
109 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
73 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
57 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
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 ...
2
votes
1answer
68 views

Existence of Real-Time Multiprocessor Schedule

Does an algorithm exist to check for the existence of a Real-Time Multiprocessor Schedule for aperiodic hard tasks(all of which have the same Release time)? Assumptions: The processors are Uniform ...
0
votes
1answer
600 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<=...
0
votes
0answers
274 views

Round-Robin schedule: process A's time quantum expires at the same time as a process B arrives. What happens next?

Let's assume we are to implement a Round-Robin algorithm. What will happen in a case when a process has completed it's time quantum at the same time as another process arrives. Let's say we have a ...
1
vote
0answers
64 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 ...
0
votes
0answers
167 views

List of scheduling problems and their statuses

As of 1993, there are 4536 scheduling problems, 3821 were proven to be $NP$-hard, 417 polynomially solvable, and 298 still open. Where can I find the most up-to-date list of scheduling problems and ...
0
votes
1answer
394 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 ...
2
votes
2answers
252 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). ...
1
vote
1answer
367 views

Interval schedule maximization when encountering intervals with equivalent end points

In interval scheduling, the greedy solution which maximizes the schedule that contains the largest number of "compliant intervals" involves initially sorting the list of intervals in ascending order ...
0
votes
0answers
874 views

What algorithm does OLA and UBER use for allotting taxis

More specifically : lets say i have 5 taxis , each available for booking at t=0; i have two days (48 hrs) with me how can I maximise their booking . I may not be able to clarify the question , this ...
2
votes
0answers
34 views

Static management of dynamic memory

I have some issue but I can't identify a way to solve it. I wanted to ask you what kind of problem it is? We have a resource - contiguous computer memory. Also we have users which require some ...
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
49 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?
3
votes
1answer
57 views

Lower bound on competitive ratio of $m$-machine scheduling

Given a sequence of positive reals $a_1, a_2, \dots, a_n$ and an integer $m$, for each $j$ assign $a_j$ to a machine $i$, $1< i < m$, so as to minimize the maximum, over $i$, of the sum of all ...
1
vote
0answers
63 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 ...
0
votes
0answers
44 views

Minimize Burst time left in CPU Scheduling in a fixed interval of time

I have $P$ different processes given along with their respective Burst time and arrival time. The time quantum is $1$ sec i.e. each process can only run for $1$ sec. There's a total time $F$ given for ...
0
votes
0answers
14 views

Scheduling problem with performance based selection

I would like to solve a scheduling problem where, I am able to maximize the number of consecutive shifts a employee may have, therefore minimizing the likelihood of them not showing up for a single, ...
1
vote
0answers
143 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 ...
3
votes
1answer
7k views

Disk scheduling algorithm - SCAN and C-SCAN

I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a ...
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 ...
1
vote
0answers
103 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 ...
4
votes
0answers
43 views

Misunderstanding SS22 Sequencing to Minimize Tardy Tasks

I was reading "COMPUTERS AND INTRACTABILITY. A Guide to the Theory of NP-Completeness", and I am stuck at this part (page 236, SS22): In the second paragraph, 3rd line, the authors said that: "The ...
0
votes
1answer
121 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
240 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 ...
-1
votes
1answer
404 views

Best way to schedule jobs so as to get minimum average turnaround time [closed]

The question is right there above.
0
votes
1answer
452 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 ...
-1
votes
1answer
83 views

Which scheduler uses scheduling algorithm?

From what I know, the high level scheduler decides which process is to be taken from backing store and placed into memory/ready queue, while the low level scheduler decides which process in the ready ...
2
votes
0answers
40 views

Identify common mathematical problem behind my task in scheduling area

Having single operator, which could do work and it's time of availability - for example from 8 am till 9 pm. And operator have limited resource - let's call it ...
0
votes
0answers
30 views

Calculating the process time for a synchronous network system

Okay I am trying to understand why asynchronous systems are better that synchronous systems in terms of throughput. Relating to the calculation done in this answer. Can someone tell if my reasoning ...
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. ...
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 ...
0
votes
0answers
287 views

Interval scheduling, unclear greedy proof

I am having trouble understanding the proof of the theorem, which states that the greedy scheduling algorithm produces solutions of maximum size for the scheduling problem. The proof that I am ...
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
2answers
127 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$)...
1
vote
0answers
77 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 $...
0
votes
0answers
89 views

Job Scheduling: Two Resources, Defined Job Length, Defined Earliest Start

Problem I stumbled over the following job scheduling problem. There are two resources, for simplicity I call them ... CPU_RAM (MAX_CPU_RAM specifies what is available in total) GPU_RAM (MAX_GPU_RAM ...
1
vote
0answers
122 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 ...