Learning to Schedule

We consider the following algorithmic question: given a list of jobs, each of which requires a certain number of time steps to be completed while incurring a random cost in every time step until finished, learn the relative priorities of jobs and make scheduling decisions of which job to process in each time step, with the objective of minimizing the expected total cumulative cost. Here, we need an algorithm that seamlessly integrates learning and scheduling. This question is motivated by several applications. Modern data processing platforms handle complex jobs whose characteristics are often unknown in advance, in which case, it is difficult to judge which jobs have higher priorities than others before accumulating enough information about the jobs [11]. Here, there is significant uncertainty in determining the relative importance of jobs or tasks, and moreover, the population of jobs may be highly dynamic, e.g., they may have all distinct features. Nevertheless, these platforms need to start processing jobs in a sequence based on partial information, which potentially results in undesired delays. However, as a system learns more about the jobs' features, it may flexibly adjust scheduling decisions to serve the jobs with high priority first.