# 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.

260 questions
Filter by
Sorted by
Tagged with
3k 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 ...
66 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?
100 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 ...
124 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 ...
60 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 ...
15 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, ...
249 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 ...
12k 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 ...
2k 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 ...
116 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 ...
45 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 ...
132 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 ...
457 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 ...
1k views

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

The question is right there above.
616 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 ...
125 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 ...
41 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 ...
32 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 ...
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. ...
127 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 ...
394 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 ...
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 ...
163 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$)...
95 views

279 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 ...
68 views

### Explanation of pilot jobs in distributed/grid computing

I'm reading into grid systems/distributed systems and came across pilot jobs that I can't find a decent explanation for. The wikipedia page is not understandable to me. I know multi-level schemes ...
2k 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 ...
49 views

### How to schedule different elements in a 24h range?

Given the following conditions: An element has: A time range, for example: 9:00 to 18:00. A repeat time, for example: every 5 minutes. Then a device recieves some elements and has to schedule them ...
92 views

### Parallel Machine Scheduling test data

I am writing optimization program for unrelated parallel machine scheduling problem on CUDA. Now, the only thing I am missing are some test cases. Does anyone know where I can find such data? I have ...
110 views

### Who was the first to define Flow Shop / Job Shop problem?

I spent some time to search in internet who was the first to formaly define Flow Shop and Job Shop problems but with no effect. I'm especially interested in article/book so I can mention it in my ...
170 views

### How does Logical Block Addressing affect OS disk scheduling optimizations such as SCAN (Elevator Algorithm)?

If the OS is scanning from one edge of the disk to the other, doing so from behind the Logical Block Addressing (LBA) abstraction, although it may aim to service requests in an elevator-like way, what ...
515 views

### Is this special case of a scheduling problem solvable in linear time?

Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,...
119 views

### How to choose waiting process in a preemptive priority-based scheduler

If my CPU schedule is preemptive priority, and I have no new processes coming, how I should choose from the waiting processes?
322 views

### Rate Monotonic First Fit vs. Rate Monotonic Next Fit vs. Proportionate Fair

What would an example of a set of tasks be, where RMFF, RMNF and P-Fair all result in a different number of processors required?
332 views

### How and which component of an Operating System is responsible for the transition of a process from the blocked state to the ready queue?

A process in an Operating System is considered to occupy several states and a process transitions between these states. A scheduler is responsible for assigning CPU time to a process. However, a ...
114 views

### Distributed parallel computing algorithms for content dependent data

I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel ...
464 views

### Problems of cyclic executive approach for scheduling of real time systems

I have a doubt on the cyclic executive approach for scheduling on real time systems. From Alan Burns's book Real-time Systems and Programming Languages. This final property represents one of the ...
488 views

### Are there any papers published proving how University Time Table Scheduling Problem is NP-Complete?

I have been researching on finding optimal solutions to generating University Time Table using Genetic Algorithm. I am searching for a Academic Paper, that properly defines the University Time Table ...
109 views

Given a set of $N$ jobs and two machines A and B, each machine can process only one job at a time. Each job, if processed, must be processed by machine A before processed by machine B. The processing ...
482 views

### Scheduling problem on bipartite graph

Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
668 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 ...
135 views

### Scheduling distributed computational graph

I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete. The common way to improve simulation performance is to use a suitable distributed linear ...
237 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$ ...
22 views

### How to understand the mathematical constraint of potentials?

Good evening! I am studying scheduling problems and I have some difficulties understanding constraints of potentials: Let be $t_j$ the time when a task $j$ starts, and $t_i$ the time when a task $i$ ...
Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ ...