Scheduling Seminar: Efficient Algorithms and Provably Good Solutions for NP-hard Scheduling Problems

0

Datum / čas
Date(s) - 12.05.
15:00 - 17:00

Kategorie ne Kategorie


Martin Skutella (TU Berlin)

Efficient Algorithms and Provably Good Solutions for NP-hard Scheduling Problems

May 12 at 15 CET

Join online: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A/featured

Machine scheduling problems are among the first optimization problems for which approximation algorithms have been analyzed. An approximation algorithm is a polynomial-time algorithm which always finds a feasible solution whose objective function value is within an a priori known factor (performance ratio) of the optimum solution value. In this talk we focus on identical parallel machine scheduling with total weighted completion time objective. We present, among other things, a refined analysis of the performance ratio for the weighted shortest processing time first (WSPT) rule. This is joint work with Sven Jäger.

The seminar is organized by Zdeněk Hanzálek (CIIRC CTU in Prague), Michael Pinedo (New Y ork University) and Guohua Wan (Shanghai Jiao Tong).

Find full info and program at https://schedulingseminar.com/.