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

learn more… | top users | synonyms

-1
votes
0answers
17 views

How does the OS regulate CPU permissions? [duplicate]

How does the operating system limit the instruction set of the CPU to other processes? I know that it'd take forever for the loader to parse out the executable code, so is there are hardware ...
0
votes
2answers
57 views

Schedule two trains whose tracks overlap so they don't crash

I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve. Recently I was asked this question and did not even know what algorithmic technique to ...
-1
votes
0answers
45 views

How can I prove that scheduling problem F2//Lmax is NP-Hard?

I'm trying to solve it via reduction to the 2-Partion problem. All online resource are leading to a single solution, which is: http://i.imgur.com/mkPrCzb.png (taken from ...
0
votes
0answers
20 views

Optimality of EDF

For Earliest Deadline First, I have read that if utilization is less or equal to 1, the task set is schedulable under EDF. But does this criteria expresses the optimality for EDF? If not, how can we ...
-1
votes
0answers
18 views

Difference between fixed and dynamic priority scheduling

What are differences between fixed and dynamic priority scheduling? For example how you tell RMS from EDF scheduling models and what do they differ at when it comes to scheduling them (in a single ...
1
vote
1answer
21 views

How profiling is done in trace scheduling?

I'm trying to understand how trace scheduling works. The book that I'm reading, Engineering a Compiler by Keith D. Cooper & Linda Torczon, states that this method is using profiling. Profiling ...
2
votes
1answer
41 views

Time quantum assignment to processes

In a book I am reading it is stated that an input/output intensive process should receive a higher time quantum whereas a computing intensive process on the other hand should receive a lower one. Here ...
3
votes
1answer
195 views

Weighted interval scheduling with m-machines

I am looking for some advice and direction on solving the weighted interval scheduling problem with $m$-machines to plan some experimental "wet lab" procedures. The problem is very similar to the ...
0
votes
0answers
124 views

Algorithm for scheduling timetable for student management system

I am developing the timetable module for a student management system. I am finding it difficult to design/develop it. It can be assumed that a given teacher is capable of teaching any standard whether ...
1
vote
0answers
16 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 ...
0
votes
1answer
33 views

Why can no task have a utilization rate greater than one?

Let $C_i$ be the execution time for task i, $T_i$ be the task period and utilization rate $U = \frac{C_i}{T_i}$ Then $U$ must be less or equal to $1$ for the task to be schedulable ...
0
votes
0answers
41 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
1answer
66 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 ...
1
vote
1answer
39 views

Is Starvation Possible in LOOK Algorithm

The LOOK algorithm (wiki) is the same as the SCAN algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any ...
2
votes
0answers
33 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. ...
0
votes
1answer
17 views

Is there a difference between the name scheduler and scheduling?

Sometimes I read about the term "scheduler" (offline-scheduler, online-scheduler,...) and then I see terms called "scheduling" (offline-scheduling, online-scheduling, preemptive scheduling, non ...
2
votes
1answer
135 views

Can Shortest Job First Scheduling be subject to convoy effect?

Look at the below table for example : Look at the Non-Preemptive SJF table Suppose if the burst time of process $P_1$ was a very large number compared to $7$, the processes $P_3,P_2$ and $P_4$ have ...
4
votes
2answers
69 views

Scheduling a tournament with variable game lengths

I want to solve the following scheduling problem: We have $N$ resources and $\binom{N}{2}$ tasks, such that every task requires exactly two resources and every pair of resources is required by exactly ...
2
votes
2answers
115 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
165 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 ...
0
votes
0answers
60 views

Reduction of specific scheduling problem to show np-completeness

Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k: Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of ...
-1
votes
1answer
165 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 ...
1
vote
0answers
43 views

Approximation for fewest incompatibilities in a scheduling algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
3
votes
1answer
105 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
2
votes
3answers
77 views

Why does lower integer represent higher priority in scheduling literature?

I'm studying Real Time Systems, and in the textbook most of the focus is on scheduling algorithms. (Textbook: Real-Time Systems by Jane W. S. Liu) In the algorithms that involve priorities, it is ...
0
votes
0answers
58 views

Solve a basic mutex lock problem while preventing deadlock

I am solving a problem with a bridge, where you have a one way bridge with people coming from each side. To solve this problem while preventing deadlock (two people going opposite directions on the ...
-1
votes
1answer
32 views

How do you come up with greedy algorithm for deadline scheduling when comparing x_subscript(i) and y_subscript(k)?

So there are two boxing teams, my team A and the opposing team B, each with m boxers. Based on the player's ranking of skill, x_subscript(i) being the ranking for ith boxer for team A and ...
3
votes
1answer
60 views

Offline scheduling fully determined arbitrary jobs in multiprocessor setting

Let $\mathcal{J} = \{J_1,...,J_n\}$ be a set of jobs with each $J_i = [a_i,r_i,d_i]$ where the job becomes available at its arrival time $a_i$, requires $r_i$ execution time and needs to be finished ...
0
votes
1answer
76 views

Round-Robin Scheduler - What exactly is the quantum time used for?

Suppose you have three stages for a job: Creation stage = the job gets created Executing stage = the job is executed/served Finishing stage = the job is "marked" as finished. Now, say the quantum ...
1
vote
1answer
42 views

top k selection in fixed size priority queue with dynamically changing values [duplicate]

My question is something of a scheduling problem. I'd like to know what algorithm to use to find the top k items in a fixed length queue in which the values of the items change dynamically.basically a ...
2
votes
0answers
138 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 ...
6
votes
1answer
114 views

Scheduling Algorithm for aperiodic multiprocessor tasks

I've got a System, which is defined as follows: A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the ...
2
votes
1answer
89 views

Arranging tasks with specific constraints (scheduling)

I have the following problem: Given a set of tasks and their duration, i need to arrange them taking in consideration some constraints; Here's an example: Suppose we are scheduling talks in a ...
3
votes
0answers
75 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 ...
1
vote
1answer
62 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 ...
0
votes
1answer
139 views

Hard disk scheduling - N-set-SCAN vs FSCAN

I'm wondering which is a better scheduling algorithm to use. The only real difference I can see is that in FSCAN there are two queues, and when a scan begins all requests are put in one queue and the ...
0
votes
1answer
85 views

Scheduling optimization problem in theta(n)

I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to ...
2
votes
0answers
207 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 ...
8
votes
3answers
478 views

Find out whose turn it is to buy the croissants

A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The ...
5
votes
1answer
560 views

Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...
2
votes
1answer
309 views

A variant of job assignment (scheduling) problem with variable time span

The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take ...
0
votes
0answers
255 views

Algorithm to solve job assignment problem

Can someone suggest an algorithm to solve job assignment problem with condition? With condition means that some jobs cannot be done by some workers. For example table as shown below: In this table ...
4
votes
1answer
264 views

Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
5
votes
4answers
2k views

Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum. Now I'm not sure if a greedy algorithm will do the trick. That is, sort by ...
4
votes
0answers
186 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 ...
11
votes
2answers
254 views

Job scheduling with a bottleneck problem

Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete. Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a ...
3
votes
1answer
120 views

Minimize the total execution time of jobs executed by 3 processors in sequence

There are 3 processors: $P_1$, $P_2$, $P_3$. $P_1$ can execute only one job while the other two can execute any number of jobs in parallel. Each job consists of 3 parts, and each part is processed by ...
1
vote
1answer
326 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 ...
2
votes
1answer
66 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 ...
0
votes
1answer
44 views

Process scheduling confusion

I've got a confusion in the following section of a book. Here we taking about FCFS Scheduling. I feel that calculation table is incorrect in the book. Because P3 got completed at time 7, it's ...