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

245 questions
Filter by
Sorted by
Tagged with
492 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. ...
251 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 ...
308 views

### Questions regarding CPU scheduling algorithms ( Round Robin and Priority scheduling )

Consider the following processes : 1) My First Question is if we need to schedule them using preemptive priority scheduling with Round-Robin for equal processes priorities with a quantum of 3. Here ...
28 views

### Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases

I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v_1, v_2)$ signifies, that tasks $v_1$ and $v_2$ can ...
746 views

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 ...
490 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). ...
86 views

### A task-scheduling problem as a matroid (CLRS book)

I don't understand very well section 16.5 of the 3rd edition of the famous Introduction to Algorithms book, known as CLRS. It defines the problem of scheduling unit-...
485 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 + ...
60 views

### CPU scheduling Decisions

Operating System - CPU scheduling Decisions The question above talks about why CPU scheduling does not take place when ready to running. But I wonder why CPU scheduling does not take place when new ...
39 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 ...
40 views

### 2-Dimensional interval scheduling problem

I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format: Cars with the start and ...
86 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 ...
20 views

### Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?

Intro The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its ...
14 views

### Scheduling Repeating, Flexible Intervals with Restrictions on Overlap

I work in 52:17 work:break intervals, as there's some evidence showing it's an effective way to structure the day. However, meetings or planned breaks often require shifting that schedule, moving, ...
67 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 ...
12 views

### Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment. Say that ...
28 views

### Cyclic finite scheduling algorithm

I have a scheduling problem with the following specifications: A single machine is used. $n$ jobs $\mathbb{J} = \{J_1,...,J_n\}$ are available from the start $t = 0$. Each job can be executed several ...
6k 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 ...
103 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 ...
20 views

### Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?

I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
42 views

### Interval Scheduling problem with more than 1 machine

There are 2 machines. Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine The list of n ...
76 views

### Tournament Scheduling Problem

I am trying to design an algorithm to compute the solution to this problem. Given a list of n tournaments with a name, start_date, end_date, latitude and longitude, find the list of p tournaments in ...
23 views

### Test data for tasks that communicate over network

I am working on a load balancer that schedules tasks that communicate over network. I want to test its performance, but I'm struggling to find test data for it. Currently I try to extract relevant ...
114k views

### What is the average turnaround time?

For the following jobs: The average wait time would be using a FCFS algorithm: (6-6)+(7-2)+(11-5)+(17-5)+(14-1) -> 0+5+6+10+13 -> 34/5 = 7 (6.8) What would the average turnaround time be?
485 views

### Algorithm favours CPU bound or I/O bound processes

Some scheduling algorithms favour CPU bound processes while others favour I/O bound processes. Which algorithm favours which type of process? My answers: SJF favours I/O bound processes.Explanation: ...
20 views

### How to place the deadlines in “Earliest deadline first scheduling” in this question?

So I followed this tutorial to get the concept of "Earliest deadline first scheduling". I have to implement this task >>> TASK. Now the thing which I am not getting in this Task is ...
18 views

### What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
68 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 ...
97 views

### Dynamic job scheduling with earliest time and deadline

I have a real life algorithmic problem and I'm trying to find out if there is any similar widely known algorithmic problem with known solutions that I could adapt to my particular use case. I want to ...
Problem : In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ ...