Datum / čas
Date(s) - 13.12.
15:00 - 17:00
Kategorie
Presenter – Céline Swennenhuis (ALGO, TU Eindhov.) Invited by – Michael Pinedo (New York Uni)
A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
Dec 13, 2023 at 15 CET
Join online or offline on our Youtube channel: Scheduling seminar – YouTube
Abstract:
In a classical scheduling problem, we are given a set of n jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on m identical parallel machines that minimizes the makespan. Using the standard 3-field notation, it is known as Pm|prec, p_j=1|Cmax. Settling the complexity of Pm|prec, p_j=1|Cmax even for m=3 machines is, together with Subgraph Isomorphism, among the last two open problems from the book of Garey and Johnson [GJ79] for which the computational complexity remains a mystery. We present an algorithm for this problem that runs in subexponential time (2^{O(sqrt(n)log(n))} time) when m = o(n).
Find full info and program at https://schedulingseminar.com/.