The scheduling tag has no wiki summary.
2
votes
0answers
101 views
Proving greedy algorithm is optimal for a scheduling problem
First, the problem discription:
For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of ...
2
votes
0answers
41 views
Scheduling with RSVP deadline and possible cancellations
There is a sequence of events $e_1,\ldots,e_n$. $s(e_i), t(e_i)$ and $w(e_i)$ is the starting, terminating time and the weight of $e_i$, respectively. $p(e_i)$ is the probability of the event getting ...
6
votes
1answer
202 views
$NP$-hardness of scheduling problem
I have been attempting to show that this problem is $NP$-complete but haven't been successful. I wonder if anyone has a suggestion for a problem I could reduce to it.
$CALLS$: Suppose we have ...
2
votes
0answers
130 views
Is this variation of the “sequencing with release times and deadlines” problem NP-complete?
The following problem is known to be NP-complete. It can be found in pages 236 and 70 of Garey & Johnson. In this book this problem is known either as ...
3
votes
1answer
192 views
Is this multiprocessor scheduling problem with overlaps NP-Hard?
The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the ...
4
votes
0answers
110 views
Weighted and complex slowdown papers
I'm trying to find some papers exploring complex variants of the slowdown metric in job scheduling systems (particularly grids).
The problem is that "weighted", "slowdown" and "complex" aren't really ...
4
votes
0answers
89 views
Problem about machine scheduling [closed]
I am re-posting the problem http://mathoverflow.net/questions/92783/random-task-scheduling-problem here because I think people here are more familiar with this topic.
Assume there are $m$ tasks, each ...
3
votes
0answers
77 views
minimizing makespan for related machines
Any reference is appreciated.
There are $n$ jobs and $m$ machines, machines has speeds and jobs have processing times. It takes $p_j/s_i$ units of time for machine $i$ with speed $s_i$ to process job ...
3
votes
2answers
118 views
Approximation results on scheduling under an uncommon constraint
I am looking for any approximation results for unrelated multiprocessor scheduling problem with precedence constraints (minimizing makespan), i.e. $R|prec|C_{max}$, with the constraint that some tasks ...
0
votes
0answers
232 views
Algorithm to maximize profit: ways to solve/approach? (Advanced NP-Complete)
This one's hard, so all help really appreciated!
I know it is NP-Complete and thus cannot be solved in polynomial time, but looking for help in analysis, i.e. what type of NP-Complete problem it ...
1
vote
1answer
129 views
2D grid placement problem
Data for the problem:
2D grid(lattice) of size NxN
n nodes placed on the grid:node_1,node_2,…node_n
Each of nodes contain some data:
a. node_i is presented by 3 parameters (x_i,y_i,t_i)
b. ...
3
votes
2answers
296 views
Dealing with duplicates in Genetic Algorithm
I'm using Genetic Algorithm to create a rota for home-care organisation. All the groundwork is complete, I'm getting the results, but results are not as good as expected.
If I calculate fitness for ...
8
votes
2answers
301 views
Is this a known combinatorial optimization/scheduling problem?
We are given $n$ stacks which hold "items" of different colour and a machine that can process multiple items of the same colour in one go. At each step, we can remove one item from the top of each ...
10
votes
0answers
300 views
Covering a set of intervals, continued
Peter Taylor and Tsuyoshi Ito solved a previous question that I posted:
Covering a set of intervals
I have a slight variation on that question that I'd also like to ask. I'm not sure what the ...
6
votes
2answers
255 views
Is the problem of finding the chromatic number of a modified interval graph NP-Complete
Few days ago I was working on interval graphs to solve the known problem of resource allocation, as we know there is a greedy approach that solves this problem (chromatic number) in polynomial time ...
4
votes
1answer
560 views
Covering a set of intervals
(I was redirected from mathoverflow in asking this)
Hello,
I'm trying to determine if the following problem is solvable in polynomial time: given a collection of $n$ half-open intervals $[s_i, t_i)$ ...
0
votes
1answer
214 views
Event scheduling.
Given a set of actions (that are performed at a rate of one action per unit time) where each must be performed at an assigned frequency (assume the frequencies add up so things can work) and at ...
18
votes
2answers
898 views
Polynomial time approximation algorithms for machine scheduling: how many open problems are left?
In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, ...
3
votes
2answers
430 views
Counting complexity of a scheduling problem. [closed]
Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements ...
