Competitive Algorithms for the Online Minimum Peak Job Scheduling (MPJS)

Retsef Levi, Professor at the MIT Operations Research Center 

Via Zoom click here

Abstract:
In this talk we will introduce a new online scheduling problem motivated by real life applications of appointment scheduling, as well as new online algorithms to the problem that admit constant competitive ration. Given a sequence of appointments arriving in an online manner, each with a specified duration, one has to schedule each appointment upon arrival within a specified time interval with the goal of minimizing the peak number of simultaneously scheduled appointments. The offline version of this problem is identical to the well-studied offline bin-packing problem. However, the two online version differ in that the MPJS problem allows flexibility to move appointments from one bin to another as long as the scheduling time is maintained. In the talk we will describe new online scheduling algorithm for the online MPJS that admits an asymptotic competitive ratio of 1.5, which is better than the currently proven lower bound on the achievable competitive ratio of the online bin packing problem. This is joint work with Celia Escribe.

Bio:

Retsef Levi is the J. Spencer Standish (1945) Professor of Operations Management at the MIT Sloan School of Management and affiliated faculty at the MIT Operations Research Center. He serves as the MIT Sloan Faculty Co-Director of the Leaders for Global Operations (LGO) program and as the Faculty Director of the MIT Sloan Food Supply Chain Analytics and Sensing (FSAS) Initiative. Levi's is an expert in risk management and the applications of advanced data-analytics within large healthcare and public health systems, food and agriculture supply chains, manufacturing of biologic drugs, cybersecurity, as well as logistics, procurement and inventory management. With over 60 articles in top leading journals, his research has had significant methodological contributions, as well as major impact on practice, including multiple field implementations of his research outcomes. Levi received numerous awards including the NSF Faculty Early Career Development award, the 2008 INFORMS Optimization Prize for Young Researchers and the 2013 Daniel H. Wagner Prize, the 2016 Harold W. Kuhn Award and the 2020 MSOM Responsible Research Award