Semi on-line scheduling on two identical machines

Reviewer: Pradip K. Srimani

Online scheduling of independent jobs on multiple uniform machines with an objective of minimizing the makespan is a classical problem. Classical list scheduling (LS) is the overall best heuristic algorithm known. Recently, people have come up with new algorithms with slightly better worst-case performance than that of LS. They have also started to consider the so-called semi online algorithms, where certain constraints are imposed on the incoming jobs. Different semi online versions arise due to the nature of the constraints imposed. The authors of this paper consider two such variations: processing time of all jobs is normally distributed in a given range, and processing time of the largest job is known a priori. They have developed heuristic algorithms to solve these two scheduling problems and analyzed their worst-case complexity using the traditional approach of comparison to the optimal offline solution. The paper concludes with a set of interesting related open problems. The paper is theoretical in nature; it deals with existence proofs that are derived using theory of inequalities. The results are mathematically elegant. The presentation is lucid, although one needs some mathematical maturity to read it . Relevant past results are provided for completeness.