Narrow Results

In this paper, we consider the on-line single machine scheduling of unit time jobs with rejection. All jobs arrive on-line over a list (one by one). For each arriving job, the on-line algorithm must decide immediately to accept or reject it. The objective is to minimize the maximum quadratic completion time of accepted jobs plus the total rejection cost of rejected jobs. For this problem, we show that 1.7299 is a lower bound on the competitive ratio and present a simple greedy algorithm with the competitive ratio 2. Furthermore, we also provide a modified greedy algorithm with a better competitive ratio $1+\frac{\sqrt{3}}{2}\approx 1.86602$.

In this paper, some results concerning the k-truck problem are produced. Firstly, the algorithms and their complexity concerning the off-line k-truck problem are discussed. Following that, a lower bound of competitive ratio (1+θ)·k/(θ·k+2) for the on-line k-truck problem is given, where θ is the ratio of cost of the loaded truck and the empty truck on the same distance, and a relevant lower bound for the on-line k-taxi problem followed naturally. Thirdly, based on the Position Maintaining Strategy (PMS), some new results which are slightly better than those of [11] for general cases are obtained. For example, a c-competitive or (c/θ+1/θ+1)-competitive algorithm for the on-line k-truck problem depending on the value of θ, where c is the competitive ratio of some algorithm to a relevant k-server problem, is developed. The Partial-Greedy Algorithm (PG) is used as well to solve this problem on a line with n nodes and is proved to be a (1+(n-k)/θ)-competitive algorithm for this case. Finally, the concepts of the on-line k-truck problem are extended to obtain a new variant: Deeper On-line k-Truck Problem (DTP). We claim that results of PMS for the STP (Standard Truck Problem) hold for the DTP.

We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m identical processors with resource augmentation, whose objective is to minimize the makespan. In this case, the approximation algorithms are given k (k ≥ 0) extra processors than the optimal off-line algorithm. For on-line algorithms, the Greedy algorithm and shelf algorithms are studied. For off-line algorithm, we consider the LPT (longest processing time) algorithm. Particularly, we prove that the schedule produced by the LPT algorithm is no longer than the optimal off-line algorithm if and only if k ≥ m - 2.

In this paper, we consider a semi-on-line scheduling problem of two identical machines with common maintenance time interval and nonresumable availability. We prove a lower bound of 2.79129 on the competitive ratio and give an on-line algorithm with competitive ratio 2.79633 for this problem.