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
2answers
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 ...
0
votes
1answer
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?
3
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
1
vote
0answers
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 ...
5
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
-1
votes
1answer
1k views

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

The question is right there above.
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
27
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
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 ...
0
votes
0answers
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 ...
1
vote
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
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$)...
1
vote
0answers
95 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
101 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
160 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
1answer
372 views

Scheduling N variable-time interdependent tasks across M workers

I have N tasks, each of them requires some time to complete. Time to complete is not the same for all tasks. Each task may depend on a number of other tasks (assume, that no dependency cycles are ...
3
votes
0answers
38 views

Scheduling problem of average sums with condition

Take a multiset $S=\{s_1,\ldots,s_n\} \subset \mathbb{N}$ and some $k \in \mathbb{N}$. Take $T$ to be the set of all sequences of the form $s_{\pi(1)},\ldots,s_{\pi(i)}$, such that $\sum_{j=1}^{i-1} ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
12
votes
2answers
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,...
1
vote
1answer
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?
0
votes
1answer
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?
1
vote
1answer
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 ...
1
vote
1answer
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 ...
4
votes
0answers
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 ...
-1
votes
1answer
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 ...
4
votes
0answers
109 views

job scheduling with deadline and two cascaded machines

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 ...
0
votes
1answer
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, ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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$ ...
1
vote
1answer
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$ ...
4
votes
1answer
4k views

Using dynamic programming to maximize work done

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$ ...
3
votes
2answers
2k views

Find Minimum number of platforms

The questions is as follows with the answer: Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to ...