Semi-online scheduling: A survey

In real-life applications, neither all the inputs of an algorithm are available at the outset, as in an offline framework, nor do they occur one by one in order, as in an online setup. Semi-online is an intermediate theoretically and practically significant framework with additional information on the successive inputs to address the limitations of online and offline frameworks. One key motivation for studying semi-online algorithms is to investigate how additional information can improve the performance of online algorithms. In online scheduling, jobs are received one by one and each job must be scheduled irrevocably before the availability of the next job. Semi-online scheduling is a relaxed variant of online scheduling, where some Extra Piece Information (EPI) about the whole job sequence is known a priori, or additional algorithmic extensions are allowed. The EPI may include one or more of the following parameter(s) such as the maximum processing time, the total sum of the processing time of all jobs, arrival sequence of the jobs based on processing time, optimum makespan value, or the range of processing time. The design of improved competitive semi-online algorithms for m-machine scheduling problem has received significant research attention after the seminal works of Liu et al. (1996) and Kellerer et al. (1997). In this survey article, we highlight the scholarly contributions and stateof-the-art results for semi-online scheduling on parallel machine models such as identical, uniformly related, and unbounded batch by considering preemptive and non-preemptive as the processing formats with optimality criteria such as makespan, load balancing, machine cost, Lp-norm load balancing, early work maximization, and the sum of completion time plus total penalty cost. The survey begins with a brief introduction to the online and semi-online frameworks for the m-machine scheduling problem and presentation of a standard well-known algorithmic performance measure, the competitive analysis. Practical applications, preliminary concepts, research motivation, and taxonomy of semi-online scheduling are presented as a foundation for a basic understanding of the area. State-of-the-art results achieved by the deterministic semi-online algorithms are classified and presented based on machine models and known EPI with a special focus on novel intuitions and algorithmic development. We discuss and analyze the impact of EPI on the competitive performance of semi-online algorithms. A classification of the references based on specific EPI is outlined for further research investigation. Finally, we conclude the survey with non-trivial research challenges and open problems.

Automated summary

The semi-online framework provides additional information to address the limitations of both online and offline setups in handling continuous inputs. The motivation for studying semi-online algorithms is to improve the performance of online algorithms. Semi-online scheduling is a relaxed variant of online scheduling that allows for advance knowledge of the entire job sequence through extra information.