Scheduling Seminar: Scheduling with Machine-Dependent Priority Lists


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

Kategorie ne Kategorie

Tami Tamir (Reichman University)

Scheduling with Machine-Dependent Priority Lists


June 21, 2023 at 15 CET

Join online or offline on our Youtube channel:


The abstract:
We consider a natural, yet challenging variant of the parallel machine scheduling problem in which each machine imposes a preferential order over the jobs and schedules the jobs accordingly once assigned to it. We study the setting in which a centralized authority assigns the jobs to machines, as well as the associated non-cooperative game in which jobs are controlled by selfish agents who independently choose which machine to use. In the talk, I will define the model, highlight the differences from other well-analyzed job-scheduling optimization problems and coordinated mechanisms, and present some of our results for several natural objectives (e.g., Makespan, lateness, total completion-time minimization) As we show, having machine-dependent priority lists dramatically affects both the computational complexity of the problem and the equilibrium inefficiency. Joint work with Vipin Ravindran Vijayalakshmi and Marc Schroder.


Tami Tamir received her Ph.D. from the computer science department at the Technion in 2001. Her research interests include design and analysis of algorithms, resource allocation problems, and algorithmic game theory. Prior to her Ph.D. studies, she was a member of the performance enhancement group of Intel in Haifa. After graduation, she was a lecturer and postdoctoral fellow at the University of Washington in Seattle, until joining the IDC in 2004. In 2017 and 2019 she was a visiting lecturer in Peking University, Beijing. Tami served as the CS school dean in 2012-2017..


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

Find full info and program at