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.

99 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
79 views

Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...
4
votes
0answers
436 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 ...
4
votes
0answers
101 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 ...
4
votes
0answers
456 views

Variation of interval scheduling algorithm with several job categories, only one from each can be used

I have a problem similar to the interval scheduling algorithm. The differences are: The jobs have the same length. There are several categories of jobs and only one job from each category can be ...
3
votes
0answers
37 views

I'ld like a better algorithm for scheduling tutors to fill a set of shifts

My problem is as follows: I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room A on M, W, F from 9-11am and Sa from 12-3 pm. ...
3
votes
0answers
41 views

Scheduling is NP-Hard via vertex cover

Are there any existing proofs involving a reduction of the single machine scheduling problem (in any of its forms really) from vertex cover in order to prove its NP-hardness? Particularly looking for ...
3
votes
1answer
595 views

Task calendar scheduling algorithm

I want to write a scheduling algorithm for the following scenario: There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is ...
3
votes
0answers
44 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 ...
3
votes
0answers
37 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} ...
3
votes
0answers
145 views

What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
2
votes
1answer
34 views

Greedy algorithm for job scheduling

Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime. How to prove that this algorithm has an approximation ratio of ...
2
votes
1answer
73 views

Schedule X Classes In N Classrooms

I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...) I am really out of thoughts I have X number of classes ...
2
votes
0answers
24 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
44 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
0answers
107 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
384 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
36 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
61 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
81 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
602 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
717 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
19 views

Optimal Selection of Non-Overlapping Jobs

I'm trying to find what the family of problem is - as well as an approach - for the following: I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri. Each task ...
1
vote
0answers
18 views

Understanding proofs Lemma 11 & 10 in this specific Computer Science Scheduling Paper

I'm having a hard time wrapping my head around the proofs Lemma 11 and Lemma 10 (Pages 10 and 11) in this paper called: Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling. Generally the ...
1
vote
0answers
24 views

“Job” scheduling with skill restrictions

I was given this real life problem and was asked if there would be a way to optimize this, I realize that this is akin to a job scheduling problem, but I can't seem to grasp how to make it work with ...
1
vote
0answers
14 views

Shortest sequence of jobs, with dependencies, subject to capacity constraints

Suppose I have $n$ courses, some with some prerequisites, and I can take up to $k$ courses in a semester. I want to compute the least number of semesters needed to complete all courses, while ...
1
vote
0answers
23 views

Unconditionally fair, weakly fair, and strongly fair scheduling

I am trying to understand the difference between weakly fair and strongly fair scheduling. For example, what scheduling policy would ensure that a process delayed at its first await statement will ...
1
vote
0answers
15 views

Criteria based estimation of a task's due date

Basically we have a ticket system, each day we get multiple tickets with different categorization (Question,Change,Error) and importance (High,Mid,Low) for different customers (A,B,C). My job is to ...
1
vote
0answers
17 views

How do programs like Apache Airflow/ Luigi determine shortest path and how does that relate to graph theory?

I am looking for a simple layman's term explanation on how do programs like Apache Airflow or Luigi (or any Task/ETL schedulers) determine the shortest path to complete a certain task and make it ...
1
vote
0answers
43 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
58 views

Designing a rationing algorithm for a store

Suppose I have a store and I have n units of item x. I want to sell all n units at the end of the day. I do not know how many customers will be coming in today. One customer could theoretically come ...
1
vote
0answers
41 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
0answers
19 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
37 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 ...
1
vote
0answers
21 views

Time dependent scheduling with profit

I have a problem. I want to know how to solve this in polynomial time (is it possible?). There are $n$ customers that must be served by single machine. For every customer $C_i$, it has a profit $P_i =...
1
vote
0answers
63 views

Dynamic Scheduling Problem

Consider the following setup: Input: An array of tasks $T=[t_1,t_2,...,t_k]$ where each task $t_i$ is an object that has the following features: start time $s,$ finish time $f$ and coordinates $x$ ...
1
vote
0answers
37 views

Job shop scheduling with events that should be completed simultaneously

I'm working on a scheduling algorithm that schedules a set of events with an event duration to a set of agents with various working times. However, some events require more than one agent to be ...
1
vote
0answers
47 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 ...
1
vote
0answers
29 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 ...
1
vote
0answers
71 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 ...
1
vote
0answers
773 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\le t_2\...
1
vote
1answer
92 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 ...
1
vote
0answers
106 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 ...
1
vote
0answers
231 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 ...
1
vote
0answers
107 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 ...
1
vote
0answers
92 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 $...
1
vote
0answers
145 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
0answers
254 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 ...
1
vote
0answers
214 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$ ...