TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 29.03.2017

isti-logo

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|pj, dj| is the problem of checking feasibility for processing each job non-preemptively for pjN time within a given time interval [rj, dj), rj,djN, on m parallel identical machines.

Resource and precedence constraints.

P|prec|Cmax is the problem of non-preemptively processing each job j for a given amount pjN 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 piq 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

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe