TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 29.03.2017


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.


René van Bevern
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe