### Page Content

### to Navigation

# Parameterized results on scheduling under side constraints

**René van Bevern (Novosibirsk State University and Sobolev Institute of Mathematics)**

This talk reports on new results on the parameterized complexity of the following scheduling problems.

**Parallel identical machines, release times and deadlines.**

P|p_{j}, d_{j}| is the problem of checking feasibility for processing each job non-preemptively for p_{j} ∈ **N** time within a given time interval [r_{j}, d_{j}), r_{j},d_{j} ∈ **N**, on m parallel identical machines.

**Resource and precedence constraints.**

P|prec|C_{max} is the problem of non-preemptively processing each job j for a given amount p_{j} ∈ **N** of time on parallel identical machineswith minimum makespan, where an additionally given partial order imposesprecedence constraints on the jobs. That is, a job start only after its predecessors finish.

**Routing Open Shop.**

Open Shop is the problem of processing each job j on each machine q non-preemptively for p_{iq }∈ **N** time with minimum makespan. Each machine processes only one job at a time; each job is processed by only one machine at a time. In Routing Open Shop, the jobs are located in the vertices of a graph with edge weights that determine the timeneeded for moving machines between vertices.

Date | Speaker | Location | Language |
---|---|---|---|

29.03.2017 12:00 | René van Bevern | TEL 512 | English |