Title: The tractability of hard scheduling problems: a parametrized complexity approach

Speaker: Professor Daniel Oron

Summary:
We consider a single machine scheduling problem with generalized due-dates to minimize various lateness measures. We prove that the problems are NP-hard in general and investigate their difficulty from a parametrized complexity perspective. We develop efficient algorithms for settings where some, or all, the range of possible values for the various parameters are bounded. This is a novel approach to evaluating the true difficulty of combinatorial optimisation problems with bounded parameter sizes.

Biography:
Daniel Oron is a Professor of Operations Research in the discipline of Business Analytics at the University of Sydney. He holds a PhD in Operations Research from the Hebrew University of Jerusalem. His area of expertise is combinatorial optimisation with a focus on scheduling theory. He is widely known for his work on multi-agent scheduling, resource allocation problems, serial and parallel batching models and production problems under varying conditions. His work has been published in leading OR journals and he currently serves at an associate editor in the Journal of Industrial and Management Optimization.

WED 1 NOVEMBER 2023 16:00-17:00 (AEDT, Melbourne Time)

MEETING ID: 873 1557 5255; PASSWORD: 778635