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
0
votes
1answer
4k views

How to calculate average waiting time for round robin cpu scheduling?

I have tried to calculate average waiting time for the below details there are two answers I'm getting using two methods I'm not understanding which one is correct? The time quantum is 2 This is the ...
0
votes
0answers
48 views

Interval scheduling with shared resources between steps

I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each ...
1
vote
2answers
377 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
0
votes
1answer
90 views

Calculating minimum processing time for many recipes and tools

I originally asked this question on StackOverflow but a comment was made to the effect that my problem pertains to Job Shop Scheduling and that it was more of a comp sci problem than a programming ...
0
votes
1answer
84 views

How can I develop a pseudo-polynomial time algorithm for a non-integer problem?

I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta_j$, i.e. the parameter is a real number and $\beta_j \leqslant 0.5, \exists j \in J$. Since the problem ...
0
votes
0answers
724 views

Calculate makespan of job shop solution?

I have a job shop problem with n jobs and m machines, a job shop means that not all jobs have to go through every machine. A job shop problem can be written as such : ...
0
votes
0answers
22 views

Finding an optimal machine assigning

I have $m$ machines and $n$ jobs. Each machine has a load capacity. Each job can be only handled by either one or two machine, and each job takes some time to finish. After it finished, new jobs can ...
2
votes
2answers
93 views

Response time of scheduling a DAG where each vertex is a task

Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to ...
0
votes
0answers
297 views

Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below: Regular chores with a start time and end time (a real-...
0
votes
0answers
57 views

A scheduling problem on an oriented graph with multiple constraints

The problem is the following : Data An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a ...
1
vote
1answer
129 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
155 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
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
1answer
77 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 ...
0
votes
1answer
212 views

Round-Robin fashion exercise

In my Operating Systems class I have an exercise to sketch out how a round-robin algorithm would apply to a specific scenario, which is the following: Now the correction that I was provided with by ...
1
vote
1answer
183 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
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
2answers
108 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 (...
2
votes
1answer
401 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 ...
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 ...
0
votes
1answer
98 views

Distribute a number of tasks into multiple days (scheduling)

This is about scheduling. I have N tasks of different length and I have to schedule them into M days. Indeed, each day has a max capacity (usually they are the same). Parameters are tight in the sense,...
1
vote
1answer
76 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
3answers
998 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
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
1answer
77 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 ...
2
votes
1answer
391 views

Correctness proof for greedy algorithm based on ratio

I've an issue stated as follows: We have 10000 jobs to do, each with some length $l_i$ and weight (importance) $w_i$. Our goal is to arrange the schedule of doing these jobs (in other words, ...
1
vote
1answer
819 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, \...
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$ ...
0
votes
1answer
385 views

Find optimal quantum at Round Robin Scheduling algorithm

In this process list situation How can I find the quantum time ( time slice ) at 80% of CPU time ? I found only for 100% of CPU time, so I don't know if it's the same for 80% case B.T.Q= [mean + ...
1
vote
0answers
36 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 ...
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 ...
3
votes
1answer
570 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 ...
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 ...
0
votes
0answers
74 views

$2$-partition reduction for weighted completion time in scheduling

I've read about the reduction from $2$-partition for the problem of minimizing weighted completion time with release dates but I'm not very experienced in doing reductions so I want to verify that my ...
-1
votes
1answer
99 views

Scheduling Algorithm for Video Player

Background: In a nutshell. I coded a video player application (on linux). I used a proprietary library/API, with this, video and audio frames comes with well defined format. After decoding (via API), ...
0
votes
0answers
46 views

Is there any proof that Scheduling with a resource constraint works with two resources?

I've been reading this paper: https://ac.els-cdn.com/S0304397511002623/1-s2.0-S0304397511002623-main.pdf?_tid=bc074517-2b81-4d37-bc92-a5c20dba6b23&acdnat=...
1
vote
1answer
470 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 ...
2
votes
1answer
54 views

Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit

I have such a task at university: we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+...
1
vote
1answer
786 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
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 ...
3
votes
1answer
124 views

Students in classroom problem - Flow in network

I have room, which is opened some days in week, in different hours each day. I have multiple students, each has time some days in week, in different hours. Each student have to visit the room ...
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 ...
0
votes
0answers
38 views

Algorithm to check if exists a valid streaming sequence in O(n)?

Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 ...
0
votes
0answers
174 views

Utilization Factor, periodic tasks and schedulability

We have 2 periodic tasks that start at the same moment in a monocore processor. Why can happen that, even if the utilization factor is <= 1, the 2 periodic tasks are not schedulable ? For example, ...
2
votes
1answer
389 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 ...
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 ...
0
votes
0answers
110 views

Scheduling algorithm with waiting time and priority

I have gone through a list of scheduling algorithms and their implementation, however couldn't find any reference to implement an algorithm that solves the following problem. Given an array of ...
1
vote
1answer
144 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 ...
2
votes
0answers
105 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 ...