New Competitive Semi-online Scheduling Algorithms for Small Number of\n Identical Machines

Design and analysis of constant competitive deterministic semi-online\nalgorithms for the multi-processor scheduling problem with small number of\nidentical machines have gained significant research interest in the last two\ndecades. In the semi-online scheduling problem for makespan minimization, we\nare given a sequence of independent jobs one by one in order and upon arrival,\neach job must be allocated to a machine with prior knowledge of some Extra\nPiece of Information (EPI) about the future jobs. Researchers have designed\nmultiple variants of semi-online scheduling algorithms with constant\ncompetitive ratios by considering one or more EPI. In this paper, we propose\nfour new variants of competitive deterministic semi-online algorithms for\nsmaller number of identical machines by considering two EPI such as Decr and\nSum. We obtain improved upper bound and lower bound results on the competitive\nratio for our proposed algorithms, which are comparable to the best known\nresults in the literature. In two identical machines setting with known Sum, we\nshow a tight bound of 1.33 on the competitive ratio by considering a sequence\nof equal size jobs. In the same setting we achieve a lower bound of 1.04 and an\nupper bound of 1.16 by considering Sum and a sequence of jobs arriving in order\nof decreasing sizes. For three identical machines setting with known Decr and\nSum, we show a lower bound of 1.11 on the competitive ratio. In this setting,\nwe obtain an upper bound of 1.5 for scheduling a sequence of equal size jobs\nand achieves an upper bound of 1.2 by considering a sequence of decreasing size\njobs. Further we develop an improved competitive algorithm with an upper bound\nof 1.11 on the competitive ratio.\n