Scheduling problems are a type of problem in which we are given a set of machines and a set of jobs; we have to specify a schedule for the machines to perform the jobs such that the jobs are completed in the most efficient manner .
As part of the REU CAAR program at the University of Maryland, I worked with three other undergraduate students to improve the best-known algorithm for concurrent open shop, which is a type of scheduling problem. We successfully did so in the online setting. Our work is available on the arXiv.
We developed a more general framework for online scheduling algorithms, which we used not only for concurrent open shop but also coflow scheduling and unrelated parallel machine scheduling, for which we developed the best-known algorithms to date.
We were supervised by Samir Khuller, the department chair of the CS department.
We presented the following poster of our work at a symposium hosted by the National Science Foundation.
What “efficient” means depends on the problem. In our work, our objective was to minimize the sum of weighted completion times. ↩