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

217 questions
Filter by
Sorted by
Tagged with
25 views

### What's the name of this DFS variation

Classical DFS: A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic. A DFS ...
4k views

### SCAN and CSCAN algorithms of disk scheduling

I am having hard time understanding the working of SCAN and CSCAN algorithm of disk scheduling.I understood FCFS,Closest Cylinder Next but heard that SCAN resembles elevator mechanism and got confused....
88 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 ...
49 views

### How to represent sums of piecewise quadratic functions for efficient optimisation?

I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has ...
11k views

### Disk scheduling algorithm - SCAN and C-SCAN

I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a ...
30 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 ...
372 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. ...
87 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 ...
42 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 ...
548 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 ...
377 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). ...
24 views

### Weighted interval set scheduling problem

Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is ...
28 views

### How to compute this CPU scheduling exercise?

How can I compute this type of problem? My doubts are one the number of jobs, I have tried drawing a Gantt chart, but it becomes huge and unmanageable. How am I supposed to represent the results? ...
379 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 + ...
40 views

### interval scheduling variant: 1 machine with 2 tasks need to complete only

I am looking for an optimal solution of an interval scheduling variant. Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum ...
40 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 ...
13 views

### How can the 4-bit page number and 8-bit offset as well as the page table be used to a answer a question like, “how big is each page”? etc

No more information required. I would just like to know how to use the information provided.
12 views

### Does anyone know the answer the following questions on converting logical - physical addresses

Due to the unforeseen pandemic, I am unable to speak to my tutor about the following question. I have emailed him, but I have not had an answer for weeks. Can someone please enlighten me. Image and ...
I'm trying to prove a greedy algorithm works for a specific problem: You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run ...