Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [scheduling]

The tag has no usage guidance.

1
vote
0answers
25 views

Scheduling with Separation Constraint

There are $N$ types of jobs. For each $i$, we have to schedule $T/D_i$ jobs of type $i$ in $T$ timeslots. We know that $\sum_{i=1}^N 1/(D_i+1) = 1$. For each type $i$, the distance between two ...
4
votes
0answers
68 views

Optimal scheduling with delay constraints

Suppose you have $K$ servers numbered $\{1,2,...,K\}$. Playing server $i$ provides a value of $v_i > 0$. However, once you play server $i$, you are not allowed to play it for the next $n_i$ time-...
1
vote
1answer
70 views

Color shifting in a bipartite graph

Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
22
votes
2answers
484 views

Testing whether letters can be scheduled to achieve a word in a regular language

I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each ...
5
votes
0answers
67 views

Series-parallel extension of a partial order respecting a given total order

Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length. An $O(n^3)$ ...
3
votes
0answers
119 views

Stacks serving interval storage requests

An interval storage request is represented by a tuple $(s,t,v)$ satisfying $s<t$, meaning that the value $v$ needs to be stored from time $s$ to time $t$. A stack serves the request $(s,t,v)$ in ...
3
votes
1answer
62 views

Complexity of Finding Optimal Synergistic Set Packings

Motivation: While developing tools for fast execution of machine learning workflows, we realized that many workflows require intermediate results -- sometimes we should cache these results, and ...
2
votes
0answers
97 views

Prove np-hard with reduction from scheduling resources [closed]

We have a system in which we have n number of process and m number of resources.The resources are boolean valued that is they can either have value 0 or 1(in brief suppose the resources as single way ...
-3
votes
2answers
175 views

Who are active researchers in the scheduling theory? [closed]

I have an interest in a postdoc on scheduling problems but I cannot find many researchers who are actively involved in this. Any help?
0
votes
0answers
43 views

Equilvalence among two Scheduling problems

I have two problems for scheduling: Packets arrive at a router. Router schedules them i.e. router determines which one will go out first and which one last. Here, the problem is which packet to send ...
1
vote
1answer
74 views

What does the contention-free communication assumption really mean in the context of DAG scheduling?

In many papers about DAG (directed-acyclic graph) scheduling in distributed systems, the authors make the assumption that the communication between the processors of the system where the DAG is ...
-4
votes
1answer
409 views

Proving NP-hardness of scheduling problem (total weighted completion time)

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this. Just to be precise, ...
1
vote
0answers
91 views

Minimum size counter-example in a 2-machine scheduling problem proof

I'm confused about something in the main proof in this paper (sorry that it's behind a paywall, but I assume many people on here have access to such things through their university and my posting the ...
1
vote
1answer
224 views

Scheduling to maximize idle time

In the context of scheduling maintenance jobs on arcs of a flow network I came across the problem to schedule jobs, indexed by $j$, and given by triples $(r_j,d_j,p_j)$ of (integer) release time, due ...
7
votes
3answers
217 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
95 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 ...
4
votes
1answer
2k 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
175 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
189 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
96 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
73 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
409 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, p_{n-...
3
votes
0answers
168 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 ...
7
votes
1answer
383 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
252 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
402 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
125 views

Problem about machine scheduling [closed]

I am re-posting the problem https://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, ...
3
votes
0answers
127 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
131 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
733 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
277 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. ...
4
votes
2answers
2k 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
698 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
339 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 ...
7
votes
2answers
347 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 ...
5
votes
1answer
684 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
240 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 ...
22
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
505 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 $\...