Scheduling is an optimisation problem. Its goal is to order 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.
0
votes
0answers
34 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
69 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 ...
0
votes
0answers
17 views
Interval Scheduling Optimization type of Problem, optimal order of manufacture
We wish to manufacture n distinct hardware items. Each item needs to go through 3 stages of processing. The first stage called design can only be performed by our master designer who works by starting ...
3
votes
0answers
25 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 ...
6
votes
1answer
72 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
83 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
50 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
45 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
0answers
26 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 ...
2
votes
1answer
136 views
Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler
Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are ...
3
votes
1answer
73 views
Single machine job scheduling
Given $n$ jobs, schedule them such that the weighted sum is minimum.
weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :
$S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
7
votes
1answer
163 views
Can Santa be both fair and efficient?
As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning ...
3
votes
1answer
200 views
Maximum Schedulable Set Zero-Lateness Deadline Scheduling
This is a homework problem for my introduction to algorithms course.
Recall the scheduling problem from Section 4.2 in which we sought to
minimize the maximum lateness. There are $n$ jobs, each ...
3
votes
1answer
471 views
First-Come-First-Serve scheduling algorithm - what happens to process after returning from I/O? where does it go in the queue
There are three processes in line
P0, P1, P2
1) P0 registered and executes
2) P0 I/O blocked
3) so P1 executes
4) P1 I/O blocked
5) P0 executes. ??
After P1 must come P2 that is what FCFS ...
0
votes
0answers
50 views
Scheduling: advance deadline for implicit-deadline rate monotonic algorithm
Given a set of tasks (execution time, deadline=period):
$T_1(20,100)$
$T_2(30,250)$
$T_3(100,400) $
Now I want to restrict the deadlines as $D_i = f \cdot P_i$, where $D_i$ is new deadline for ...
1
vote
1answer
136 views
NP-completeness of scheduling to minimise tardy tasks with release times
In "Computers and Intractability A Guide to the Theory of NP-Completeness" textbook pp 236, "Sequencing to minimize tardy tasks" is NP-complete.
To be specific the problem is as follows:
For each ...
4
votes
1answer
119 views
Getting parallel items in dependency resolution
I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
4
votes
1answer
3k 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?
8
votes
2answers
201 views
Ordering elements so that some elements don't come between others
Given an integer $n$ and set of triplets of distinct integers
$$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$
find an algorithm which either finds a permutation ...
13
votes
2answers
166 views
How does variance in task completion time affect makespan?
Let's say that we have a large collection of tasks $\tau_1, \tau_2, ..., \tau_n$ and a collection of identical (in terms of performance) processors $\rho_1, \rho_2, ..., \rho_m$ which operate ...
6
votes
1answer
156 views
Are two-level schedulers only useful to manage swapping?
Two-level scheduling is useful when a system is running more processes than fit in RAM: a lower-level scheduler switches between resident processes, and a higher-level scheduler swaps groups of ...
4
votes
1answer
146 views
Analyzing load balancing schemes to minimize overall execution time
Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given ...
