New Variants of Online and Offline Scheduling with Calibrations

Description

Scheduling is an area of computer science which studies how to efficiently execute aseries of tasks, or jobs. A scheduling algorithm decides when and where to run the jobs(possibly with some constraints) to minimize an objective function.Recent work has considered scheduling on machines that need to be calibrated. Thesemachines are assumed to be high-performance and high-maintenance, and performvery precise tasks, for example, medical and healthcare equipment or embedded systemswith input sensors. As such, they need to be calibrated before they can be trusted toperform a job. Performing these calibrations can be very expensive, possibly much morethan the cost of running the machines. The calibrations are only effective for a setperiod of time, after which the machine may no longer be accurate, and must be(expensively) recalibrated before running more jobs.The goal of algorithms in this framework is to minimize the number of calibrations.This objective function has an interesting property: in most objective functions (say,minimizing total flow time, or maximizing number of jobs completed by a deadline), it isgenerally profitable to schedule a job as early as possible. However, to minimizecalibrations, the algorithm wants to group jobs together as much as possible, possiblydelaying some jobs considerably. The known algorithms in this framework are designedto effectively handle this tradeoff: grouping jobs for more efficient calibrations, whilemaintaining a reasonable schedule where jobs are not delayed too long.Our goal in this project is to extend the initial work on scheduling with calibrations. Inparticular, we want to generalize the model to give more algorithms that could be usefulin practical situations (in a high-precision manufacturing plant, for example). As such,we want algorithms that perform well in minimizing the number of calibrations, whilebeing practical to implement and run. Our initial results show that very simple---though difficult to analyze---algorithms can perform very well even with constraintsthat initially seem difficult to tackle.?