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

192 questions
Filter by
Sorted by
Tagged with
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. ...
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 ...
324 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 ...
132 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$)...
82 views

243 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 ...
57 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 ...
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 ...
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 ...
87 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 ...
100 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 ...
139 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 ...
400 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,...
97 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?
129 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?
239 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 ...
97 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 ...
406 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 ...
248 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 ...
100 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 ...
270 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, ...
429 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 ...
129 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 ...
189 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$ ...
21 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$ ...
2k 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$ ...
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 ...
60 views

### Algorithm to collect items before they expire

I thought about the following problem: There are goods $\mathbb{G} = (g_1, \dots, g_k)$ on the line. Coordinates are expressed in meters and sorted in increasing order. All goods have different ...