The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
2
votes
1answer
186 views

Scheduling Problem Optimisation using LP solvers

I am currently working on a scheduling system which schedules individuals based on timeslots that have the following attributes: (1) Day of Week (2) Month (3) Session(AM/PM). The individuals ...
2
votes
2answers
173 views

Heuristic for Tournament Scheduling

I am holding a bi-yearly tournament in my city, for which I want to write a program that gives me (nearly-)optimal pairings, and waiting time. The setup is as follows: ...
2
votes
1answer
969 views

task scheduling optimization problem

I'm interested in such problem. I have a set of $n$ tasks ${T_i}$ and directed acyclic graph, which nodes correspond to tasks and edges correspond to order of execution two tasks. In other words if I ...
2
votes
1answer
88 views

Algorithm for finding optimal branch points

I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd ...
2
votes
1answer
132 views

Variant of interval scheduling (multiple machines with given availability)

I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks ...
2
votes
0answers
18 views

Job Shop Problem with dynamic jobs

I've got a problem at hand that's about scheduling tasks to different ressources, basically a simple job shop problem. But: my tasks "branch" dynamically, that is, there are tasks that not only have a ...
2
votes
0answers
43 views

Scheduling m independent jobs on n workers to optimize total run time

I have a scenario, in which I have m independent jobs to be schedule on n workers parallely. Time required by each of these jobs ...
2
votes
1answer
338 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 ...
2
votes
0answers
78 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 ...
2
votes
2answers
296 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). ...
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 ...
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 ...
2
votes
0answers
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 ...
2
votes
0answers
72 views

Activity scheduling with activities that can move around

In this problem. I have a set of "activities" which can happen. Each "activity" is associated with several values: Duration: The length of time the activity takes Earliest time to start: The earilest ...
2
votes
0answers
73 views

Optimize sequence when item costs are interdependent

I'm tempted to phrase this question notationally, but I may be jumping the gun on the exact problem definition as well. So let me start with the real-world scenario and work forward from there. You'...
2
votes
0answers
570 views

Job scheduling problem in O(n log n)

There are $n \leq 10^6$ kinds of cake layers, and for each kind we have a machine capable of baking it in one unit of time and nothing more. Now, a cake is a sequence of layers, more specificly a ...
2
votes
0answers
688 views

Single machine job scheduling (Greedy heuristic)

Here is a variation of a job-scheduling Problem. Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge ...
1
vote
1answer
287 views

Does an algorithm exist for scheduling jobs on two processors?

I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found ...
1
vote
1answer
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 ...
1
vote
1answer
147 views

Designing a scheduling algorithm

I have only intro CS under my belt, so I'm looking for some fast advice. I want to write a scheduling algorithm for the following scenario. I have customers who have selected how many hours they want ...
1
vote
3answers
248 views

What algorithms are there for scheduling tasks

The scenario is something like this I have tasks that get requested, with a category and a priority For simplicity let's assume that rate of incoming tasks and completion is about the same, with some ...
1
vote
1answer
478 views

How does the problem of “Scheduling to Minimize Lateness” exhibit optimal substructure?

The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos): Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ ...
1
vote
1answer
453 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
1answer
115 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 ...
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
37 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 ...
1
vote
1answer
293 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 ...
1
vote
1answer
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?
1
vote
1answer
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 ...
1
vote
1answer
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$ ...
1
vote
1answer
504 views

NP-completeness of scheduling to minimise tardy tasks with release times

In "Computers and Intractability A Guide to the Theory of NP-Completeness" textbook pp 236, "Sequencing to minimize tardy tasks" is NP-complete. To be specific the problem is as follows: For each ...
1
vote
1answer
19 views

How to schedule events optimally given when the events are available?

Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example: $$ \begin{align} \textrm{Event 1} &\rightarrow \textrm{[1, 2, 3]} \\ \textrm{Event 2}...
1
vote
1answer
72 views

Approximation ratio of greedy algorithm for makespan

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3. ...
1
vote
1answer
57 views

Can a schedule be conflict serializable but not serializable?

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then, My question is: Can a schedule be conflict serializable but ...
1
vote
1answer
53 views

Matching schedules between users and providers

I have a problem I've been dealing for the past few days, and I'm pretty stuck. Each user has a schedule for a given week, such as ...
1
vote
2answers
105 views

How to generate an instance for an NP_hard proof, where each element has two inputs?

I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (...
1
vote
1answer
37 views

Rate Monotonic maximum execution time

There are several periodic tasks (Period, Execution time), e.g.: A = (20, 9) B = (12, 4) C = (4, X) What methods/tests can be used for finding the maximum execution time X for which the task ...
1
vote
1answer
62 views

Variant of interval scheduling with varying task durations

I am probably just missing the correct term for my problem to find the solution but here it goes: I have a set of tasks with a given duration and an interval for each task in which it has to be ...
1
vote
1answer
411 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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
121 views

How can OS schedule disk requests efficiently without knowing the LBN to PBN mapping ?

I learn from the OS schoolbook that the OS has the function that schedule the disk requests with the knowing algorithms such as SSTF, SCAN .. However, the date layout inner disk drives now is very ...
1
vote
1answer
3k views

Interval Scheduling Problem with more than One Resource

Consider the interval scheduling problem, see also here. In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest ...
1
vote
0answers
36 views

coloring of an interval graph with constraints

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
1
vote
1answer
18 views

What is Round Robin's behavior when a process comes at the same time that the old process is swapped out?

Let's say there are two processes: p1 and p2, their arrival time and service time are 0,2 and 3,1 respectively. The time quantum is 2s. After excuting for two seconds, will the processor excute p2 ...
1
vote
0answers
29 views

How to justify using available code (in different language) for comparing algorithms [closed]

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
1
vote
0answers
35 views

$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost

I have this problem A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
1
vote
1answer
145 views

Proccess scheduling arrival time

If I have a set of processes, let's say 9 and I know the burst time and the waiting time for SJF algorithm and also know that processes arrive in groups of 3 processes at M1 moment, M2 moment, M3 ...
1
vote
0answers
14 views

Disk Scheduling for a Fragmented Hard-Drive

Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule I/O requests depending on which ...
1
vote
0answers
34 views

Sort-of interval scheduling

The Problem I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize... the number of pairwise ...