Online Scheduling with Machine Cost and a Quadratic Objective Function

We will consider a quadratic variant of online scheduling with machine cost. Here, we have a sequence of independent jobs with positive sizes. Jobs come one by one and we have to assign them irrevocably to a machine without any knowledge about additional jobs that may follow later on. Owing to this, the algorithm has no machine at first. When a job arrives, we have the option to purchase a new machine and the cost of purchasing a machine is a fixed constant. In previous studies, the objective was to minimize the sum of the makespan and the cost of the purchased machines. Now, we minimize the sum of squares of loads of the machines and the cost paid to purchase them and we will prove that 4/3 is a general lower bound. After this, we will present a 4/3-competitive algorithm with a detailed competitive analysis.