The tag has no wiki summary.

learn more… | top users | synonyms

7
votes
3answers
172 views

Job scheduling: minimizing number of reads

Consider the following scheduling problem: input: set of computations $C = \{c_1, ..., c_n\}$ set of computing nodes $P = \{p_1, ..., p_n\}$ Dependency graph $D$ between jobs (DAG) $(c_i,c_j)$ ...
0
votes
0answers
59 views

Are there any approaches to the following scheduling problem?

Consider the following problem: we are given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$. Every task $n_i$ is qualified with two parameters: The time it takes to be completed ($t_i$) and, The ...
2
votes
1answer
54 views

Existing benchmarks for scheduling problems?

Which benchmarks exist to evaluate the performance of algorithms for Job-Shop or Flow-shop scheduling problems?
6
votes
1answer
78 views

Minimize makespan on identical machines when jobs are vectors

Given are $n$ $d$-dimensional vectors and $m$ machines where $d$ need not be fixed. The objective is to minimize the makespan i.e., assign the vectors to machines such that the maximum of the ...
3
votes
0answers
37 views

Optimization of class schedule

I am creating a scheduling program that I need to either optimize or prove that what I have is already optimal. I have n groups, all of which need to do some activity a in time slot t. A person can ...
3
votes
0answers
78 views

Minimize the time when guard observes more than one event (for fixed number of guards)

Consider the following optimization problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which ...
2
votes
0answers
58 views

What is the use of the multi-project scheduling problem compared to single-project?

I am doing some research regarding (resource-constrained) scheduling, and in several papers I find multi-project scheduling problems. What is so special about multi-project scheduling problems ...
4
votes
1answer
296 views

Is This Scheduling Problem NP-Hard?

The scheduling problem (arising from distributed computing) is defined as a decision problem as follows: Instance: A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, ...
2
votes
0answers
50 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 ...
7
votes
1answer
252 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
169 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
262 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
112 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
93 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
91 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
125 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
310 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
172 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
432 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
422 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
309 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
280 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
625 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
221 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
1k 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
448 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 ...